二叉查找树（Binary Search Tree）

二叉查找树（BST）的特性

1. 左子树上面所有节点的值均小于或等于它的根节点的值
2. 右子树上所有节点的值均大于或等于它的根节点的值。
3. 左右子树分别为二叉排序树

下图中这棵树，就是一颗典型的二叉查找树： 那这样的结构有什么好处呢？我们试着查找一下值为10的节点。

1. 查看根节点为9：
2. 由于10>9，因此查看右子节点13
3. 由于10<13，因此查看左子节点11
4. 由于10<11，因此查看左子节点，发现10正是要查找的节点。

二叉查找树，查找所需的最大次数等同于二叉查找树的高度。 在插入节点时，也是利用类似的方法，通过一层层比较大小，找到新节点适合的插入位置。

缺点： 缺点提现在插入新节点的时候。 例子： 假设初始的二叉查找树只有三个节点，根节点为9，左子节点值为8，右子节点为12，如图 接下来我们一次插入如下五个节点：7，6，5，4，3。依照二叉查找树的特性，结果会变成什么样呢？

为了解决二叉查找树多次插入新节点而导致的不平衡，红黑树应用而生。

红黑树是一种自平衡的二叉查找树。除了符合二叉查找树的基本特性外，还有下列附加特性。

1. 节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶子节点都是黑色的空节点（NIL节点）。
4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（简称黑高）。

正因为这些规则，才保证了红黑树的自平衡。 红黑树从根到叶子的最长路径不会超过最短路径的2倍 当插入或删除节点的时候，红黑树的规则有可能被打破。这个时候需要做一些调整，来维持我们的规则。