rbtree.java

关于用java实现的程序

/** RBTree class
	Original: Linda Luo
	Mods:  	Mervyn Ng
 **/
import java.util.*;
import java.applet.*;
import java.awt.*;
import java.lang.*;

class RBTree{
	private	RBNode root;
	public final RBNode sentinel;

	// Counters for coverage checking
	private static int case1ct;
	private static int case2ct;
	private static int case3ct;
	private static int case4ct;
	private static int case5ct;
	private static int case6ct;
	private static int case7ct;
	private static int case8ct;
	private Vector v_rbnodes = new Vector();
	private static final int padding = 100;
	private RBNode buffer[];

	private DrawingPanel dpAfter, dpBefore;
	private Graphics g;

	private Image offscreen = null;
	private Graphics offGraphics = null;
	private Dimension offscreensize = null;
	private Image beforeOffSc = null;
	private Graphics beforeOffGraphics = null;
	private Dimension beforeOffSize = null;

	private static final int x_offset = 50;
	private static final int y_offset = 10;
	
	private static final int labelFontSize = 12;
	
	
	public RBTree(){
	sentinel = new RBNode(0,0,0); 
	sentinel.Set_Cost(0.00);
	//sentinel = new RBNode(0);  
	sentinel.SetColorBlack();
	root = sentinel;
	case1ct = 0;
   	case2ct = 0;
   	case3ct = 0;
   	case4ct = 0;
  	case5ct = 0;
   	case6ct = 0;
	case7ct = 0;
	case8ct = 0;
	}

	/* Find Node containding data */
	public RBNode FindNode(int data){
		RBNode current = root;
		while(current != sentinel) {
		//if (data == current.Data())
		if (data == current.Cost())
				return (current);
			else {
				//if(data < current.Data())
				if(data < current.Cost())
					current = current.Left();
				else 	current = current.Right();
				}
			} 	
		
		return null;
		}

	/* Rotate node x to left */
	private void RotateLeft(RBNode x, Graphics g){
		Color origColour = x.getColour();
		x.Highlight(g, Color.yellow);		
	
		RBNode y = x.Right();
	
	
		/* establish x.right link */
		x.SetRight(y.Left());
		if (y.Left() != sentinel)
			y.Left().SetParent(x);
			
		/* establish y.parent link */
		if (y != sentinel) y.SetParent(x.Parent());
		if (x.Parent() != null){
			if (x == x.Parent().Left())
				x.Parent().SetLeft(y);
			else 
				x.Parent().SetRight(y);
			}
		else root = y;

	
		/* link x and y */
		y.SetLeft(x);
		if (x != sentinel) x.SetParent(y);

		x.Unhighlight_Node(g, origColour);
		}

	/* Rotate node x to right */
	private void RotateRight(RBNode x, Graphics g){
		Color origColour = x.getColour();
		x.Highlight(g, Color.yellow);		

		RBNode y = x.Left();
		
		/* establish x.left link */
		x.SetLeft(y.Right());
		if (y.Right() != sentinel)
			y.Right().SetParent(x);

		/* establish y.parent link */
      		if (y != sentinel) 
			y.SetParent(x.Parent());
	        if (x.Parent() != null){
     			if (x == x.Parent().Right())
         			x.Parent().SetRight(y);
         		else
         			x.Parent().SetLeft(y);
        		}
      		else root = y;


       	/* link x and y */
       	y.SetRight(x);
      	if (x != sentinel) x.SetParent(y);

		x.Unhighlight_Node(g, origColour);
		}

