# 红黑树
红黑树是平衡二叉树的一种实现方式, 相比AVL树要求的结点的高度差不能大于1, 红黑树更加宽松一些, 也因此对于红黑二叉树的平衡次数和旋转次数会更少, 因此应用的更加广泛.
# 红黑树的平衡的五条特性
当满足一下的条件时, 说明这是一颗平衡的红黑树.
- 任意一个结点的颜色只能是黑色或者红色
- 根节点是黑色
- 任何为NULL的结点视为黑色
- 红色的结点不会相邻, 也就是说红色结点的孩子节点不能是红色
- 从根节点出发,达到任意一个叶子结点的路径上, 黑色节点数量必须相同.
# 添加新节点时对应的4种情况
两种简单情况:
- 根节点为null, 则添加节点就是添加一个根节点,我们添加节点后,将节点的颜色设置为黑色即可
- 父节点的颜色为黑色, 对于这种情况,我们添加节点后,不需要进行任何的平衡,因为父节点为黑色的结点添加节点不会影响平衡.(新添加节点的颜色为红色)
情况3: 父节点为红色,并且叔叔节点为红色.
情况4：父节点为红色,并且叔叔节点为黑色.
# 红红相邻情况导致失衡调整
在线的演示网站 (opens new window) 对于失衡情况, 我们有两种调整方式.
- 变色
- 旋转
# 情况3的调整
步骤
以该图为例子:
因为插入节点后, 新节点与父节点与红色结点相邻, 因此出现红红相邻的情况.
最先想到的调整方式就是将父节点变成黑色, 但是这时就会导致到达新节点的路径上黑色节点数量多于 叔叔路径中叶子节点的路径上的黑色节点, 违反了特性5.
此时我们想到将叔叔节点也变为黑色, 但是此时又会导致祖先结点的父节点(5)的另一个分支中的黑色节点数量小于左边分支, 因此我们又想将祖先结点变为红色,此时 如果祖先节点的父节点不是红色,那么此时的红黑树就平衡了,否则还需要处理红红相邻的情况.
总结 父节点为红色, 叔叔节点为红色, 此时将父节点和叔叔节点都变为黑色, 然后将祖先结点变为红色, 判断祖先结点与它的父节点是否产生了红红相邻的情况.如果是,则对祖先节点进行调整.
# 情况4的调整
父节点为红色, 叔叔节点为黑色, 我们有4种调整方案
- 父节点是左孩子, 新插入的结点为左孩子, 此时是LL不平衡
- 父节点是左孩子, 新插入的结点为右孩子, 此时是LR不平衡
- 父节点是右孩子, 新插入的结点为左孩子, 此时是RL不平衡.
- 父节点是右孩子, 新插入的结点为右孩子, 此时是RR不平衡.
LL的不平衡, 我们需要对父节点进行一次右旋.
对父节点进行一次右旋, 然后将父节点变为黑色,将祖父节点变为红色.
LR的不平衡, 我们需要进行父节点一次左旋,新的父节点再一次右旋
先对父节点2进行一次左旋, 将2旋转成3的左孩子, 3变成新的父节点,此时 又是红红相邻,但此时是LL的情况, 进行一次右旋.
右旋后, 父节点变为黑色, 祖父节点变为红色
RR的不平衡, 我们需要对父节点进行一次左旋.
对父节点进行一次左旋, 然后将父节点变为黑色,将祖父节点变为红色.
失衡:
调整后:
对于RL的不平衡,我们需要对父节点进行一次右旋,然后对新的右节点进行一次左旋.
调整前:
先对父节点进行一次右旋,然后出现了RR的情况, 然后我们对其进行一次左旋.
然后将祖父节点变为红色, 父亲节点变为黑色.
# 删除节点时,对应的情况
被删除节点是根节点. (case 1)
- 被删除节点没有孩子.
- 被删除节点只有一个孩子.
- 被删除节点有两个孩子.
被删除节点不是根节点.
- 被删除节点有两个孩子 (case 0)
- 被删除节点没有孩子
- 被删除节点是红色(直接删除,不影响平衡)
- 被删除节点是黑色(进行黑黑平衡)
- 被删除节点有一个孩子
- 被删除节点是红色(将孩子替换自己的位置, 并且将颜色设置为红色.)
- 被删除节点是黑色
- 如果该节点只有一个红色孩子,则将红色孩子替代自己的位置,并且将颜色设置为黑色
