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: 见下面的输出,只差一个局部的旋转而已。

c2java 第3篇 红黑树删除的理解和jdb调试初步

图片来源: 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
$
*/


 

 

c2java 第3篇 红黑树删除的理解和jdb调试初步,布布扣,bubuko.com

c2java 第3篇 红黑树删除的理解和jdb调试初步

上一篇:MySQL 模拟条件索引


下一篇:oracle更改数据库字符集编码!