首页 > 代码库 > 马程序员学习笔记——红黑树解析四
马程序员学习笔记——红黑树解析四
---------------------- ASP.Net+Unity开发、.Net培训、期待与您交流！ ----------------------
本篇是将上面三篇的理论知识转化成代码，java实现
首先，看一下算法导论里的伪代码
一、左旋
The pseudocode for LEFT-ROTATE assumes that right[x] ≠ nil[T] and that the root‘s parent is nil[T].（伪代码的左旋方法中假设X的右孩子不为空）
LEFT-ROTATE(T, x) 1 y ← right[x] ? Set y. 2 right[x] ← left[y] //开始变化，y的左孩子成为x的右孩子 3 if left[y] ！=nil[T] 4 then p[left[y]] <- x 5 p[y] <- p[x] //y成为x的父结点 6 if p[x] = nil[T] 7 then root[T] <- y 8 else if x = left[p[x]] 9 then left[p[x]] ← y 10 else right[p[x]] ← y 11 left[y] ← x //x成为y的左孩子（一月三日修正） 12 p[x] ← y
二、元素插入
RB-INSERT(T, z) //注意我给的注释...
1 y ← nil[T] // y 始终指向 x 的父结点。
2 x ← root[T] // x 指向当前树的根结点，
3 while x ≠ nil[T]
4 do y ← x
5 if key[z] < key[x] //向左，向右..
6 then x ← left[x]
7 else x ← right[x] // 为了找到合适的插入点，x 探路跟踪路径，直到x成为NIL 为止。
8 p[z] ← y // y置为 插入结点z 的父结点。
9 if y = nil[T]
10 then root[T] ← z
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z //此 8-13行，置z 相关的指针。
14 left[z] ← nil[T]
15 right[z] ← nil[T] //设为空，
16 color[z] ← RED //将新插入的结点z作为红色
17 RB-INSERT-FIXUP(T, z) //因为将z着为红色，可能会违反某一红黑性质，
//所以需要调用RB-INSERT-FIXUP(T, z)来保持红黑性质。三、插入修复
RB-INSERT-FIXUP(T, z)
1 while color[p[z]] = RED
2 do if p[z] = left[p[p[z]]]
3 then y ← right[p[p[z]]]
4 if color[y] = RED
5 then color[p[z]] ← BLACK ? Case 1
6 color[y] ← BLACK ? Case 1
7 color[p[p[z]]] ← RED ? Case 1
8 z ← p[p[z]] ? Case 1
9 else if z = right[p[z]]
10 then z ← p[z] ? Case 2
11 LEFT-ROTATE(T, z) ? Case 2
12 color[p[z]] ← BLACK ? Case 3
13 color[p[p[z]]] ← RED ? Case 3
14 RIGHT-ROTATE(T, p[p[z]]) ? Case 3
15 else (same as then clause
with "right" and "left" exchanged)
16 color[root[T]] ← BLACK四、删除
RB-DELETE(T, z)
1 if left[z] = nil[T] or right[z] = nil[T]
2 then y ← z
3 else y ← TREE-SUCCESSOR(z)
4 if left[y] ≠ nil[T]
5 then x ← left[y]
6 else x ← right[y]
7 p[x] ← p[y]
8 if p[y] = nil[T]
9 then root[T] ← x
10 else if y = left[p[y]]
11 then left[p[y]] ← x
12 else right[p[y]] ← x
13 if y 3≠ z
14 then key[z] ← key[y]
15 copy y's satellite data into z
16 if color[y] = BLACK //如果y是黑色的，
17 then RB-DELETE-FIXUP(T, x) //则调用RB-DELETE-FIXUP(T, x)
18 return y //如果y不是黑色，是红色的，则当y被删除时，红黑性质仍然得以保持。不做操作，返回。
//因为：1.树种各结点的黑高度都没有变化。2.不存在俩个相邻的红色结点。
//3.因为入宫y是红色的，就不可能是根。所以，根仍然是黑色的。五、删除修复
RB-DELETE-FIXUP(T, x) 1 while x ≠ root[T] and color[x] = BLACK 2 do if x = left[p[x]] 3 then w ← right[p[x]] 4 if color[w] = RED 5 then color[w] ← BLACK ? Case 1 6 color[p[x]] ← RED ? Case 1 7 LEFT-ROTATE(T, p[x]) ? Case 1 8 w ← right[p[x]] ? Case 1 9 if color[left[w]] = BLACK and color[right[w]] = BLACK 10 then color[w] ← RED ? Case 2 11 x ← p[x] ? Case 2 12 else if color[right[w]] = BLACK 13 then color[left[w]] ← BLACK ? Case 3 14 color[w] ← RED ? Case 3 15 RIGHT-ROTATE(T, w) ? Case 3 16 w ← right[p[x]] ? Case 3 17 color[w] ← color[p[x]] ? Case 4 18 color[p[x]] ← BLACK ? Case 4 19 color[right[w]] ← BLACK ? Case 4 20 LEFT-ROTATE(T, p[x]) ? Case 4 21 x ← root[T] ? Case 4 22 else (same as then clause with "right" and "left" exchanged) 23 color[x] ← BLACK
-------------------------------------------------------华丽分割线----------------------------------------------------------------------
六、红黑树的java实现
除了必备的左右旋、插入、删除，另外还增加了求前趋后继，中序遍历，最大值最小值等方法
代码：
class RBTree {
public static final boolean RED = false;
public static final boolean BLACK = true;
// 定义节点的结构
private class Node {
int value;
boolean color = false;
Node parent = null;
Node left = null;
Node right = null;
public Node() {
}
private Node(int value, boolean color, Node parent, Node left, Node right) {
this.value = http://www.mamicode.com/value;>
测试代码：
public static void main(String[] args) {
RBTree tree = new RBTree();
tree.put(12);
tree.put(1);
tree.put(9);
tree.put(2);
tree.put(0);
tree.put(11);
tree.put(7);
tree.put(19);
tree.put(4);
tree.put(15);
tree.put(18);
tree.put(5);
tree.put(14);
tree.put(13);
tree.put(10);
tree.put(16);
tree.put(6);
tree.put(3);
tree.put(8);
tree.put(17);
System.out.println();
tree.remove(12);
tree.remove(1);
tree.remove(9);
// tree.remove(2);
// tree.remove(0);
// tree.remove(11);
// tree.remove(7);
// tree.remove(19);
// tree.remove(4);
// tree.remove(15);
// tree.remove(18);
// tree.remove(5);
// tree.remove(14);
// tree.remove(13);
// tree.remove(10);
// tree.remove(16);
// tree.remove(6);
// tree.remove(3);
// tree.remove(8);
// tree.remove(17);
System.out.println("gen " + tree.getRoot());
System.out.println();
System.out.println(tree.get(12));
System.out.println(tree.get(1));
System.out.println(tree.get(9));
System.out.println(tree.get(2));
System.out.println(tree.get(0));
System.out.println(tree.get(11));
System.out.println(tree.get(7));
System.out.println(tree.get(19));
System.out.println(tree.get(4));
System.out.println(tree.get(15));
System.out.println(tree.get(18));
System.out.println(tree.get(5));
System.out.println(tree.get(14));
System.out.println(tree.get(13));
System.out.println(tree.get(10));
System.out.println(tree.get(16));
System.out.println(tree.get(6));
System.out.println(tree.get(3));
System.out.println(tree.get(8));
System.out.println(tree.get(17));
tree.inorder();
参考：
经典算法研究系列：五、红黑树算法的实现与剖析
http://blog.csdn.net/v_JULY_v/article/details/6109153
红黑树从头至尾插入和删除结点的全程演示图
http://blog.csdn.net/v_JULY_v/article/details/6284050
---------------------- ASP.Net+Unity开发、.Net培训、期待与您交流！ ----------------------详细请查看：http://edu.csdn.net
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。