彻底理解红黑树（一）之 二叉搜索树
彻底理解红黑树（二）之 插入
彻底理解红黑树（三）之 删除
前言
红黑树的插入情况并不算复杂，建议阅读本文后，自己动手试试，一来印证本文是否正确，二来自己尝试着摸一些规律，加深印象（文末也有一个简单的例子，已涉及全部情况）。
1. 红黑树的定义
红黑树在二叉搜索树的基础上，还要求有以下性质：
- 节点是红色或黑色；
- 根节点是黑色；
- 不能有连续的两个红色节点。
- 从任一节点到其每个叶子的简单路径都包含相同数目的黑色节点。
两棵简单的红黑树
性质3表明：红色节点的父、左子、右子只能是黑色节点，红色和红色不能直接连一起；而黑色无论红黑都可以连一起。（红色暴脾气互不相容，黑色和蔼可亲谁来都行）；
性质4表明：随便选一个节点，不论从怎么走，走到最后叶子节点时，其经过路径的黑色节点数量都是相等的（所谓完全黑平衡）。
而性质3和4共同决定了：最长路径的节点总数量不会超过最短路径的两倍。因为黑色节点数量要一样，红色不能连着来，从而路径全黑时最短，红黑交替时最长。比如4个黑色节点，最短：黑-黑-黑-黑（4），最长:黑-红-黑-红-黑-红-黑（7）。
因为路径长度/高度差有了一定限制，所以称红黑树是有一定平衡性的，不会出现极端倾斜的情况。
有一些红黑树定义（比如维基百科），还有一个性质：“叶子是黑色的NULL节点”：
带NULL节点的两棵黑红树
引入黑色的NULL节点并不会对之前的定义产生影响（各路径都增加一个黑色节点，黑色数量依然相等），其目的更多是为了简化平衡操作的情况，平衡时可以认为：null就是黑色节点。此时只需要考虑红和黑这两种情况就行，而不用考虑非红非黑的null。
2.旋转
说插入之前，先来看看旋转：
树的旋转
旋转后，原来“左小右大”的特点不会受到影响；影响的是左右子树的高度，右旋左子树高度+1，右子树-1；左旋右子树高度+1，左子树-1。
比如某棵树的左子树高度已经达到3，而右子树只有1，只需要右旋一下，左右子树高度都将调整为2。整棵树来看，高度就相当于降低了1（3 -> 2），这就是高度的“平衡”。
旋转前首先要确定旋转的节点（姑且叫支点）是哪个，这个非常重要。比如上图右旋前，要以X为支点才能转成右侧那样，如果选择Y作为支点，则要往下一层看了（X节点将以P的角色出现）。
另外留意一下b：
右旋前，b是挂在Y的右子，而右旋后，挂到了X的左子了；
左旋前，b是挂在X的左子，而左旋后，挂到了Y的右子了；
3. 插入平衡
开始之前，我们先约定一下名称：
红黑树属于二叉搜索树，插入动作也与二叉搜索树一致，只不过红黑树在插入之后，多了平衡动作（旋转与涂色）。
新插入的节点均为红色节点，因为红色不会影响路径上黑色节点的数量，保持性质4。如果父节点为黑色，就直接结束了；如果父节点为红色，则需要另外处理了。
以新插入的节点为当前平衡节点N，插入平衡大体上分为以下情形：
红黑树-插入平衡情形
情形1. N为根节点（父节点为NULL）
当前平衡节点N为根节点时，直接涂黑根节点即可。
N为根节点
情形2. 父黑
父节点为黑色时，无需其他操作，已然平衡。
父黑
情形3. 父红-叔红
父红-叔红时，将父/叔节(P/U)点涂黑，祖父节点(GP)涂红；而后以祖父节点(GP)作为新的平衡节点N，递归执行平衡操作。
i情形3 父红-叔红
情形4. 父红-叔黑
情形4.1 父节点和N同一边
情形4.1.1 父N同左
“父N同左”指的是：父节点为祖父节点的左子，N为父节点的左子。
此时以祖父节点(GP)为支点进行右旋；然后将P涂黑，将GP涂红。
情形4.1.1 父N同左
旋转后，P涂黑是因为要涂为原GP的黑色（往上兼容GP的父节点）；而GP涂红则是因为右旋后，经过U的路径的黑色节点数量+1，涂红进行数量平衡；下同。
情形4.1.2 父N同右
“父N同右”指的是：父节点是祖父节点的右子，N为父节点的右子。
此时以祖父节点(GP)为支点进行左旋；将P涂黑，将GP涂红。
情形4.1.2 父N同右
情形4.2 父节点和N不在同一边
情形4.2.1 父左N右
“父左N右”指的是：父节点是祖父节点的左子，N为父节点的右子。
此时，以父节点(P)进行左旋，旋转后，以P作为新的平衡节点N，转至 [情形4.1.1 父N同左] 处理。
父左N右
情形4.2.2 父右N左
“父右N左”指的是：父节点是祖父节点的右子，N为父节点的左子。
此时，以父节点(P)进行右旋，旋转后，以P作为新的平衡节点，此时再进行【情形4.1.2 父N同右】处理。
父右N左
4. 插入总结与实例
首先是先插入再说；插入后，以刚插入的节点作为当前平衡节点N，进行平衡操作。现在回头看插入平衡的这几种情形，其实并不复杂：
- N为根：涂黑完事；
- 父黑：啥事不用管；
- 父红叔红：父/叔涂黑，祖父涂红，然后把祖父当成新的平衡节点递归处理（我们下面平衡了，让他老人家和上面沟通吧）；
- 父红叔黑：父节点和新插入节点同一边的话，扭一下就完事了（同左右旋，同右左旋，顺便涂色）；不在同一边的话，先扭到同一边吧。
例：插入 10,20,15,30,5,8；
为了简化，图中没有画出null的黑色节点。
网友评论