是一棵二叉搜索树，是一个2-3树（黑色表示3结点，红色表示2结点）在每个结点上增加了一个存储位来表示结点的颜色。通过对任何一条从根到结点叶子的简单路径上各个结点的颜色来进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。每次插入都是红结点。
1.每个节点或是红色的，或是黑色的
2.根节点是黑色的
3.每个叶结点是黑色的
4.如果一个节点是红色的，则它的两个子节点是黑色的
5.对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色结点。
————————————————————插入————————————————————
情况1：插入关注节点a的叔节点d是红色的
（1）将b和d都着为黑色
（2）将c着为红色
（3）c作为新关注节点a来继续。
情况2：插入结点a的叔节点是是黑色，且a是一个右孩子
（1）关注节点变成节点 a 的父节点 b
（2）围绕新的关注节点b 左旋
情况3：插入节点a的叔节点是黑色，且a是一个左孩子
（1）围绕关注节点 a 的祖父节点 c 右旋；
（2）将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。
————————————————————删除————————————————————
1.针对删除结点初步调整
使每个节点，从该结点到达其可达叶子节点的所有路径，包含相同数目的黑色结点。
如果一个节点既可以是红色，也可以是黑色，在画图的时候，我会用一半红色一半黑色来表示。
如果一个节点是“红 - 黑”或者“黑 - 黑”，我会用左上角的一个小黑点来表示额外的黑色。
情况1：如果删除结点是a，它只有一个子节点b
（1）删除结点a，并把结点b替换到结点a的位置
（2）结点a只能是黑色，结点b只能是红色，其他情况均不符合红黑树的定义。这种情况下，我们把节点 b 改为黑色；
情况2：如果要删除的结点a有两个非空子节点，并且它的后继节点就是结点的右子节点c
（1）如果节点 a 的后继节点就是右子节点 c，那右子节点 c 肯定没有左子树。我们把节点 a 删除，并且将节点 c 替换到节点 a 的位置。这一部分操作跟普通的二叉查找树的删除操作无异；
（2）然后把节点 c 的颜色设置为跟节点 a 相同的颜色；
（3）如果节点 c 是黑色，为了不违反红黑树的最后一条定义，我们给节点 c 的右子节点 d 多加一个黑色，这个时候节点 d 就成了“红 - 黑”或者“黑 - 黑”；
（4）这个时候，关注节点变成了节点 d，第二步的调整操作就会针对关注节点来做。
情况3：如果要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是右子节点
（1）找到后继节点 d，并将它删除，删除后继节点 d 的过程参照 CASE 1；
（2）将节点 a 替换成后继节点 d；
（3）把节点 d 的颜色设置为跟节点 a 相同的颜色；
（4）如果节点 d 是黑色，为了不违反红黑树的最后一条定义，我们给节点 d 的右子节点 c 多加一个黑色，这个时候节点 c 就成了“红 - 黑”或者“黑 - 黑”；
（5）这个时候，关注节点变成了节点 c，第二步的调整操作就会针对关注节点来做。
2.针对关注节点进行二次调整
为了让红黑树找那个不存在相邻的红色结点
情况1：如果关注节点是 a，它的兄弟节点 c 是红色的
（1）围绕关注节点 a 的父节点 b 左旋；
（2）关注节点 a 的父节点 b 和祖父节点 c 交换颜色；
（3）关注节点不变；
（4）继续从四种情况中选择适合的规则来调整。
情况2：如果关注节点是 a，它的兄弟节点 c 是黑色的，并且节点 c 的左右子节点 d、e 都是黑色的
（1）将关注节点 a 的兄弟节点 c 的颜色变成红色；
（2）从关注节点 a 中去掉一个黑色，这个时候节点 a 就是单纯的红色或者黑色；
（3）给关注节点 a 的父节点 b 添加一个黑色，这个时候节点 b 就变成了“红 - 黑”或者“黑 - 黑”；
（4）关注节点从 a 变成其父节点 b；
（5）继续从四种情况中选择符合的规则来调整。
情况3：如果关注节点是 a，它的兄弟节点 c 是黑色，c 的左子节点 d 是红色，c 的右子节点 e 是黑色
(1)围绕关注节点 a 的兄弟节点 c 右旋；
(2)节点 c 和节点 d 交换颜色；
(3)关注节点不变；
(4)跳转到 CASE 4，继续调整。
情况4：如果关注节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色的
(1)围绕关注节点 a 的父节点 b 左旋；
(2)将关注节点 a 的兄弟节点 c 的颜色，跟关注节点 a 的父节点 b 设置成相同的颜色；
(3)将关注节点 a 的父节点 b 的颜色设置为黑色；
(4)从关注节点 a 中去掉一个黑色，节点 a 就变成了单纯的红色或者黑色；
(5)将关注节点 a 的叔叔节点 e 设置为黑色；
(6)调整结束。
网友评论