hzqjyyx
6/14/2018 - 10:40 AM

BST.java

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);
        }
    }
}