二叉排序树

又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：

• 若他的左子树不空，则左子树上所有节点的值均小于它根节点的值
• 若他的右子树不空，则右子树上所有节点的值均大于根节点的值
• 它的左、右子树也分别为二叉排序树

二叉排序树特点

是以链接的方式存储，保持了链接存储结构在执行插入或删除操作室，不用一栋元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入、删除时间性能比较好。而对于二叉排序树的查找，走的就是从根节点到需要查找的节点的路径，其比较次数等于给定值的节点在二叉树的层数。极端情况下，最少为1次，即根节点就是要找的点。最多也不会超过树的深度。可问题就在于，二叉排序树的形状是不确定的= = #

平衡二叉树

是一种排序二叉树，其中每个节点的左子树和右子树高度差之多等于1，也称AVL树。

从名字上也能看出来，这是一种高度平衡的二叉排序树。什么叫高度平衡，就是要么是一棵空树，要么它的左、右子树都是平衡二叉树。且左、右子树深度差绝对值不超过1.我们将二叉树上节点左子树深度减去右子树深度的值称为平衡因子BF（Balance Factory）。

距离插入节点最近的，且平衡因子绝对值大于1的节点为根的数，我们称为最小不平衡子树。