Skip to content

Instantly share code, notes, and snippets.

@tomerun

tomerun/BinTree.java

Created Aug 25, 2012
Embed
What would you like to do?
Introduction to Algorithm exercise 12.3-6
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);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment