<pre name="code" class="java">/*
* 红黑树
*/
public class RedBlackTree {
public static final RbTreeNode NIL = new RbTreeNode(RbColor.BLACK);
private RbTreeNode root = null;
public static void main(String[] args) {
RedBlackTree rbt = new RedBlackTree();
//测试插入 page 179 红黑树不唯一
rbt.insertRbTreeNode(new RbTreeNode(11,RbColor.BLACK));
rbt.insertRbTreeNode(new RbTreeNode(2,RbColor.RED));
rbt.insertRbTreeNode(new RbTreeNode(1,RbColor.BLACK));
rbt.insertRbTreeNode(new RbTreeNode(7,RbColor.BLACK));
rbt.insertRbTreeNode(new RbTreeNode(5,RbColor.RED));
rbt.insertRbTreeNode(new RbTreeNode(8,RbColor.RED));
rbt.insertRbTreeNode(new RbTreeNode(14,RbColor.BLACK));
rbt.insertRbTreeNode(new RbTreeNode(15,RbColor.RED));
rbt.printTree();
rbt.deleteRbTreeNode(rbt.searchRbTreeNode(rbt.root, 7));
rbt.printTree();
System.out.println(rbt.searchMaximum(rbt.root).key);
}
public RedBlackTree() {
this.root = NIL;
}
//中序遍历二叉树
private void traverseTree(RbTreeNode x) {
if(x != NIL) {
traverseTree(x.left);
System.out.print(x.key + " " + x.color + " ");
traverseTree(x.right);
}
}
private void printTree() {
System.out.println("root:"+root.key+" "+root.color);
traverseTree(root);
System.out.println();
}
//查找某一子节点
private RbTreeNode searchRbTreeNode(RbTreeNode x,int key) {
while(x != NIL && key != x.key) {
if(key < x.key) {
x = x.left;
} else {
x = x.right;
}
}
return x;
}
//插入某一子节点
private void insertRbTreeNode(RbTreeNode z) {
RbTreeNode y = NIL;
RbTreeNode x = root;
while(x != NIL) {
y = x;
if(z.key < x.key) {
x = x.left;
} else {
x = x.right;
}
}
z.parent = y;
if(y == NIL) {
root = z;
} else if(z.key < y.key) {
y.left = z;
} else {
y.right = z;
}
z.left = NIL;
z.right = NIL;
z.color = RbColor.RED;
rbInsertFixUp(z); //插入修正
}
//插入修正
private void rbInsertFixUp(RbTreeNode z) {
RbTreeNode y = null;
while(z.parent.color == RbColor.RED) { //当z的父节点是黑色时，不需要矫正
if(z.parent == z.parent.parent.left) { //左分支情况
y = z.parent.parent.right; //根据叔节点分情况
if(y.color == RbColor.RED) {
z.parent.color = RbColor.BLACK;
y.color = RbColor.BLACK;
z.parent.parent.color = RbColor.RED;
z = z.parent.parent;
} else {
if(z == z.parent.right) {
z = z.parent;
leftRotate(z);
}
z.parent.color = RbColor.BLACK;
z.parent.parent.color = RbColor.RED;
rightRotate(z.parent.parent);
}
} else {
y = z.parent.parent.left; //根据叔节点分情况
if(y.color == RbColor.RED) {
z.parent.color = RbColor.BLACK;
y.color = RbColor.BLACK;
z.parent.parent.color = RbColor.RED;
z = z.parent.parent;
} else {
if(z == z.parent.left) {
z = z.parent;
rightRotate(z);
}
z.parent.color = RbColor.BLACK;
z.parent.parent.color = RbColor.RED;
leftRotate(z.parent.parent);
}
}
}
root.color = RbColor.BLACK;
}
//删除某一子节点
private void deleteRbTreeNode(RbTreeNode z) {
RbTreeNode y = z;
RbTreeNode x = NIL;
RbColor yOriginalColor = y.color;
if(z.left == NIL) {
x = z.right;
rbTransplant(z,z.right);
} else if(z.right == NIL) {
x = z.left;
rbTransplant(z,z.left);
} else {
y = searchMinimum(z.right);
yOriginalColor = y.color;
x = y.right;
if(y.parent == z) {
x.parent = y;
} else {
rbTransplant(y,y.right);
y.right = z.right;
z.right.parent = y;
}
rbTransplant(z,y);
y.left = z.left;
z.left.parent = y;
y.color = z.color;
}
if(yOriginalColor == RbColor.BLACK) {
rbDeleteFixUp(x);
}
}
private void rbDeleteFixUp(RbTreeNode x) {
//x总是指向一个具有双重黑色的非根节点
RbTreeNode w = NIL;
while(x != root && x.color == RbColor.BLACK) {
if(x == x.parent.left) {
w = x.parent.right; //w指向兄节点
if(w.color == RbColor.RED) {
w.color = RbColor.BLACK; //case 1
x.parent.color = RbColor.RED; //case 1
leftRotate(x.parent); //case 1
w = x.parent.right; //case 1
}
if(w.left.color == RbColor.BLACK
&& w.right.color == RbColor.BLACK) {
w.color = RbColor.BLACK; //case 2
x = x.parent; //case 2
}
else {
if(w.right.color == RbColor.BLACK) {
w.left.color = RbColor.BLACK; //case 3
w.color = RbColor.RED; //case 3
rightRotate(w); //case 3
w = x.parent.right; //case 3
}
w.color = x.parent.color; //case 4
x.parent.color = RbColor.BLACK; //case 4
w.right.color = RbColor.BLACK; //case 4
leftRotate(x.parent); //case 4
x = root; //case 4
}
} else {
w = x.parent.left; //w指向兄节点
if(w.color == RbColor.RED) {
w.color = RbColor.BLACK; //case 1
x.parent.color = RbColor.RED; //case 1
rightRotate(x.parent); //case 1
w = x.parent.left; //case 1
}
if(w.right.color == RbColor.BLACK
&& w.left.color == RbColor.BLACK) {
w.color = RbColor.BLACK; //case 2
x = x.parent; //case 2
}
else {
if(w.left.color == RbColor.BLACK) {
w.right.color = RbColor.BLACK; //case 3
w.color = RbColor.RED; //case 3
leftRotate(w); //case 3
w = x.parent.left; //case 3
}
w.color = x.parent.color;
x.parent.color = RbColor.BLACK;
w.left.color = RbColor.BLACK;
rightRotate(x.parent);
x = root;
}
}
}
}
private void rbTransplant(RbTreeNode u,RbTreeNode v) {
if(u.parent == NIL) {
root = v;
} else if(u == u.parent.left) {
u.parent.left = v;
} else {
u.parent.right = v;
}
v.parent = u.parent;
}
//获取最小键值节点
private RbTreeNode searchMinimum(RbTreeNode x) {
while(x.left != NIL) {
x = x.left;
}
return x;
}
//获取最大键值节点
private RbTreeNode searchMaximum(RbTreeNode x) {
while(x.right != NIL) {
x = x.right;
}
return x;
}
//左旋
private void leftRotate(RbTreeNode x) {
RbTreeNode y = x.right;
x.right = y.left;
if(x.right != NIL) {
y.left.parent = x;
}
y.parent = x.parent;
if(x.parent == NIL) { //如果是根节点
root = y;
} else if(x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
//右旋
private void rightRotate(RbTreeNode y) {
RbTreeNode x = y.left;
y.left = x.right;
if(x.right != NIL) {
x.right.parent = y;
}
x.parent = y.parent;
if(y.parent == NIL) {
root = x;
} else if(y == y.parent.left) {
y.parent.left = x;
} else {
y.parent.right = x;
}
x.right = y;
y.parent = x;
}
//红黑树节点类
private static class RbTreeNode {
RbTreeNode left = null;
RbTreeNode right = null;
RbTreeNode parent = null;
RbColor color = RbColor.RED;
int key = 0;
public RbTreeNode(int key,RbColor color) {
this.key = key;
this.color = color;
}
public RbTreeNode(RbColor color) {
this.color = color;
}
}
private enum RbColor {
RED,BLACK
}
}原文：http://blog.csdn.net/q389281541/article/details/44900123