Arithmetic-红黑树
2018-04-01
Arithmetic
- 红黑树结构剖析
- 参考文档:
红黑树数据结构剖析;算法导论 - 基本概念
- 数据结构设计
- 作为红黑树节点, 其基本属性有: 节点的颜色/左子节点指针/右子节点指针/父节点指针/节点值
- 红黑树的插入操作
- 如果插入第一个节点, 我们直接用根节点记录它, 并设置为黑色
- 如果不是, 则默认插入的节点颜色为红色, 因为插入黑色的节点会破坏根路径上的节点总数
- 插入后调整: 在插入后不满足上述5条规则时进行调整
- 原因: 插入节点和父节点的颜色都是红色, 发生冲突
- 原因: 插入节点和父节点的颜色都是红色, 发生冲突
- 插入问题分类
- 叔父节点为黑色
- 解决思路: 将多出的节点移到叔父节点那一方
- 分类
- 外侧插入
- n是p的左子节点, p是g的左子节点
- n是p的右子节点, p是g的右子节点
- n是p的左子节点, p是g的左子节点
- 内侧插入
- n是p的左子节点, p是g的右子节点
- n是p的右子节点, p是g的左子节点
- n是p的左子节点, p是g的右子节点
- 外侧插入
- 叔父节点是红色
- 解决思路: 将p/u节点变成黑色, 此时路径上黑色数量增加1, 将g变为红色, 再通过操作解决g和gp的冲突
- 操作: 从当前插入点n向根节点root回溯两次
- 第一次回溯处理
所有拥有两个红色节点的节点, 并按照上图的方式进行处理, 同时暂时忽略gp和p的颜色冲突。如果根节点的两个子节点也是这种情况，则在颜色交换完毕后重新将根节点设置为黑色。 - 第二次回溯专门处理连续的红色节点冲突。由于经过第一遍的处理，在新插入点n的路径上一定不存在同为红色的兄弟节点了。而仍出现gp和p的红色冲突时，gp的兄弟节点（gu）可以断定为黑色，这样就
回归前边讨论的叔父节点为黑色时的情况处理。
- 第一次回溯处理
- 叔父节点为黑色
- 红黑树的删除操作
- 如只有唯一子节点或没有子节点, 则该节点删除, 并将其子节点代替自身位置
- 如有两个子节点, 则从右子树中选择最小值节点y(此节点无左节点, 因为其最小), 将y的值拷贝到待删除节点yold(yold颜色不变), 从而将问题转化成独立后继的问题(即只有一个右子节点)
- 考虑被删除节点y的颜色
- 为红, 删除后不影响平衡性
- 为黑, 该路径上的黑节点少1, 需进行调整
- 考虑n的颜色
- 为红, 将n变为黑, 则恢复平衡性
- 为黑, 按下面步骤考虑(设p为n的父节点, w为n的兄弟节点)
- 解决思路: 从兄弟节点借调黑色节点过来, 兄弟节点将红色节点变成黑色以保持平衡性
- w为红色, w的父/子节点必为黑色, 此时进行如下操作: 将w和p交换颜色, 并将w左旋, 这样讲问题转换成了
步骤2能解决的问题 - w为黑色, 本步骤包括但不限于步骤1, 因为p可能为红. 此时考虑w的子节点:
- w的子节点x/y全为黑色, 此时将w的颜色设置为红, 并将p设置为新的n节点, 重新开始进入
考虑n的颜色的步骤 - w的子节点x/y为红/黑, 此时将x设置为黑色, w设置为红色, 并以x为轴右旋, 最后将n的新兄弟设置为w, 这样就把问题属于下一种情况: w的右子节点为红, 左节点为黑
- w的右子节点为红, 包含上一种情况. 这时将w的右子节点y设置为黑色，并交换w与父节点p的颜色（w原为黑色，p颜色可黑可红），再以w为旋转轴左旋转，红黑树调整算法结束。
- w的子节点x/y全为黑色, 此时将w的颜色设置为红, 并将p设置为新的n节点, 重新开始进入
- 考虑n的颜色
- 考虑被删除节点y的颜色
- 删除总结:
- 参考文档: