红黑树

红黑树（Red Black Tree） 是一种自平衡二叉查找树，为了解决二叉查找树多次插入新结点导致的不平衡问题。

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

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

这些规则是保证了红黑树从根到叶子的最长路径不会超过最短路径的2倍。

下图中这棵树，就是一颗典型的红黑树：

当插入或者删除结点的时候，红黑树的规则有可能被打破。此时需要做出一些调整，从而继续维持红黑树的规则。

红黑树的插入

红黑树的插入首先按照二叉查找树插入结点，之依据一定规则进行调整。

链接：红黑树的插入操作

红黑树的删除

红黑树的删除首先按照二叉查找树删除结点，之后依据一定规则进行调整。

链接：二叉查找树的删除操作

链接：红黑树的删除操作