红黑树RBTree介绍与插入

AVL树：
树的高度：
1,2,3三个节点，如果普通的二叉树，则1没有左边，只有右边，右边高度为2（1-2,2-3）
当左右两个树的高度大于1的时候，AVL将会把树弄成平衡的，将1节点左旋，变成root=2，左边为1，右边为3仍然平衡

红黑树跟AVL树区别主要是红黑树只要求黑色节点平衡

定义

1. 每个节点要么是红的，要么是黑的
2. 根节点是黑的
3. 每个叶子节点是黑的（红黑树每个节点都有2个为空的不显示的叶子节点）
4. 如果一个节点是红的，那么他的两个儿子都是黑的
5. 对每个节点，从该节点到其子孙节点（这里说的是空的叶子节点）的所有路径上包含相同数目的黑节点（如从30走左边或者右边），从10到所有的叶子节点是3个黑色的

image.png

红黑树的插入

对于新节点必须直接给红色，否则会破坏第五条，即路径上不再包含相同黑节点。即使还不满足其他4条定义也必须这么做

1. 插入红色10，发现不满足条件2，因此将10变色为黑色
2. 插入红色20，比10大，放在右边，这时候再看是否满足定义，发现满足所有定义

image.png

3. 插入红色30，发现比10大，就找10的右边，发现比20大，就放在20的右边，发现这时候不满足条件4，但满足条件1,2,3,5

image.png

然后这时候10右边高度为2，大于左边高度0，大2个长度，因此开始将10左旋，并转换箭头方向，然后根据根节点必须是黑色的，因此将20变成黑色的，又因为第五条需保证左右两边黑色节点数相同，因此需要将10变色变成红色

image.png

4. 插入红色40

image.png

发现不再满足条件4，即红色节点的两个儿子必须都是黑色的，这里不需要旋转，考虑变色，20先变红，再变黑，将10，30变成黑色的，即可完成条件4

image.png

5. 插入红色25，5

image.png

总结：

• 如果新插入的节点的父节点是黑色的，则不需要调整，如插入25和5
• 如果新插入的节点的父节点是红色的，则需要调整
  （1）如果叔叔节点（祖父=爷爷的另一个儿子）是空的，这时候需要旋转 + 变色（参见步骤3）
  （2）叔叔节点存在，也是红色的，如插入50，父节点40红色，且50的叔叔节点25也是红色的，则只需要变色，即将25和40变色为黑色，把30变为红色。即将父节点 + 叔叔节点变为黑色，祖父节点变为红色。

image.png image.png

（3）叔叔节点存在，是黑色的（主要出现在底下的树调整完以后，影响了上面的树）

插入60，将35和50变为黑色，将祖父节点40变为红色

image.png image.png

调整完40为顶点的子树以后，继续向上去调整，因为把40换成了红色，因此继续模拟40是要插入的新节点，以20位顶点的子孙三代节点是不是平衡的。这时候发现，40节点的父亲是红色的，而叔叔节点10是黑色的。
这时候考虑的方式是：将20左旋，并将30本来的左节点25变为20的右节点

image.png

左旋完以后进行变色，将30变成黑色，将20变成红色

可以发现，第一种情况和第三种情况是一样的其实

image.png