Introduction to Algorithm exercise 12.3-6

BinTree.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

public class BinTree {

	static Random rand = new Random();

	public static void main(String[] args) throws Exception {
		for (int t = 0; t < 10; ++t) {
			ArrayList<Integer> keys = new ArrayList<Integer>();
			for (int i = 0; i < 100000; ++i) {
				keys.add(i);
			}
			Collections.shuffle(keys);
			BinTree tree = new BinTree();
			for (int k : keys) {
				tree.insert(new Node(k));
			}
			Collections.shuffle(keys);
			for (int k : keys) {
				tree.delete(k);
			}
		}
	}

	Node root;

	void insert(Node node) {
		if (this.root == null) {
			this.root = node;
			return;
		}
		Node p = null;
		Node c = this.root;
		while (c != null) {
			p = c;
			if (node.key < c.key) {
				c = c.left;
			} else {
				c = c.right;
			}
		}
		if (node.key < p.key) {
			p.left = node;
		} else {
			p.right = node;
		}
		node.parent = p;
	}

	Node search(int key) {
		Node c = this.root;
		while (c != null) {
			if (c.key == key) break;
			if (key < c.key) {
				c = c.left;
			} else {
				c = c.right;
			}
		}
		return c;
	}

	Node delete(int key) {
		Node z = search(key);
		if (z == null) return null;
		Node y = null;
		if (z.left == null || z.right == null) {
			y = z;
		} else {
			y = (rand.nextBoolean() ? successor(z) : predecessor(z));
			//				y = successor(z);
			//				y = predecessor(z);
		}
		Node x = (y.left != null ? y.left : y.right);
		if (x != null) {
			x.parent = y.parent;
		}
		if (y.parent == null) {
			this.root = x;
		} else {
			if (y == y.parent.left) {
				y.parent.left = x;
			} else {
				y.parent.right = x;
			}
		}
		if (y != z) {
			z.key = y.key;
		}
		y.parent = y.left = y.right = null;
		return y;
	}

	Node successor(Node x) {
		if (x.right != null) {
			return x.right.min();
		}
		Node y = x.parent;
		while (y != null && y.right == x) {
			x = y;
			y = y.parent;
		}
		return y;
	}

	Node predecessor(Node x) {
		if (x.left != null) {
			return x.left.max();
		}
		Node y = x.parent;
		while (y != null && y.left == x) {
			x = y;
			y = y.parent;
		}
		return y;
	}

	void print() {
		Node.print(this.root, 0);
	}

	static class Node {
		Node parent, left, right;
		int key;

		Node(int key) {
			this.key = key;
		}

		Node min() {
			return this.left != null ? this.left.min() : this;
		}

		Node max() {
			return this.right != null ? this.right.max() : this;
		}

		static void print(Node node, int depth) {
			char[] indent = new char[depth * 2];
			Arrays.fill(indent, ' ');
			if (node == null) {
				System.out.println(String.valueOf(indent) + "nil");
				return;
			}
			print(node.left, depth + 1);
			System.out.println(String.valueOf(indent) + node.key);
			print(node.right, depth + 1);
		}

	}

}