CH04-排序二叉树

解决查询速度慢的方案除了哈希表外，还可以使用二叉排序树。我们知道，查询慢主要是因为不知道元素的位置，使用 hash 函数映射虽然解决了问题，但其并不稳定，当出现大量的哈希碰撞后其表现更像一个链表，查询速度大大降低。

二叉排序树的方案则是使元素有序，这样便可以使用二分法进行查找了，虽然效率相比 hash 函数低一些，但可以通过 AVL 树、红黑树等增加稳定性。

HashMap 在 JDK1.8 的实现中，就结合了哈希表的高效和红黑树的稳定，我们之后会详细分析其实现。

定义

二叉排序树(Binary Sort Tree)，又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：

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

如下就是一棵简单的二叉排序树：

当对这棵树进行中序遍历时，其结果将按照从小到大排序。

查询操作

二叉排序树的查找时间复杂度为 O(lg n)，查找使用二分法。要在上图中找到元素 37，只需要四次操作即可。

首先，找到根元素22，37比22大，所以淘汰左子树，再找到35，淘汰左子树，再找到41，进入左子树，得到37。可以看到其速度比挨个对比高了很多。

插入操作

二叉排序树的插入操作和查询类似，也需要通过二分法进行查找，找到合适的位置再插入元素，所以其插入速度相比链表较慢。

删除操作

从二叉排序树中删除一个元素主要分为三种情况。

例如要从下面这个二叉排序树中删除一个元素：

1. 删除的元素是叶结点，这时可以直接删除它。比如要删除值为 1 的元素，删除它对树没有任何影响。
2. 删除的元素仅有左孩子或者仅有右孩子时，直接让其孩子顶替它即可。比如要删除元素 35，只需要用 41 顶替它即可。
3. 删除的元素既有左孩子又有右孩子，这时删除它相对复杂。一种好的方式是找到它的前驱或者后继来代替它。比如要删除元素 9，就用 6 或者 13 代替它即可。

问题

一棵普通的二叉排序树也会出现不平衡问题，如果插入的数据都在树的一侧，就会使得树的深度迅速增大，每次二分查找可以排除的数据很少，从而查询速度严重下降，比如下方这棵树：

要查找值为 2 的元素，使用二分法和使用链表速度差不多。为了解决这种问题，就需要在元素插入时即进行修正，后续介绍的AVL树和红黑树就是两种不同的解决方案。