江苏龙网

  1. 主页 > 生活百科 > >

红黑树算法( 三 )

红黑树算法


定义5：给定任意节点，从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点（不会被破坏，因为插入节点是红色的）
 
上面总结出当每次插入至多只有一条定义被破坏，要么是定义2（根节点必须是黑色但插入的是红色），要么是定义4（如果它父节点是红色但插入的子节点默认也是红色），他们不可能同时被破坏，因为如果新插入节点是根，那么根本还没有子节点，根本不会出现定义4的情况；如果不是根，那就证明存在根，根肯定已经是黑色的，虽然在进过多次调整后根节点也可能会被破坏，所以简单粗暴的办法就是每次插入最后那行代码把根节点着为黑色即可 。下面给出调整红黑树的代码，紧接着分析定义4被破坏的3种情况相应的调整规则 。
/** * 调整红黑树结构，保证不破坏红黑树定义 * * @param newNode 新插入节点 */private void updateRedBlackTree(Node newNode) {//如果新增节点的父节点颜色是红色，这种情况一定破坏了红黑树定义//定义4：如果一个节点是红色的，那么它的两个子节点都是黑色的while (newNode.parent.color == RED) {//如果新增节点的父节点是祖父节点的左孩子if (newNode.parent == newNode.parent.parent.left) {//新增节点的叔节点Node uncleNode = newNode.parent.parent.right;//情况1：叔节点是红色if (uncleNode.color == RED) {this.setColor(newNode.parent, BLACK);this.setColor(uncleNode, BLACK);this.setColor(newNode.parent.parent, RED);newNode = newNode.parent.parent;//情况2：叔节点是黑色且新插入节是右孩子} else if (uncleNode.color == BLACK && newNode == newNode.parent.right) {newNode = newNode.parent;this.leftRotate(newNode);}//情况3：叔节点是黑色且新插入节是左孩子this.setColor(newNode.parent, BLACK);this.setColor(newNode.parent.parent, RED);this.rightRotate(newNode.parent.parent);//如果新增节点的父节点是祖父节点的右孩子，交换位置后继续按左孩子逻辑调整} else if (newNode.parent == newNode.parent.parent.right) {Node uncleNode = newNode.parent.parent.left;//情况1：叔节点是红色if (uncleNode.color == RED) {this.setColor(newNode.parent, BLACK);this.setColor(uncleNode, BLACK);this.setColor(newNode.parent.parent, RED);newNode = newNode.parent.parent;//情况2：叔节点是黑色且新插入节是右孩子} else if (uncleNode.color == BLACK && newNode == newNode.parent.left) {newNode = newNode.parent;this.rightRotate(newNode);}//情况3：叔节点是黑色且新插入节是左孩子this.setColor(newNode.parent, BLACK);this.setColor(newNode.parent.parent, RED);this.leftRotate(newNode.parent.parent);}}//简单粗暴总是将根节点设置为黑色this.rootNode.color = BLACK;}private void setColor(Node node, int color) {if (node != null) {node.color = color;}} 
情况1：新插入节点（newNode）的叔节点（uncleNode）是红色
 
此时情况如下图（下图省略了不关键的子树）
 

红黑树算法

文章插图
 
 
这种情况由于newNode的父节点和叔节点都是红色时发生，先将父节点变为黑色（修复被破坏的定义4），然后将祖父节点变为红色（变色父节点后导致定义5被破坏），最后将叔节点变为黑色（变色祖父节点后导致定义4再次被破坏），还没有结束，实际代码实现上，还需要将祖父节点指针赋值给newNode,循环检查直至根节点，因为我们改变了祖父节点的颜色，势必会破坏上面的结构 。
 
情况2：新插入节点（newNode）的叔节点是黑色的且newNode是一个右孩子
情况3：新插入节点（newNode）的叔节点是黑色的且newNode是一个左孩子
【红黑树算法】情况4：叔节点是黑色且新插入节点是左孩子
 
其它情况的分析思路留给读者自己根据代码配合注释和前面的讲解去分析，无非就是旋转和变色，这里就不再过多地做规则翻译 。




推荐阅读


上一篇：迪拜著名的建筑 迪拜十大最疯狂的建筑

下一篇：日本本州发生6.2级地震 日本5.1级地震