二叉排序树与平衡二叉树
二叉排序树是这样一棵树：所有非叶子结点至多拥有两个儿子（Left和Right）；所有结点存储一个关键字；非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；
含有n个结点的二叉排序树却是不唯一的。所以对于含有同样关键字序列的一组结点，结点插入的先后次序不同，所构成的二叉排序树的形态和深度不同。而二叉排序树的平均查找长度ASL与二叉排序树的形态有关，二叉排序树的各分支越均衡，树的深度浅，其平均查找长度ASL越小。
由此可见，在二叉排序树上进行查找时的平均查找长度和二叉排序树的形态有关。在最坏情况下，二叉排序树是通过把一个有序表的n个结点插入生成的，由此得到二叉排序树退化为一棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同，也是（n+1）/2。在最好情况下，二叉排序树在生成过程中，树的形态比较均匀，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，就平均性能而言，二叉排序树上的查找和二分查找相差不大，并且二叉排序树上的插入和删除结点十分方便，无需移动大量结点。因此，对于需要经常做插入、删除、查找运算的表，宜采用二叉排序树结构。由此，人们也常常将二叉排序树称为二叉查找树。
平衡二叉排序树是一种改进的二叉排序树，一棵平衡二叉排序树或者是一棵空树，或者是一棵任意一结点的左子树与右子树的高度至多差1的二叉树排序树。对于二叉排序树上的任何结点，其平衡因子定义为该结点左子树的高度减去该结点右子树高度。任一结点的平衡因子只可能是-1，0，1。平衡的二叉排序树的查找方法与一般的二叉排序树完全一样，其优点是总能保持查找长度为O(log2n)量级。往平衡的二叉排序树插入新结点时，需要对树的结构进行必要调整，以动态地保持平衡二叉排序树的特点。