	/* allocate node for data and insert in tree */
	public boolean InsertNode(int data, AlgAnimFrame frame, RBTree tree){
		RBNode parent;
		RBNode current;	
		RBNode x;

		FontMetrics fm;
		int str_width, str_ht;
		int label_x, label_y;

		DrawingPanel dp = frame.getDrawingPanel();
		Graphics g = dp.getGraphics();
		
		System.out.println("RBTree: InsertNode: value " + data );
		/* find where node belongs */
		current = root;
		parent = null;
		while (current != sentinel){
			//System.out.println("root is "+root.Get_ID());
			if (data == current.Cost()) {
				//System.out.println("data == current.Data");
				return true;
				}
			parent = current;
			if (data < current.Cost()) {
				current = current.Left();
				//System.out.println("data < current.Data");
				}
			else {
				current = current.Right();
				//System.out.println("data >= current.Data");
				}
			System.out.println("value of data is "+data+", current = "+current.Cost());	
			}

		/* setup new node */
		//x = new RBNode(data);
		x = new RBNode(0, 0, 0); //merv
		x.Set_Cost((double)data);
		//System.out.println("data of x is "+data);
		if (x == null) {
			//System.out.println("x is null");
			return false;
			}
		x.SetLeft(sentinel);
		x.SetRight(sentinel);
		x.SetParent(parent);
		//System.out.println("new node setup");
		/* insert node in tree */
		if (parent != null) {
			if (data < parent.Cost())
				parent.SetLeft(x);
			else parent.SetRight(x);
			//System.out.println("parent != null");
			}
		else {
			root = x;
			//System.out.println("parent == null");
			}
		//System.out.println("Before DT");
		v_rbnodes.addElement((Object)x);
		/*-*/ drawRBTree(frame);
		if(tree.GetOffscreen() == null) {
			System.out.println("RBTree: offscreen is null");
			}

		ShadowLabel insertLabel = new ShadowLabel("Inserting Data Value: " +data);
		drawLabel(insertLabel, x_offset, (tree.dpAfter.getPanelHeight() - y_offset), frame);

		/*insertLabel.setFontSize(labelFontSize);
		fm = frame.getDrawingPanel().getFontMetrics(insertLabel.getFont());
		str_width = fm.stringWidth(insertLabel.getText());
		str_ht = fm.getHeight();
		label_x = x.Mid_X() - str_width/2;
		label_y = x.Mid_Y() + x.radius;// + str_ht + y_offset;
		System.out.println("radius is: " + x.radius);
		insertLabel.move(label_x, label_y);
		insertLabel.draw(offGraphics);
		*/
		
		g.drawImage(tree.GetOffscreen(), 0, 0, null);

		// Set up image for before panel
		drawRBTree(frame);
		insertLabel.setText("Before Rotation");
		insertLabel.draw(offGraphics);

		frame.waitStep();
		InsertFixup(x, frame, tree);
		v_rbnodes.addElement((Object)x);
		return (true);

		}	

	/* delete node z from tree */
	public void DeleteNode(RBNode z, AlgAnimFrame frame){

		RBNode x;
		RBNode y;
		
		if ( z == sentinel) return;
		
		if ( z.Left() == sentinel || z.Right() == sentinel){
			/* y has a sentinel node as a child */
			y = z;
			}
		else{
			/* find tree successor with a sentinel node as a child */
			y = z.Right();
			while ( y.Left() != sentinel) y = y.Left();
			}
	
		/* x is y's only child */
		if (y.Left() != sentinel)
			x = y.Left();
		else x = y.Right();
	
		/* remove y from the parent chain */
		x.SetParent(y.Parent());
		if (y.Parent() != null){
			if (y == y.Parent().Left())
				y.Parent().SetLeft(x);
			else y.Parent().SetRight(x);
			}
		else root = x;
		
		//if (y != z) z.SetData(y.Data());
		if (y != z) z.Set_Cost(y.Cost());
		
		if (y.IsBlack()) DeleteFixup(x, frame);
		
		}

