public class BST {
private Node root;
private class Node {
int value;
Node p, left, right;
}
private Node search(Node node, int t) {
while (node != null) {
if (node.value == t) {
return node;
} else if (t < node.value) {
node = node.left;
} else {
node = node.right;
}
}
return null;
}
private Node successor(Node node) {
if (node == null) return null;
if (node.right != null) {
return minimum(node.right);
}
Node y = node.p;
while (y != null && node == y.right) {
node = y;
y = y.p;
}
return y;
}
private Node predecessor(Node node) {
if (node == null) return null;
if (node.left != null) {
return maximum(node.left);
}
Node y = node.p;
while (y != null && node == y.left) {
node = y;
y = y.p;
}
return y;
}
private Node minimum(Node node) {
if (node == null) return null;
while (node.left != null) {
node = node.left;
}
return node;
}
private Node maximum(Node node) {
if (node == null) return null;
while (node.right != null) {
node = node.right;
}
return node;
}
private void transplant(Node u, Node v) {
if (u.p == null) {
root = v;
} else if (u == u.p.left) {
u.p.left = v;
} else {
u.p.right = v;
}
if (v != null)
v.p = u.p;
}
public void insert(int t) {
Node node = search(root, t);
if (node != null) {
throw new RuntimeException("Element has existed");
}
node = root;
Node y = null;
while (node != null) {
y = node;
if (t < node.value) {
node = node.left;
} else {
node = node.right;
}
}
Node z = new Node();
z.p = y;
z.value = t;
if (y == null) {
root = z;
} else if (t < y.value) {
y.left = z;
} else {
y.right = z;
}
}
public void delete(int t) {
Node node = search(root, t);
if (node == null) {
throw new RuntimeException("No such elements");
}
if (node.left == null) {
transplant(node, node.right);
} else if (node.right == null) {
transplant(node, node.left);
} else {
Node y = minimum(node.right);
if (y.p != node) {
transplant(y, y.right);
y.right = node.right;
y.right.p = y;
}
transplant(node, y);
y.left = node.left;
y.left.p = y;
}
}
public void build(int... src) {
BST.shuffleArray(src);
for (int a : src) {
insert(a);
}
}
private static void shuffleArray(int... src) {
Random random = ThreadLocalRandom.current();
for (int i = 0; i < src.length - 1; i++) {
int j = random.nextInt(src.length - i) + i;
int tmp = src[i];
src[i] = src[j];
src[j] = tmp;
}
}
public boolean contains(int t) {
return search(root, t) != null;
}
public int successor(int t) {
return successor(search(root, t)).value;
}
public int predecessor(int t) {
return predecessor(search(root, t)).value;
}
public int minimum() {
return minimum(root).value;
}
public int maximum() {
return maximum(root).value;
}
public void clear() {
root = null;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
inorder(root, sb);
return sb.toString();
}
private void inorder(Node node, StringBuilder sb) {
if (node != null) {
inorder(node.left, sb);
sb.append(node.value).append(' ');
inorder(node.right, sb);
}
}
}