package com.rao.linkList;

/**

 * @author Srao

 * @className AvlTree

 * @date 2019/12/3 21:23

 * @package com.rao.linkList

 * @Description 二叉平衡树

 */

/**

 * 定义Avl树的节点

 */

class AvlNode{

    int data;

    AvlNode lchild;//左孩子

    AvlNode rchild;//右孩子

    int height;//当前节点所在的高度

}

/**

 * 定义平衡二叉树

 */

public class AvlTree {

    /**

     *

     * @param avlNode

     * @return 返回当前节点所在的高度

     */

    public int height(AvlNode avlNode){

        if (avlNode == null){

            return -1;

        }else {

            return avlNode.height;

        }

    }

    /**

     * 左左型，进行右旋操作

     * @param K2：非平衡二叉树的根节点，以这个点进行旋转

     * @return

     */

    public AvlNode R_Rotate(AvlNode k2){

        AvlNode k1;

        //进行旋转

        k1 = k2.lchild;

        k2.lchild = k1.rchild;

        k1.rchild = k2;

        //重新计算高度,只有一个节点时的高度为0

        //原先根节点的高度

        k2.height = Math.max(height(k2.lchild), height(k2.rchild)) + 1;

        //新根节点的高度

        k1.height = Math.max(height(k1.rchild), height(k1.rchild)) + 1;

        //返回新的根节点

        return k1;

    }

    /**

     * 右右型，进行左旋操作

     * @param k2

     * @return

     */

    public AvlNode L_Rotate(AvlNode k2){

        AvlNode k1;

        //进行旋转

        k1 = k2.rchild;

        k2.rchild = k1.lchild;

        k1.lchild = k2;

        //重新计算高度

        //原先根节点的高度

        k2.height = Math.max(height(k2.lchild), height(k2.rchild)) + 1;

        //新根节点的高度

        k1.height = Math.max(height(k1.rchild), height(k1.rchild)) + 1;

        //返回新的根节点

        return k1;

    }

    /**

     * 左右型，先进行左旋，再进行右旋

     * @param k3 非平衡树的根节点

     * @return

     */

    public AvlNode L_R_Rotate(AvlNode k3){

        //先对其左孩子进行左旋

        k3.lchild = L_Rotate(k3.lchild);

        //再进行整体右旋

        return R_Rotate(k3);

    }

    /**

     * 右左型，先进行右旋，再进行左旋

     * @param k3

     * @return

     */

    public AvlNode R_L_Rotate(AvlNode k3){

        //先对其右孩子进行右旋

        k3.rchild = R_Rotate(k3.rchild);

        //再整体左旋

        return L_Rotate(k3);

    }

    /**

     * 向平衡二叉树中插入一个数

     * @param data：要插入的数

     * @param t：二叉树的根节点

     * @return 返回新的二叉树

     */

    public AvlNode insert(int data, AvlNode t){

        //如果二叉树已经没有根节点，那么这个数就成了一个新的二叉树

        if (t == null){

            t = new AvlNode();

            t.data = data;

            t.lchild = null;

            t.rchild = null;

        }else if (data < t.data){

            //向左孩子递归插入

            t.lchild = insert(data, t.lchild);

            //进行调整，如果左孩子的高度比右孩子的高度大2

            if (height(t.lchild) - height(t.rchild) == 2){

                //左左型,右旋

                if (data < t.lchild.data){

                    t = R_Rotate(t);

                }else {//左右型，先左旋，再右旋

                    t = L_R_Rotate(t);

                }

            }

        }else if (t.data < data){

            //向右递归插入

            t.rchild = insert(data, t.rchild);

            //进行调整，如果右孩子的高度比左孩子的高度大2

            if (height(t.rchild) - height(t.lchild) == 2){

                //右右型，左旋

                if (data > t.rchild.data){

                    t = L_Rotate(t);

                }else {

                    //右左型，先右旋，再左旋

                    t = R_L_Rotate(t);

                }

            }

        }

        //重新计算树的高度

        t.height = Math.max(height(t.lchild), height(t.rchild)) + 1;

        return t;

    }

}