2014-06-29

[原]红黑树的java实现

红黑树的原理以及算法见文章：http://blog.csdn.net/v_JULY_v/article/details/6105630

链接文章中已经把原理讲得很清楚了，本文只讨论java来实现红黑树，主要是链接文章中的算法实现，或者说是算法导论中的算法实现吧

红黑树的节点定义:


package org.algorithm.RedBlackTree;

/**
* Created with IntelliJ IDEA.
* User: qarkly
* Date: 14-6-8
* Time: 下午11:16
* To change this template use File | Settings | File Templates.
*/
public class RedBlackNode {
public static final byte RED = 0x00;
public static final byte BLACK = 0x01;
public static RedBlackNode NILL = new RedBlackNode(BLACK);

RedBlackNode parent;
RedBlackNode left;
RedBlackNode right;
Comparable element;
byte color;

public RedBlackNode(RedBlackNode left,RedBlackNode right,Comparable element){
this.left = left;
this.right = right;
this.element = element;
color = RED;
}

public RedBlackNode(byte color){
this.color = color;
}

public RedBlackNode(Comparable element,byte color){
this.color = color;
this.element = element;
this.left = NILL;
this.right = NILL;
}

}

左旋操作实现：

 /**
* 左旋操作
* @param node
*/
private void leftRotate(RedBlackNode node){
if(node == null || node == RedBlackNode.NILL)
return;
RedBlackNode pNode = node.right;
node.right = pNode.left;
pNode.left.parent = node;
pNode.parent = node.parent;
if(node.parent == RedBlackNode.NILL){
root = pNode;
}else if(node == node.parent.left){
node.parent.left = pNode;
}else {
node.parent.right = pNode;
}
pNode.left = node;
node.parent = pNode;

}

红黑树的插入实现，文章的BR_INSERT（T ，z）：

 private void insert(RedBlackNode node){
RedBlackNode preNode = RedBlackNode.NILL;
RedBlackNode curNode = root;
while (curNode != RedBlackNode.NILL){
preNode = curNode;
if(node.element.compareTo(curNode.element) < 0){
curNode = curNode.left;
}else if(node.element.compareTo(curNode.element) >0){
curNode = curNode.right;
}else{
return;
}
}

node.parent = preNode;
if(preNode == RedBlackNode.NILL){
root = node;
}else if(node.element.compareTo(preNode.element) < 0){
preNode.left = node;
}else{
preNode.right = node;
}
node.left = node.right = RedBlackNode.NILL;
node.color = RedBlackNode.RED;
BrInsertFixup(node);

}

插入修复算法RB-INSERT-FIXUP现实：

 private void BrInsertFixup(RedBlackNode node){
RedBlackNode pNode;
while (node.parent.color == RedBlackNode.RED){
if(node.parent == node.parent.parent.left){
pNode = node.parent.parent.right;
if(pNode.color == RedBlackNode.RED){
node.parent.color = RedBlackNode.BLACK;
pNode.color = RedBlackNode.BLACK;
node.parent.parent.color = RedBlackNode.RED;
node = node.parent.parent;
}else {
if (node == node.parent.right){
node = node.parent;
leftRotate(node);
}
node.parent.color = RedBlackNode.BLACK;
node.parent.parent.color = RedBlackNode.RED;
rightRotate(node.parent.parent);
// node = node.parent;
}
}else{
//镜像情况处理
pNode = node.parent.parent.left;
if(pNode.color == RedBlackNode.RED){
node.parent.color = RedBlackNode.BLACK;
pNode.color = RedBlackNode.BLACK;
node.parent.parent.color = RedBlackNode.RED;
node = node.parent.parent;
}else {
if(node == node.parent.left){
node = node.parent;
rightRotate(node);
}
node.parent.color = RedBlackNode.BLACK;
node.parent.parent.color = RedBlackNode.RED;
leftRotate(node.parent.parent);
// node = node.parent;
}
}
}
root.color = RedBlackNode.BLACK;

}

红黑树的删除实现RB-DELETE(T, z)

 private RedBlackNode delete(RedBlackNode node){
if(node == null || node == RedBlackNode.NILL){
return RedBlackNode.NILL;
}

RedBlackNode pNode;

if (node.left == RedBlackNode.NILL || node.right == RedBlackNode.NILL){
pNode = node;
}else {
pNode = findSuccessor(node);
}

RedBlackNode nNode;
if(pNode.left != RedBlackNode.NILL){
nNode = pNode.left;
}else {
nNode = pNode.right;
}

nNode.parent = pNode.parent;
if(pNode.parent == RedBlackNode.NILL){
root = nNode;
}else{
if(pNode == pNode.parent.left){
pNode.parent.left = nNode;
}else{
pNode.parent.right = nNode;
}
}

if(pNode != node){
node.element = pNode.element;
}

if(pNode.color == RedBlackNode.BLACK ){
BrDeleteFixup(nNode);
}

return pNode;
}

删除后的修复和保持操作RB-DELETE-FIXUP(T, x)

 private void BrDeleteFixup(RedBlackNode node){
if(node == null ){
return;
}
while (node != root && node.color == RedBlackNode.BLACK){
if(node == node.parent.left){
RedBlackNode bNode = node.parent.right;
if(bNode.color == RedBlackNode.RED){
bNode.color = RedBlackNode.BLACK;
node.parent.color = RedBlackNode.RED;
leftRotate(node.parent);
bNode = node.parent.right;
}
if(bNode.left.color == RedBlackNode.BLACK && bNode.right.color == RedBlackNode.BLACK){
bNode.color = RedBlackNode.RED;
node = node.parent;
continue;
}else if(bNode.right.color == RedBlackNode.BLACK){
bNode.left.color = RedBlackNode.BLACK;
bNode.color = RedBlackNode.RED;
rightRotate(bNode);
bNode = node.parent.left;
}
bNode.color = node.parent.color;
node.parent.color = RedBlackNode.BLACK;
bNode.right.color = RedBlackNode.BLACK;
leftRotate(node.parent);
node = root;

}else{
RedBlackNode bNode = node.parent.left;
if(bNode.color == RedBlackNode.RED){
bNode.color = RedBlackNode.BLACK;
node.parent.color = RedBlackNode.RED;
rightRotate(node.parent);
bNode = node.parent.left;
}
if(bNode.left.color == RedBlackNode.BLACK && bNode.right.color == RedBlackNode.BLACK){
bNode.color = RedBlackNode.RED;
node = node.parent;
continue;
}else if(bNode.left.color == RedBlackNode.BLACK){
bNode.right.color = RedBlackNode.BLACK;
bNode.color = RedBlackNode.RED;
leftRotate(bNode);
bNode = node.parent.right;
}
bNode.color = node.parent.color;
node.parent.color = RedBlackNode.BLACK;
bNode.left.color = RedBlackNode.BLACK;
rightRotate(node.parent);
node = root;
}
}
node.color = RedBlackNode.BLACK;

}

文中代码排版貌似不太好看，附上github的完整代码

https://gist.github.com/qarkly/4db9abf5c231f12e45d7

<div>
    作者：qarkly112649 发表于2014/6/29 15:28:37 [原文链接](http://blog.csdn.net/qarkly112649/article/details/35787283)
</div>
<div>
阅读：986 评论：0 [查看评论](http://blog.csdn.net/qarkly112649/article/details/35787283#comments)
</div>