· 红黑树特性

红黑树是自平衡二叉搜索树的一种，每个节点具有一个属性表示该节点是红色还是黑色，红黑树具有3个特性或者规则限制：

1. 根节点和nil节点是黑色
2. 红色节点的两个子节点是黑色（即红色节点不能连续出现，但是黑节点可以连续出现，黑节点的子节点可以是黑节点）
3. 从任意一个节点到每个叶子节点的所有路径都包含相同个数的黑色节点（例如下图从13到任意一个叶子节点都只经过了2个黑色节点）。

正是由于这3点特性或者说限制才保证了红黑树的自平衡，使得从根到叶子的最长路径不会超过最短路径的2倍。

红黑树如下图所示：

当插入和删除节点的时候，红黑树的规则可能被打破，此时要做出调整使其继续符合这3个特性。

调整方式有3种：变色（红变黑或者黑变红）、左旋和右旋（介绍AVL时已经介绍过，不再赘述）。

下面将对插入节点这个动作介绍其调整过程，需要注意的是，新插入的节点一开始是红色节点。

·插入时的调整

需要分5种情况。

情况1：插入的节点（A）是根节点，没有父节点。

此时只需把插入的节点变为黑色即可，这样做是因为根节点必须是黑色。

情况2：新结点（B）的父结点是黑色。此时无需调整，因为从A到左支和到右支叶子节点所经过的黑色节点个数没变，因此A到左支和右支叶子节点经过的黑节点依旧相等。

情况3：新结点（D）的父结点和叔叔结点都是红色。

此时违背规则2。但我们不能直接将D变成黑色，否则A左支的黑色节点会比右支的黑色节点多1个，违背规则3。

正确做法：将B变黑色（违背规则3），再将A变红色（违背规则2，AC是连续红节点），再将C变黑色（此时满足3个规则）。

情况4：新结点（D）的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的左孩子，父结点（B）是祖父结点（A）的左孩子。

此时需要对A右旋，使得结点B成为祖父结点，结点A成为结点B的右孩子，让结点B变为黑色，结点A变为红色。这样做还是为了维持从该子树自己的根节点到其左右子树的叶子节点所经过的黑节点个数相等。

情况5：新结点（D）的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的右孩子，父结点（B）是祖父结点的左孩子。

把B左旋变成情况4，再按情况4处理即可。

其实我们需要记住插入节点后属于上面5种情况中的那种以及每种情况的调整方法，但不用死记，我们只需要记住一个调整宗旨就行：调整后，从根节点到左右分支的任一叶子节点所经历的黑节点都要相同，不违背该规则的调整方法才是正确的调整方法。这样就很容易理解和记住每种情况的调整方法。

删除一个节点的调整情况由于过于变态复杂，因此不在这里展开，有兴趣的同学可以看看 《漫画算法2》一书对红黑树的介绍，或者看看公众号“程序员小灰”的这篇介绍红黑树的文章：漫画：什么是红黑树？（整合版）

·对比AVL树和红黑树

AVL树是严格平衡的BST，要求每个节点的左右子树高度不超过1，而红黑树要求任何一条路径不会超过最短路径的2倍，因此红黑树对平衡的要求更宽松，所以AVL树的查找效率高于红黑树，插入和删除的效率低于红黑树。频繁查找用AVL，频繁插入和删除用红黑树。

更多内容请关注微信公众号