二叉排序树

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值
（3）左、右子树也分别为二叉排序树
（4）没有键值相等的节点。

平均查找长度

分为成功和失败两种查找长度

查找成功：

成功平均查找长度 =（每层结点的个数 × 当前深度）之和 / 总结点数。

失败查找

失败平均查找长度 = （失败结点的个数 × 失败结点的父结点所在深度）之和 / 总失败结点数