java源码之二叉查找树与二叉平衡树
二叉排序树
解决查询速度慢的方案除了哈希表外，还可以使用二叉排序树。查询慢主要是因为不知道元素的位置，使用hash函数映射虽然解决了问题，但其并不稳定，当出现大量的哈希碰撞后其表现更像一个链表，查询速度大大降低。 二叉排序树的方案则是使元素有序，这样便可以使用二分法进行查找了，虽然效率相比hash函数低一些，但可以通过AVL树、红黑树等增加稳定性。
定义
二叉排序树(Binary Sort Tree)，又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
- 它的左、右子树也分别为二叉排序树
如下就是一棵简单的二叉排序树：
当对这棵树进行中序遍历时，其结果将按照从小到大排序。
查询操作
二叉排序树的查找时间复杂度为O(lg n)，查找使用二分法。要在上图中找到元素37，只需要四次操作即可。 首先，找到根元素22，37比22大，所以淘汰左子树，再找到35，淘汰左子树，再找到41，进入左子树，得到37。可以看到其速度比挨个对比高了很多。
插入操作
二叉排序树的插入操作和查询类似，也需要通过二分法进行查找，找到合适的位置再插入元素，所以其插入速度相比链表较慢。
删除操作
从二叉排序树中删除一个元素主要分为三种情况。 例如要从下面这个二叉排序树中删除一个元素：
- 删除的元素是叶结点，这时可以直接删除它。比如要删除值为1的元素，删除它对树没有任何影响。
- 删除的元素仅有左孩子或者仅有右孩子时，直接让其孩子顶替它即可。比如要删除元素35，只需要用41顶替它即可。
- 删除的元素既有左孩子又有右孩子，这时删除它相对复杂。一种好的方式是找到它的前驱或者后继来代替它。比如要删除元素9，就用6或者13代替它即可。
缺陷
一棵普通的二叉排序树也会出现不平衡问题，如果插入的数据都在树的一侧，就会使得树的深度迅速增大，每次二分查找可以排除的数据很少，从而查询速度严重下降，比如下方这棵树：
要查找值为2的元素，使用二分法和使用链表速度差不多。
为了解决这种问题，就需要在元素插入时即进行修正，后续介绍的AVL树和红黑树就是两种不同的解决方案。
平衡二叉树（AVL Tree）
二叉排序树很好的平衡了插入与查找的效率，但不平衡的二叉排序树效率大打折扣。AVL树就是一种解决此问题的方案。
定义
平衡二叉树(Self-Balancing Binary Search Tree 或Height-Balanced Binary Search Tree)，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1 。它是一种高度平衡的二叉排序树。意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1 。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balance Factor)，那么平衡二叉树上所有结点的平衡因子只可能是-1 、0 和1。 如下图就是一棵AVL树：
实现原理
平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。最小不平衡子树是指距离插入结点最近的，且平衡因子的绝对值大于1 的结点为根的子树。 下面通过一个实例，了解平衡二叉树的构建过程。 假如我们要将数组int[] a = {3, 2, 1, 4, 5, 6, 7, 10, 9}构建成一棵二叉排序树，如果直接按照二叉排序树的定义，会得到下面的结果：
以下为创建过程：
