系统使用细节

有序表在 java 中就是 TreeMap。c++中就是 map。

1. 其添加删除的时间复杂度为 $O(lo{g}^N)$ ，相较于哈希表略高；
2. 与哈希表类似，其内部的 key-value 也有相同的存储方式，按值或者按照引用传递；
3. 可以查询最小最大的 key，附近的 key，这些是哈希表没有的功能；
4. 对于非基础类型已经其包装类，需要自己定制比较器，否则会报错；
5. 哈希表适合单点查询，而有序表适合于查询多个数据，并且保证这些数据是有序。

二叉搜索树 - BST

二叉搜索树就是二叉排序树。各种复杂的具体有序表都是 BST 的优化，所以，了解 BST 是必要的。
有序表-BST

二叉搜索树的瓶颈

注意： 搜索二叉树不接受重复的数据。
当数据极端的时候，会导致搜索二叉树不平衡，从而极大的降低二叉搜索树的效率。
所以为了解决这个问题，平衡搜索二叉树就出现了。

平衡二叉树

不论是什么搜索二叉树，让其变得平衡的基本动作就是左旋和右旋，但是其使用的策略各不同，所以其平衡性也不一样。时间复杂度都是 $O(logN)$，没有差别。

我们进行旋转的基本目标有两个：

1. 让树的高度减小；
2. 让二叉树的中序遍历不变；

而让这颗二叉树变得平衡的操作就是耳熟能详的左旋和右旋。

• 左旋和右旋的时间复杂度都为 $O(1)$ ，只设计有限的几个节点的操作；
• 左旋和右旋不会破坏搜索树的性质，并且能够很大程序的减少二叉搜索树的高度，从而提高了搜索的高度。

旋转操作

左旋转

先指定某个头节点，在某个头节点左旋。某个节点左旋就是这个节点往左边倒下去，也就是右子树上来。

右旋转

以某个节点为头，该节点往右边倒，其左孩子的右孩子变为了这个节点的左孩子。

常见平衡搜索二叉树

Java JDK 中的有序表有诸多瓶颈，只能进行相当有限的操作。最致命的缺点就是不能保存重复值。所以，以下的一些有序表可以很大程度上的规避这个问题：

• AVL 树：有序表-AVL树；
• sb 树：有序表-sb 树；
• 跳表：有序表-跳表；
  在实际使用中，跳表和 sb 树是我们最常用的有序表结构。