c2java 第3篇 红黑树删除的理解和jdb调试初步
红黑树节点的删除，值替换后不改变红黑属性，归结为删除最多有一个孩子的节点，对应到2-3-4树叶节点的：
1. 4-节点
2. 3-节点
3. 2-节点
a.兄节点至少是3-节点: 两次转移.
b.弟节点是2-节点:一次转移，一次融合.
c.父节点是2-节点:cascading
2-3-4树的删除太复杂，估计没人用在实践中；并且还有个缺点：
真正该删除的保留，而其他节点被删除，如果仍然被程序其他部分持有，就悲剧了。
因此算法导论第三版做了更改，许多其他书籍引用还是第2版的做法。
删除后的调整
/*
|
B
/ A D
/ \ / a b C E
/ \ / c d e f
*/
0. 只涉及到A到E五个节点，周围节点a-f不变。
1. 最终目的状态是经过A的黑高度加一，其他节点高度不变。
2. 初始状态是经过A的黑高度少了一。
3. 初始树的形态有多种：
(A,D) = (b,r)
(A,D,Dl,Dr) = (b,b,b,b)
(A,D,Dl,Dr) = (b,b,r,b)
(A,D,Dl,Dr) = (b,b,*,r)
其中Dl,Dr分别是D的左右儿子，*表示颜色任意；
Q: 插入一个元素后马上删除之，树的形态会不会变？
A: 见下面的输出，只差一个局部的旋转而已。
图片来源: http://blog.chinaunix.net/uid-26575352-id-3061918.html
语言注记
====
L1 如果我们想这样定义类:
Struct Node{
int val;
Struct Node *child[2];
};可以简化fixup()代码，但是java不支持，只能这样:Node.java
class Node{
int val;
Node[] child = {null, null};
public Node(int _val, Node l, Node r){
val = _val;
child[0] = l; child[1] = r;
}
public static void main(String[] arg){
Node b = new Node(1, null, null),
c = new Node(2, null, null),
a = new Node(0, b, c);
System.out.printf("%d %d\n", a.child[0].val, a.child[1].val);
}
}
如果非要这样子，我们自然引出这样的问题：因为数组是在堆上分配的，java如何避免内存碎片化？
L2 我的jdb 不能stop in 行号，只能这样stop in RBTree.plant断点在函数开头，
如果函数很长则颇为不便，是不是jdk 1.5 for windows 的不支持呢？
附jdb #gdb 的对比
====
stop in RBTree.plant #break plant
clear #delete
cont #c
locals #info local
dump var #print *var
print val #print var
set val = x # print val = x
where #bactrace
up, down #frame n
next, step #next, step
threads/thread #info thread/ thread n
monitor cmd #?
catch, watch #?
trace #跟踪函数的进出
classes：列举当前已知的类。
suspend, resume：线程的suspend和resume，需要加线程号为参数。
methods, fileds：列举类的方法和成员变量。
树的输出，根据后序和中序可以重构二叉树。
附代码：
/*RBTree.java -- Red Black Tree
todo: 把插入改成算法导论第3版的。
author: ludi 2014.04
*/
class RBNode<T extends Comparable<T>>
{
RBNode<T> parent, left, right;
int color;
T nodeValue;
RBNode(T item, RBNode<T> left, RBNode<T> right,
RBNode<T> parent, int color)
{
nodeValue = item;
this.left = left;
this.right = right;
this.parent = parent;
this.color = color;
}
}
public class RBTree<T extends Comparable<T>>
{
RBNode<T> root;
RBNode<T> NIL = null;
final static int BLACK = 0, RED = 1;
public RBTree()
{/*构造方法: 这样构造NIL使得它可以像其他节点那样参与旋转*/
if (NIL == null)
NIL = new RBNode<T>(null, null, null, null, BLACK);
root = NIL;
}
public void deleteTree(RBNode<T> t)
{/*析构方法*/
if (t != NIL){
deleteTree(t.left);
deleteTree(t.right);
t = null;
}
}
private void rotate (RBNode<T> pivot, int type)
{/*type == 0: 左旋*/
RBNode<T> p = pivot.parent, g = pivot.parent.parent;
if(0 == type){
p.right = pivot.left;
pivot.left = p;
pivot.parent = g;
p.parent = pivot;
if (p.right != NIL)
p.right.parent = p;
}else{
p.left = pivot.right;
pivot.right = p;
pivot.parent = g;
p.parent = pivot;
if (p.left != NIL)
p.left.parent = p;
}
if (p == root)
root = pivot;
else if (p == g.right)
g.right = pivot;
else
g.left = pivot;
}
private void delRotate (RBNode<T> x, int type)
{/*type == 0: x左旋下沉*/
RBNode<T> y;
if(0 == type){
y = x.right;
x.right = y.left;
if(y.left != NIL){y.left.parent = x;}
y.left =x;
}else{
y = x.left;
x.left = y.right;
if(y.right != NIL){y.right.parent = x;}
y.right = 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;
x.parent = y;
}
private void split4Node(RBNode<T> x)
{/*提升4-节点并做必要的旋转*/
/*翻转颜色*/
x.color = RED;
x.left.color = BLACK;
x.right.color = BLACK;
RBNode<T> p = x.parent;
if (p.color == RED){/*如果父节点是红色则需要旋转*/
RBNode<T> g = x.parent.parent;
g.color = RED;
if ( p == g.left && x == p.right ){/*x是g的内部孙子*/
rotate(x, 0);
x.color = BLACK;
p = x; /*准备右旋*/
}else if ( p == g.right && x == p.left ){
rotate(x, 1);
x.color = BLACK;
p = x;
}else{
p.color = BLACK;
}
rotate(p, p == g.left ? 1 : 0);
}
}
public boolean add(T item)
{/*插入*/
RBNode<T> curr = root, parent = NIL, newNode;
while (curr != NIL){/*查找插入点*/
if (curr.nodeValue.equals(item))
return false;
/*R1 沿路分裂4-节点*/
if (curr.left.color == RED &&
curr.right.color == RED)
split4Node(curr);
parent = curr;
if (item.compareTo(curr.nodeValue) < 0)
curr = curr.left;
else
curr = curr.right;
}
/*R2 新节点以红节点插入*/
newNode = new RBNode<T>(item, NIL, NIL, parent, RED);
if (parent == NIL){
root = newNode;
}else{
if (item.compareTo(parent.nodeValue) < 0)
parent.left = newNode;
else
parent.right = newNode;
/*R3 出现连续的红节点需要旋转*/
if (parent.color == RED)
split4Node(newNode);
}
root.color = BLACK; /*R4 根节点是黑色的*/
return true;
}
private void plant(RBNode<T> u, RBNode<T> v)
{/*把v放置在u位置*/
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 void fixup(RBNode<T> x)
{
RBNode<T> w; /*x的兄弟*/
while(x != root && x.color == BLACK){
if(x == x.parent.left){
w = x.parent.right;
if(w.color == RED){
/*case1: w 是红的*/
w.color = BLACK;
x.parent.color = RED;
delRotate(x.parent, 0); /*颜色翻转和旋转*/
w = x.parent.right; /*指向原来w的左儿子，此时w必为黑*/
}
if(w.left.color == BLACK && w.right.color == BLACK){
/*case2: w 是黑的，w的儿子都是黑的*/
w.color = RED; /*w和x都去掉一个黑*/
x = x.parent; /*为补偿，父亲节点加一个黑*/
}else{
if(w.right.color == BLACK){
/*case3:w 是黑的，w的左儿子是红的，w的右儿子是黑的*/
w.left.color = BLACK;
w.color = RED;
delRotate(w, 1);
w = x.parent.right;
}
/*case4:w 是黑的，w的右儿子是红的*/
w.color = x.parent.color;
x.parent.color = BLACK;
w.right.color = BLACK;
delRotate(x.parent, 0); /*终于去掉了x的附加黑*/
x = root; /*设置终止条件*/
}
}else{/*symmetry*/
w = x.parent.left;
if(w.color == RED){
w.color = BLACK;
x.parent.color = RED;
delRotate(x.parent, 1);
w = x.parent.left;
}
if(w.left.color == BLACK && w.right.color == BLACK){
w.color = RED;
x = x.parent;
}else{
if(w.left.color == BLACK){
w.right.color = BLACK;
w.color = RED;
delRotate(w, 0);
w = x.parent.left;
}
w.color = x.parent.color;
x.parent.color = BLACK;
w.left.color = BLACK;
delRotate(x.parent, 1);
x = root;
}
}
}
x.color = BLACK;
}
void removeNode(RBNode<T> z)
{/*删除z*/
RBNode<T> y = z, x;
int yoc = y.color;
/*标准二叉树删除：用z的后继y替换z*/
if(z.left == NIL){
x = z.right;
plant(z, z.right);
}else if(z.right == NIL){
x = z.left;
plant(z, z.left);
}else{
y = minimum(z.right);
yoc = y.color;
x = y.right;
if(y.parent == z)
x.parent = y;
else{
plant(y, y.right);
y.right = z.right;
y.right.parent = y;
}
plant(z, y);
y.left = z.left;
y.left.parent = y;
y.color = z.color;
}
/*红黑属性的维护： y是红节点则什么都不用做。*/
if(BLACK == yoc)
fixup(x);
}
RBNode<T> find(RBNode<T> t, T val){
/*以t为根，查找值为val的节点*/
while(t != NIL){
if(t.nodeValue == val)break;
else if(val.compareTo(t.nodeValue) < 0)
t = t.left;
else
t = t.right;
}
return t;
}
public RBNode<T> remove(T val){
/*删除并返回值为val的节点，如果值不存在返回null*/
RBNode<T> t = find(root, val);
if(t == NIL)return null;
removeNode(t);
return t;
}
public RBNode<T> minimum(RBNode<T> t)
{/*以t为根节点的最小节点是其最左节点*/
while(t.left != NIL){
t = t.left;
}
return t;
}
/*下面是非核心方法，仅用来练习二叉树*/
void visitInOrder(RBNode<T> t){
if(t == NIL)return;
visitInOrder(t.left);
System.out.print(t.nodeValue + " ");
visitInOrder(t.right);
}
int height(RBNode<T> t){
int hl, hr;
if(t == NIL)return -1;
hl = height(t.left);
hr = height(t.right);
hl = 1 + (hl > hr ? hl : hr);
System.out.print(t.nodeValue + ":" + hl + " ");
return hl;
}
void print(){
System.out.println("tree height: ");
height(root);
System.out.println();
System.out.println("visitInOrder:");
visitInOrder(root);
System.out.println();
}
}
class Test{
public static void main(String[] arg){
RBTree<Integer> tree = new RBTree<Integer>();
//int[] arr = {40, 20, 10, 35, 50, 25, 30};
int[] arr = {2,15,12,4,8,10,25,35,55,11};
for(int i = 0; i < arr.length; ++i){
tree.add(arr[i]);
System.out.print("after insert " + arr[i] + ", ");
tree.print();
}
for(int i = arr.length-1; i >= 0; --i)
{
tree.remove(arr[i]);
System.out.print("after delete " + arr[i] + ", ");
tree.print();
}
tree.deleteTree(tree.root);
tree = null;
}
}
/*
$ javac -encoding UTF-8 -g RBTree.java && java Test > xx.txt
ludi@msys ~/java
$ cat xx.txt
after insert 2, tree height:
2:0
visitInOrder:
2
after insert 15, tree height:
15:0 2:1
visitInOrder:
2 15
after insert 12, tree height:
2:0 15:0 12:1
visitInOrder:
2 12 15
after insert 4, tree height:
4:0 2:1 15:0 12:2
visitInOrder:
2 4 12 15
after insert 8, tree height:
2:0 8:0 4:1 15:0 12:2
visitInOrder:
2 4 8 12 15
after insert 10, tree height:
2:0 10:0 8:1 4:2 15:0 12:3
visitInOrder:
2 4 8 10 12 15
after insert 25, tree height:
2:0 10:0 8:1 4:2 25:0 15:1 12:3
visitInOrder:
2 4 8 10 12 15 25
after insert 35, tree height:
2:0 10:0 8:1 4:2 15:0 35:0 25:1 12:3
visitInOrder:
2 4 8 10 12 15 25 35
after insert 55, tree height:
2:0 10:0 8:1 4:2 15:0 55:0 35:1 25:2 12:3
visitInOrder:
2 4 8 10 12 15 25 35 55
after insert 11, tree height:
2:0 8:0 11:0 10:1 4:2 15:0 55:0 35:1 25:2 12:3
visitInOrder:
2 4 8 10 11 12 15 25 35 55
after delete 11, tree height:
2:0 8:0 10:1 4:2 15:0 55:0 35:1 25:2 12:3
visitInOrder:
2 4 8 10 12 15 25 35 55
after delete 55, tree height:
2:0 8:0 10:1 4:2 15:0 35:0 25:1 12:3
visitInOrder:
2 4 8 10 12 15 25 35
after delete 35, tree height:
2:0 8:0 10:1 4:2 15:0 25:1 12:3
visitInOrder:
2 4 8 10 12 15 25
after delete 25, tree height:
2:0 8:0 10:1 4:2 15:0 12:3
visitInOrder:
2 4 8 10 12 15
after delete 10, tree height:
2:0 8:0 4:1 15:0 12:2
visitInOrder:
2 4 8 12 15
after delete 8, tree height:
2:0 4:1 15:0 12:2
visitInOrder:
2 4 12 15
after delete 4, tree height:
2:0 15:0 12:1
visitInOrder:
2 12 15
after delete 12, tree height:
2:0 15:1
visitInOrder:
2 15
after delete 15, tree height:
2:0
visitInOrder:
2
after delete 2, tree height:
visitInOrder:
ludi@msys ~/java
$
*/
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
