实现有序集的数据结构就是红黑树，这也是 JDK 中 TreeMap 中 Tree 的意思。如果你有一定的 Java 开发经验，相信你一定会知道相比于 HashMap，基于红黑树的 TreeMap 的一个显著特点就是其维护的键值对是有序排列的。

二分查找树

因为红黑树就是一种近似平衡的二分查找树实现。我们知道，在一个线性的链表里，如果要查找某个特定节点，唯一能做的事情就是从头到尾遍历节点，这带来了平均为 O(N) 的查找时间复杂度。但是如果数据存储在有序的二分查找树上，情况就大有不同。二分查找树的二分是指什么呢？举个非常简单的例子，你在便利店购物，有一个商品忘记扫码触发门禁警报，怎么从一堆商品里迅速定位呢？一个一个扫显然很慢，聪明的方法是将商品先分为两堆过门禁，找到触发的那堆再二分，继续下去，就能迅速找到啦。本质就在于二分每次可以排除掉一半的查询范围。二分查找也是非常常见的算法。

具体来说，二分查找树一种可以用来实现二分搜索的数据结构。具体来说，我们在一棵普通的二叉树上放置需要存储的符号表，并保证所有节点和其左右子节点满足这样的关系：每个节点的左节点要不为空，要不为比当前节点小的元素（符号）；每个节点的右节点要不为空，要不为比当前节点大的元素（符号）。

在这样的约束下，我们的查找只需要从根节点出发，比较当前节点和目标元素之间的大小，要么往左走，要么往右走；这是因为比当前节点大的元素一定在当前节点右边，反之则在当前节点左边，所以我们每次比较总可以排除左右子树中的一颗。

反复进行这样的搜索过程，直到当前节点已经是叶子结点，或者当前结点和目标元素相等为止。需要比较的次数最多为树的最大高度 h，因此整个搜索过程的时间复杂度就是 O(h)，显然，O(h) 在大部分时候是一个比 O(n) 小得多的数。

平衡二分查找树