	/* maintain red-black tree balance after inserting node x */
	private void InsertFixup(RBNode x, AlgAnimFrame frame, RBTree tree){
		DrawingPanel dpAfter = frame.getDrawingPanel();
		DrawingPanel dpBefore = frame.getBeforeDp();

		ShadowLabel colorLabel = new ShadowLabel("Restoring Red-Black Property...");
		ShadowLabel bforeLabel = new ShadowLabel("Before Rotation");
		ShadowLabel rotLeftLab = new ShadowLabel("Rotating Left...");
		ShadowLabel rotRightLab = new ShadowLabel("Rotating Right...");

		/* check red-black properties */
		while (x != root && x.Parent().IsRed()){
			System.out.println("In while loop");
			/* we have a violation */
			if (x.Parent() == x.Parent().Parent().Left()){
				RBNode y = x.Parent().Parent().Right();
				case1ct++;	
				//System.out.println("In case 1");
				//System.out.println("Node x data is "+x.Get_ID());
				//System.out.println("Node y data is "+y.Get_ID());
				if (y.IsRed()){
				
					/* uncle is red */
					drawLabel(colorLabel, x_offset, (tree.dpAfter.getPanelHeight() - y_offset), frame);
					x.Parent().SetColorBlack();
					y.SetColorBlack();
					x.Parent().Parent().SetColorRed();
					x = x.Parent().Parent();
					v_rbnodes.addElement((Object)x);
					DrawOffScreen(frame, tree);
					frame.waitStep();			
	
					case2ct++;
					//System.out.println("In case 2");
					//System.out.println("Node x data is "+x.Get_ID());
					//System.out.println("Node y data is "+y.Get_ID());
					}
				else {
					case3ct++;	
					//System.out.println("In case 3");
					//System.out.println("Node x data is "+x.Get_ID());
					//System.out.println("Node y data is "+y.Get_ID());
					/* uncle is black */
					if (x == x.Parent().Right()){
						/* make x a left child */
						x = x.Parent();

						drawBeforeLabel(bforeLabel, x_offset, (tree.dpBefore.getPanelHeight() - y_offset), frame);
						drawLabel(rotLeftLab, x_offset, (tree.dpAfter.getPanelHeight() - y_offset), frame);

						RotateLeft(x, g);
						v_rbnodes.addElement((Object)x);
						DrawOffScreen(frame, tree);
						frame.waitStep();
						case4ct++;
						//System.out.println("In case 4");
						//System.out.println("Node x data is "+x.Get_ID());
						//System.out.println("Node y data is "+y.Get_ID());
						}
				
					/* recolor and rotate */
					drawLabel(colorLabel, x_offset, (tree.dpAfter.getPanelHeight() - y_offset), frame);

					x.Parent().SetColorBlack();
					x.Parent().Parent().SetColorRed();
					v_rbnodes.addElement((Object)x);
					DrawOffScreen(frame, tree);
					frame.waitStep();

					drawBeforeLabel(bforeLabel, x_offset, (tree.dpBefore.getPanelHeight() - y_offset), frame);
					drawLabel(rotRightLab, x_offset, (tree.dpAfter.getPanelHeight() - y_offset), frame);

					RotateRight(x.Parent().Parent(), g);
					v_rbnodes.addElement((Object)x);
					DrawOffScreen(frame, tree);
					frame.waitStep();
					}
				}
			else{
			
				/* mirror image of above code */
				RBNode y = x.Parent().Parent().Left();
				case5ct++;
				//System.out.println("In case 5");
				//System.out.println("Node x data is "+x.Get_ID());
				//System.out.println("Node y data is "+y.Get_ID());
				if (y.IsRed()){
					/* uncle is red */
					drawLabel(colorLabel, x_offset, (tree.dpAfter.getPanelHeight() - y_offset), frame);

					x.Parent().SetColorBlack();
         	   			y.SetColorBlack();
			            	x.Parent().Parent().SetColorRed();
		  	                x = x.Parent().Parent();
					v_rbnodes.addElement((Object)x);
					DrawOffScreen(frame, tree);
					frame.waitStep();
					case6ct++;
					//System.out.println("In case 6");
					//System.out.println("Node x data is "+x.Get_ID());
					//System.out.println("Node y data is "+y.Get_ID());
               				}
 		       		else {
					case7ct++;
					//System.out.println("In case 7");
					//System.out.println("Node x data is "+x.Get_ID());
					//System.out.println("Node y data is "+y.Get_ID());
					/* uncle is black */
			                if (x == x.Parent().Left()){
			               	x = x.Parent();

					drawBeforeLabel(bforeLabel, x_offset, (tree.dpBefore.getPanelHeight() - y_offset), frame);
					drawLabel(rotRightLab, x_offset, (tree.dpAfter.getPanelHeight() - y_offset), frame);

			                RotateRight(x, g);
					v_rbnodes.addElement((Object)x);
					DrawOffScreen(frame, tree);
					frame.waitStep();
			                case8ct++; 
					//System.out.println("In case 8");
					//System.out.println("Node x data is "+x.Get_ID());
					//System.out.println("Node y data is "+y.Get_ID());
				 	}
                                
				drawLabel(colorLabel, x_offset, (tree.dpAfter.getPanelHeight() - y_offset), frame);

		        	x.Parent().SetColorBlack();
		                x.Parent().Parent().SetColorRed();
				v_rbnodes.addElement((Object)x);
				DrawOffScreen(frame, tree);
				frame.waitStep();

				drawBeforeLabel(bforeLabel, x_offset, (tree.dpBefore.getPanelHeight() - y_offset), frame);
				drawLabel(rotLeftLab, x_offset, (tree.dpAfter.getPanelHeight() - y_offset), frame);

            			RotateLeft(x.Parent().Parent(), g);
				v_rbnodes.addElement((Object)x);
				DrawOffScreen(frame, tree);
				frame.waitStep();
            			}
        		}
		}
//	drawRBTree(frame);
	root.SetColorBlack();
	drawRBTree(frame);
	g.drawImage(tree.GetOffscreen(), 0, 0, null);
	frame.waitStep();
	System.out.println("InsertFixup return");
	}





	/* maintain red-black tree balance after deleting node x */
	private void DeleteFixup(RBNode x, AlgAnimFrame frame){
			
		DrawingPanel dp = frame.getDrawingPanel();
		Graphics g = dp.getGraphics();

		
        while (x != root && x.IsBlack()){
       		if (x == x.Parent().Left()){
         		RBNode w = x.Parent().Right();

        		if (w.IsRed()){
				w.SetColorBlack();
               			x.Parent().SetColorRed();
               			RotateLeft(x.Parent(), g);
				w = x.Parent().Right();
				}
        		if (w.Left().IsBlack() && w.Right().IsBlack()){
				w.SetColorRed();
				x = x.Parent();
				}
			else{
						
        			if (w.Right().IsBlack()){
        			w.Left().SetColorBlack();
				w.SetColorRed();
				RotateRight(w, g);
				w = x.Parent().Right();
            			}
            	   			
				if (x.Parent().IsBlack()) 
					w.SetColorBlack();
				else w.SetColorRed();
				x.Parent().SetColorBlack();
		
				w.Right().SetColorBlack();
				RotateLeft(x.Parent(), g);
				x = root;
	      			}
           		}