package week7;

import java.util.ArrayDeque;
import java.util.ArrayList;
public class AVLTree<T extends Comparable<T>> {

    /**
     *  将数组内的数据存储进二叉树
     * @param nodeValues 需要录入二叉树的数组
     * @return 返回已录入数据的二叉树的根节点
     */
    public static AVLTree<Integer> initTreeAndShowData(int[] nodeValues) {
        AVLTree<Integer> tree = new AVLTree<Integer>();
        for (int i = 0; i < nodeValues.length; i++) {
            tree.insert(nodeValues[i]);
            System.out.print(nodeValues[i] + " ");
        }
        System.out.println();
        return tree;
    }

    /****************************************************************************/

    /**
     * 二叉树内部节点
     */
    public class TreeNode<T extends Comparable<T>> {
        private T data;
        private TreeNode<T> left;
        private TreeNode<T> right;
        private int height;
        TreeNode(T data) {
            this.data = data;
            left = null;
            right = null;
        }
    }

    public TreeNode<T> root;

    AVLTree() {
        root = null;
    }

    /**
     * 将给定数据插入节点
     * @param data  需要插入树中的节点数据
     */
    public void insert(T data) {
        root = insertNode(root, data);
    }

    /**
     * 插入二叉树的内部实现
     * @param root 指定的根节点
     * @param data  需要插入的数据
     * @return  返回插入数据后的树
     */
    private TreeNode<T> insertNode(TreeNode<T> root, T data) {
        if (root == null) {
            root = new TreeNode<>(data);
        } else {
            //比较插入数据与当前根节点的大小
            int cmp = data.compareTo(root.data);

            if (cmp < 0) {
                root.left = insertNode(root.left, data);
                //判断平衡因子是否超过了1
                if (isLargerThanOne(root)) {
                    if (data.compareTo(root.left.data) < 0) {
                        //左单旋
                        root = singleLeftRotation(root);
                    } else {
                        //左-右双旋
                        root = doubleLeftRightRotation(root);
                    }
                }
            } else if (cmp > 0) {
                root.right = insertNode(root.right, data);
                if (isLargerThanOne(root)) {
                    if (data.compareTo(root.right.data) > 0) {
                        //右单旋
                        root = singleRightRotation(root);
                    } else {
                        //右-左双旋
                        root = doubleRightLeftRotation(root);
                    }
                }
            } else {
                System.out.println("已存在相同节点");
            }
        }
        //更新节点高度
        root.height = Math.max(getHeightRecord(root.left), getHeightRecord(root.right)) + 1;
        return root;
    }


    private boolean isLargerThanOne(TreeNode tree) {
        return Math.abs(getHeightRecord(tree.left) - getHeightRecord(tree.right)) > 1;
    }

    /**
     *  将传入节点的左子节点提升为根
     * @param tree  被破坏节点
     * @return  返回旋转完毕后的子树
     */
    private TreeNode singleLeftRotation(TreeNode tree) {
        //将被破坏节点的左子节点提升为根节点
        TreeNode root = tree.left;
        //如果新根节点的右边不为空，把它放进被破坏节点的左边
        tree.left = root.right == null ? null : root.right;
        //被破坏节点放进新根节点的右边
        root.right = tree;
        return root;
    }

    /**
     *  将传入节点的右子节点提升为根
     * @param tree  被破坏节点
     * @return  返回旋转完毕后的子树
     */
    private TreeNode singleRightRotation(TreeNode tree) {
        //将被破坏节点的右子节点提升为根节点
        TreeNode root = tree.right;
        //如果新根节点的左边不为空，转移到被破坏节点的右边
        tree.right = root.left == null ? null : root.left;
        //被破坏节点放进新根节点的左边
        root.left = tree;
        return root;
    }

    /**
     * 处理LR插入
     * @param tree  被破坏节点
     * @return  返回旋转完毕后的子树
     */
    private TreeNode doubleLeftRightRotation(TreeNode tree) {
        tree.left = singleRightRotation(tree.left);
        return singleLeftRotation(tree);
    }

    /**
     * 处理RL插入
     * @param tree  被破坏节点
     * @return  返回旋转完毕后的子树
     */
    private TreeNode doubleRightLeftRotation(TreeNode tree) {
        tree.right = singleLeftRotation(tree.right);
        return singleRightRotation(tree);
    }

    /**
     * 获取tree的高度
     * @param tree  一个节点
     * @return  如果为null，返回0，否则返回高度
     */
    private int getHeightRecord(TreeNode tree) {
        if (tree != null) {
            return tree.height;
        }
        return 0;
    }

    /**
     * 按层级显示一棵二叉树，不带高度的二叉树
     * @param node 二叉树的根节点
     */
    public void show(TreeNode<Integer> node) {
        ArrayDeque<TreeNode> nodes = new ArrayDeque<>();
        int i = 0, n = 0;
        boolean isFirst = true;
        TreeNode<Integer> t;
        nodes.add(node);
        while (nodes.size() != 0) {
            t = nodes.remove();
            System.out.print(t.data + "\t");
            if (++i == 2 << n || isFirst) {
                i = 0;
                n = isFirst ? n : n + 1;
                isFirst = false;
                System.out.println();
            }
            if (t.left != null) {
                nodes.add(t.left);
            }
            if (t.right != null) {
                nodes.add(t.right);
            }
        }
        System.out.println();
    }
    /**
     * 按层级显示一棵二叉树，带高度的二叉树
     * @param node 二叉树的根节点
     */
    public void show2(TreeNode<Integer> node) {
        ArrayList<TreeNode> nodes = new ArrayList<TreeNode>();
        TreeNode<Integer> t;
        nodes.add(0, node);
        int size = nodes.size();
        while (size != 0) {
            t = nodes.remove(0);
            if (t.left != null) {
                nodes.add(t.left);
            }
            if (t.right != null) {
                nodes.add(t.right);
            }

            if ((size = nodes.size()) != 0 && t.height == nodes.get(0).height) {
                System.out.print(t.data + "\t");
            } else {
                System.out.println(t.data);
            }
        }
    }

    /**
     * 属性不带高度时，根据根节点判断高度
     * @param tree 根节点
     * @return  树的高度
     */
    private int getHeightRecursion(TreeNode tree) {
        if (tree == null) {
            return 0;
        }
        int left = getHeightRecursion(tree.left);
        int right = getHeightRecursion(tree.right);
        return (left > right ? left : right) + 1;
    }
}