import java.util.ArrayList;

public class BinarySearchTree<K extends Comparable<K>, V> {

    private Node root;
    private int size;

    public BinarySearchTree() {
        root = null;
        size = 0;
    }

    public static void main(String[] args) {
        ArrayList<Integer> words = new ArrayList<>();

        for (int i = 0; i < 1000; i++) {
            words.add(i);
        }

        BinarySearchTree<Integer, Integer> tree = new BinarySearchTree<>();

        for (Integer word : words) {
            if (!tree.contains(word)) {
                tree.insert(word, 0);
            }

            tree.set(word, tree.search(word).value + 1);
        }

        System.out.println("Height: " + tree.getHeight(tree.root));

        System.out.println(tree.getMin().key + ": " + tree.getMin().value);

        tree.remove(tree.getMin().key);

        System.out.println(tree.getMin().key + ": " + tree.getMin().value);

        System.out.println("Is valid BST? " + tree.isBST());
    }

    /**
     * Insert content to BST
     *
     * @param key
     * @param value
     */
    public void insert(K key, V value) {
        root = insert(root, key, value);
    }

    /**
     * Insert content under a specific node, usually called by
     * <code>{@link #insert(K, V)}</code>.
     *
     * @param node
     * @param key
     * @param value
     * @return
     */
    private Node insert(Node node, K key, V value) {
        if (node == null) {
            size++;
            return new Node(key, value);
        }

        // insert to left branch
        if (key.compareTo(node.key) < 0) {
            node.left = insert(node.left, key, value);
        }
        // insert to right branch
        else if (key.compareTo(node.key) > 0) {
            node.right = insert(node.right, key, value);
        }
        // update the node with given value instead of creating a new one
        else {
            node.value = value;
        }

        return node;
    }

    /**
     * Update the node bind the given key with new value.
     *
     * @param key
     * @param value
     * @return
     */
    public void set(K key, V value) {
        Node node = search(root, key);

        if (node == null) {
            throw new IllegalArgumentException(key + " Not Present!");
        }

        node.value = value;
    }

    /**
     * Search the whole BST for the wanted node binding given key.
     *
     * @param key
     * @return
     */
    private Node search(K key) {
        return search(root, key);
    }

    /**
     * Search the specific node for the wanted node binding given key, usually called by
     * <code>{@link #search(K)}</code>.
     *
     * @param node
     * @param key
     * @return
     */
    private Node search(Node node, K key) {
        if (node == null) {
            return null;
        }

        // exactly the wanted node
        if (key.compareTo(node.key) == 0) {
            return node;
        }
        // wanted node on left branch
        else if (key.compareTo(node.key) < 0) {
            return search(node.left, key);
        }

        // wanted node on right branch

        return search(node.right, key);
    }

    /**
     * Search the whole BST for the node binding the smallest key.
     *
     * @param
     */
    private Node getMin() {
        return getMin(this.root);
    }

    /**
     * Search under the given node for the node binding the smallest key, usually called by
     * <code>{@link #getMin()}</code>.
     *
     * @param node
     */
    private Node getMin(Node node) {
        if (node.left == null) {
            return node;
        }

        return getMin(node.left);
    }

    /**
     * Delete the node binding the given key under the whole BST.
     *
     * @param key
     * @return
     */
    public V remove(K key) {
        if (isEmpty()) {
            return null;
        }

        Node node = search(root, key);

        if (node != null) {
            root = remove(root, key);

            return node.value;
        }

        return null;
    }

    /**
     * Delete the node binding the given key under the given node, usually called by
     * <code>{@link #remove(K)}</code>.
     *
     * @param node
     * @param key
     * @return
     */
    private Node remove(Node node, K key) {
        if (node == null) {
            return null;
        }

        // search left
        if (key.compareTo(node.key) < 0) {
            node.left = remove(node.left, key);
            return node;
        }
        // search right
        else if (key.compareTo(node.key) > 0) {
            node.right = remove(node.right, key);
            return node;
        }

        // exactly the current one is the wanted node

        // 4 situations to be considered separately.

        size--;

        // 1. both empty
        if (node.left == null && node.right == null) {
            return null;
        }

        // 2. left empty
        if (node.left == null) {
            return node.right;
        }

        // 3. right empty
        if (node.right == null) {
            return node.left;
        }

        // 4. both non-empty

        // Find the min node on right branch which should be a node without left branch.
        Node successor = getMin(node.right);

        // Remove the min node from its original position and serves as a successor of current
        // node that going to be removed.
        successor.right = remove(node.right, successor.key);

        successor.left = node.left;

        // unlink the removed node, so that the gc will quickly find it.
        node.left = node.right = null;

        return successor;
    }

    public boolean contains(K key) {
        return search(root, key) != null;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getHeight() {
        return getHeight(root);
    }

    private int getHeight(Node root) {
        if (root == null) {
            return 0;
        }

        int left = getHeight(root.left);
        int right = getHeight(root.right);

        return Math.max(left, right) + 1;
    }

    /**
     * Verify current tree whether it's a qualified Binary Search Tree or not.
     *
     * @return
     */
    public boolean isBST() {
        ArrayList<K> keys = new ArrayList<>();

        inOrderTraversal(root, keys);

        for (int i = 1; i < keys.size(); i++) {
            if (keys.get(i - 1).compareTo(keys.get(i)) > 0) {
                return false;
            }
        }

        return true;
    }

    private void inOrderTraversal(Node node, ArrayList<K> keys) {
        if (node == null) {
            return;
        }

        inOrderTraversal(node.left, keys);

        keys.add(node.key);

        inOrderTraversal(node.right, keys);
    }

    private class Node {
        K key;
        V value;

        Node left;
        Node right;

        Node(K key, V value) {
            this.key = key;
            this.value = value;

            left = null;
            right = null;
        }
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-05 10:59:17

results matching ""

    No results matching ""