package demo;

import java.util.LinkedList;
import java.util.prefs.BackingStoreException;

import org.w3c.dom.Node;

/**
 * 自平衡二叉树
 * 
 * @author Administrator
 *
 * @param <K>
 * @param <V>
 */
public class BSTAvl<K extends Comparable<K>, V> {

    private final Node EmptyNode = null;
    private Node head; // 头结点
    private int count;// 树中的节点个数
    private final static int balancerThreadhold = 2;// 树调整阈值

    /**
     * 私有节点
     * 
     * @author Administrator
     *
     * @param <K>
     * @param <V>
     */
    private class Node {
        K key;
        V value;
        Node left;
        Node right;
        int height;

        private Node(K key, V val) {
            this.key = key;
            this.value = val;
            this.left = EmptyNode;
            this.right = EmptyNode;
            this.height = 1;
        }

        private Node(Node node) {
            this.key = node.key;
            this.value = node.value;
            this.left = node.left;
            this.right = node.right;
            this.height = node.height;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("{ ").append(key).append(":").append(value).append(" }");
            return sb.toString();

        }

    }

    public BSTAvl() {
        head = EmptyNode;
        count = 0;
    }

    /**
     * 当前节点中的元素个数
     * 
     * @return
     */
    public int size() {
        return count;
    }

    /**
     * 当前树是否为空
     * 
     * @return
     */
    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * 添加公共方法
     * 
     * @param key
     * @param val
     */
    /**
     * @param key
     * @param val
     */
    public void insert(K key, V val) {
        checkArg(key, "key is null");
        head = insert(head, key, val);

    }

    /**
     * 实际的内部添加方法
     * 
     * @param root
     * @param key
     * @param val
     * @return
     */
    private Node insert(Node root, K key, V val) {
        if (root == EmptyNode) {
            count++;
            return new Node(key, val);
        }
        if (root.key.compareTo(key) > 0)
            root.left = insert(root.left, key, val);
        else if (root.key.compareTo(key) < 0)
            root.right = insert(root.right, key, val);
        else 
            root.value = val;
        
        root = tryBalance(root);
        return root;
    }

    private Node tryBalance(Node root) {
        // 计算新的高度
        root.height = 1 + Math.max(getHeight(root.left), getHeight(root.right));
        // 根据平衡因子和节点数的高度，判断是否需要左旋或是右旋
        // LL
        if (getBalanceFactor(root) > 1 && getBalanceFactor(root.left) >= 0)
            return rotationRight(root);

        // RR
        if (getBalanceFactor(root) < -1 && getBalanceFactor(root.right) <= 0)
            return rotationLeft(root);
        // LR
        if (getBalanceFactor(root) > 1 && getBalanceFactor(root.left) < 0) {
            root.left = rotationLeft(root.left);
            return rotationRight(root);
        }
        // RL
        if (getBalanceFactor(root) < -1 && getBalanceFactor(root.right) > 0) {
            root.right = rotationRight(root.right);
            return rotationLeft(root);
        }
        return root;
    }

    /**
     * 根据key查找指定的值公共方法
     * 
     * @param key
     * @return
     */
    public V search(K key) {
        return (V) search(head, key);
    }

    /**
     * 实际的搜索方法
     * 
     * @param root
     * @param key
     * @return
     */
    private V search(Node root, K key) {
        checkArg(key, "key is null");
        if (root == EmptyNode)
            return null;

        if (root.key.compareTo(key) == 0)
            return root.value;

        else if (root.key.compareTo(key) > 0)
            return (V) search(root.left, key);
        else
            return (V) search(root.right, key);
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        preOrder(head);
    }

    private void preOrder(Node root) {
        if (root == EmptyNode)
            return;
        System.out.print(root);
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 中序遍历
     */
    public void midOrder() {
        midOrder(head);
    }

    private void midOrder(Node root) {

        if (root == EmptyNode)
            return;
        midOrder(root.left);
        System.out.print(root);
        midOrder(root.right);

    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        postOrder(head);
    }

    private void postOrder(Node root) {
        if (root == EmptyNode)
            return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root);
    }

    /**
     * 非空检查
     * 
     * @param key
     * @param thrStr
     */
    private void checkArg(Object key, String thrStr) {
        if (key == null)
            throw new IllegalArgumentException(thrStr);
    }

    /**
     * 层级遍历
     */
    public void levelOrder() {
        if (head == EmptyNode)
            return;
        LinkedList<Node> ll = new LinkedList();
        ll.addLast(head);
        while (!ll.isEmpty()) {
            Node node = ll.removeFirst();
            System.out.println(node);
            if (node.left != EmptyNode)
                ll.addLast(node.left);
            if (node.right != EmptyNode)
                ll.addLast(node.right);
        }
    }

