import java.util.ArrayList;

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

    private Node root;
    private int size;

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

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

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

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

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

    /**
     * Get the height of the max long branch.
     *
     * @param node
     * @return
     */
    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        }

        return node.height;
    }

    /**
     * The height difference between left and right branches.
     *
     * @param node
     * @return
     */
    private int getBalanceFactor(Node node) {
        if (node == null) {
            return 0;
        }

        return getHeight(node.left) - getHeight(node.right);
    }

    /**
     * Rotate when right is higher
     *
     * @param node
     * @return
     */
    private Node rightRotate(Node node) {
        //          node                              nodex
        //         /   \                              /   \
        //      nodex   N5       right rotate       N1    node
        //      /   \            - - - - - - >     /  \   /  \
        //    N1     N4                          N2   N3 N4   N5
        //   /   \
        //  N2    N3

        Node nodex = node.left;

        Node N3 = nodex.right;

        nodex.right = node;
        node.left = N3;

        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        nodex.height = Math.max(getHeight(nodex.left), getHeight(nodex.right)) + 1;

        return nodex;
    }

    /**
     * Rotate when right is higher
     *
     * @param node
     * @return
     */
    private Node leftRotate(Node node) {
        //     node                                nodex
        //     /   \                               /   \
        //    N1  nodex       left rotate        node   N3
        //        /   \     - - - - - - >       /  \   /  \
        //       N2    N3                       N1 N2 N4  N5
        //            /  \
        //           N4   N5

        Node nodex = node.right;

        Node N2 = nodex.left;

        nodex.left = node;
        node.right = N2;

        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        nodex.height = Math.max(getHeight(nodex.left), getHeight(nodex.right)) + 1;

        return nodex;
    }

    /**
     * Insert new element.
     *
     * @param key
     * @param value
     */
    public void insert(K key, V value) {
        root = insert(root, key, value);
    }

    /**
     * Insert content under a specific node and adjust the balance of the tree afterwards, 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;
        }

        // Update current height after inserting new node which may change.
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

        return keepBalance(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;
        }

        Node retNode;

        // search left
        if (key.compareTo(node.key) < 0) {
            node.left = remove(node.left, key);
            retNode = node;
        }
        // search right
        else if (key.compareTo(node.key) > 0) {
            node.right = remove(node.right, key);
            retNode = node;
        }
        // exactly the current one is the wanted node
        else {
            // 4 situations to be considered separately.

            size--;

            // 1. both empty
            if (node.left == null && node.right == null) {
                retNode = null;
            }
            // 2. left empty
            else if (node.left == null) {
                retNode = node.right;
            }
            // 3. right empty
            else if (node.right == null) {
                retNode = node.left;
            }
            // 4. both non-empty
            else {
                // 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;

                retNode = successor;
            }
        }

        if (retNode == null) {
            return null;
        }

        return keepBalance(node);
    }

    /**
     * Adjust the tree to make it balanced.
     *
     * @param node
     * @return
     */
    private Node keepBalance(Node node) {

        int balanceFactor = getBalanceFactor(node);

        // left branch is much higher, run right rotate
        if (balanceFactor > 1) {

            if (getBalanceFactor(node.left) < 0) {
                node.left = leftRotate(node.left);
            }

            return rightRotate(node);
        }

        // right branch is much higher, run left rotate
        if (balanceFactor < -1) {

            if (getBalanceFactor(node.right) > 0) {
                node.right = rightRotate(node.right);
            }

            return leftRotate(node);
        }

        return node;
    }

    /**
     * Verify if the tree is balanced.
     *
     * @return
     */
    public boolean isBalanced() {
        return isBalanced(root);
    }

    /**
     * Verify if the tree is balanced recursively, usually called by
     * <code>{@link #isBalanced(Node)}</code>..
     *
     * @param node
     * @return
     */
    private boolean isBalanced(Node node) {
        if (node == null) {
            return true;
        }

        int balanceFactor = getBalanceFactor(node);
        if (Math.abs(balanceFactor) > 1) {
            return false;
        }

        return isBalanced(node.left) && isBalanced(node.right);
    }

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

    public int getSize() {
        return size;
    }

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

    /**
     * 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;

        int height;

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

            this.left = null;
            this.right = null;

            this.height = 1;
        }
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-05 11:00:25

results matching ""

    No results matching ""