    /**
     * 获取最小的节点
     * 
     * @return
     */
    public K getMinNode() {
        checkArg(head, "this tree is empty!!");
        return (K) getMinNode(head).key;

    }

    private Node getMinNode(Node root) {
        if (root.left == EmptyNode)
            return root;
        return getMinNode(root.left);
    }

    /**
     * 获取最大的节点
     * 
     * @return
     */
    public K getMaxNode() {
        checkArg(head, "this tree is empty!!");
        return (K) getMaxNode(head).key;
    }

    private Node getMaxNode(Node root) {
        if (root.right == EmptyNode)
            return root;
        return getMaxNode(root.right);
    }

    /**
     * 删除最小的节点
     */
    public void removeMin() {
        checkArg(head, "the tree is empty");
        head = removeMin(head);
    }

    private Node removeMin(Node root) {
        if (root.left == EmptyNode) {
            Node rightNode = root.right;
            root = EmptyNode;
            count--;
            return rightNode;
        }
        root.left = removeMin(root.left);
        return root;
    }

    public void removeMax() {
        checkArg(head, "the tree is empty");
        head = removeMax(head);
    }

    private Node removeMax(Node root) {
        if (root.right == EmptyNode) {
            Node leftNode = root.left;
            root = null;
            count--;
            return leftNode;
        }
        root.right = removeMax(root.right);
        return root;
    }

    public void remove(K key) {
        head = remove(head, key);
    }

    /**
     * 删除指定
     * 
     * @param root
     * @param key
     * @return
     */
    private Node remove(Node root, K key) {
        if (root == EmptyNode)
            return EmptyNode;
        Node retNode;

        if (root.key.compareTo(key) < 0) {//
            root.right = remove(root.right, key);
            retNode = root;
        } else if (root.key.compareTo(key) > 0) {
            root.left = remove(root.left, key);
            retNode = root;
        } else {// equal
            if (root.left == EmptyNode) {// 没有左节点
                Node rightNode = root.right;
                root = EmptyNode;
                count--;
                retNode = rightNode;
            } else if (root.right == EmptyNode) {// 没有右节点
                Node leftNode = root.right;
                root = EmptyNode;
                count--;
                retNode = leftNode;
            } else {
                // 左右节点都存在
                Node min = getMinNode(root.right);
                Node s = new Node(min);
                s.right = remove(root.right,s.key);
                s.left = root.left;
                retNode = s;
            }

            if (retNode == EmptyNode)
                return EmptyNode;
        }
        retNode = tryBalance(retNode);
        return retNode;
    }

    /**
     * 获取平衡因子
     * 
     * @param node
     * @return
     */
    public int getBalanceFactor(Node node) {
        checkArg(node, "节点为空!!");
        return getHeight(node.left) - getHeight(node.right);
    }

    /**
     * 获取节点高度
     * 
     * @param node
     * @return
     */
    public int getHeight(Node node) {
        if (node == null)
            return 0;
        return node.height;

    }

    /**
     * 节点左旋
     * 
     * @param node
     */
    public Node rotationLeft(Node node) {

        Node x = node.right;
        Node T3 = x.left;

        x.left = node;
        node.right = T3;

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

        return x;
    }

    public Node rotationRight(Node node) {

        Node x = node.left;
        Node T3 = x.right;

        x.right = node;
        node.left = T3;

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

        return x;

    }

    public boolean isAvl() {
        return isAvl(head);
    }

    /**
     * 判断当前树是否为平衡树
     * 
     * @param head
     * @return
     */
    private boolean isAvl(Node node) {
        if (node == null)
            return true;
        if (Math.abs(getBalanceFactor(node)) > 1)
            return false;
        return isAvl(node.left) && isAvl(node.right);
    }

    /**
     * 主要的测试函数
     * 
     * @param args
     */
    public static void main(String[] args) {
        BSTAvl<Integer, Object> bst = new BSTAvl();
        bst.insert(1, "hello");
        bst.insert(10, "hello");
        bst.insert(9, "hello");
        bst.insert(20, "hello");
        bst.insert(11, "hello");
        bst.insert(14, "hello");
        bst.insert(90, "hello");
        bst.insert(25, "hello");
//      bst.insert(60, "hello");
        bst.insert(78, "hello");
        bst.midOrder();
        System.out.println("");
        System.out.println(bst.isAvl());
        bst.remove(14);
        // System.out.println("");
        System.out.println(bst.isAvl());
        bst.midOrder();
    }

}