public class AvlTreeNode {

    int value;
    int bf;
    AvlTreeNode leftChild;
    AvlTreeNode rightChild;

    public AvlTreeNode(int value) {
        this.value = value;
        bf = 0;
    }

    /**
     * 添加子节点

     * @param subNode
     */
    public void addNode(AvlTreeNode subNode) {

        if(subNode.value <= this.value) {
            // 在左子树上添加新节点
            if(leftChild == null) {
                leftChild = subNode;
            } else {
                leftChild.addNode(subNode);
            }
        } else {
            // 在右子树上添加新节点
            if(rightChild == null) {
                rightChild = subNode;
            } else {
                rightChild.addNode(subNode);
            }
        }

        // 平衡因子 > 1 则触发旋转
        if(Math.abs(calBf()) > 1) {
            rotate();
        }
    }

    /**
     * 计算节点平衡因子(右子树高 - 左子树高)
     * @return
     */
    public int calBf() {
        int leftDeep = 0;
        int rightDeep = 0;
        if(null != leftChild) {
            leftDeep = leftChild.getSubDeep();
        }

        if(null != rightChild) {
            rightDeep = rightChild.getSubDeep();
        }
        this.bf = rightDeep - leftDeep;
        return this.bf;
    }

    public void rotate() {
        if (-2 == this.bf) {
            if(-1 == leftChild.calBf()) {
                // 直接右旋
                rightRotate();
            } else {

                // 先左旋
                leftChild.leftRotate();

                // 再右旋
                rightRotate();
            }
        } else if (2 == this.bf) {
            if(1 == rightChild.calBf()) {
                // 直接右旋
                leftRotate();
            } else {
                // 先左旋
                rightChild.rightRotate();

                // 再右旋
                leftRotate();
            }
        }

    }

    /**
     * 右旋
     */
    public void rightRotate() {
        // 克隆当前节点(顶节点)后面右旋, 当前节点降级为中间节点
        AvlTreeNode tmpNode = new AvlTreeNode(this.value);

        // 废弃中间节点, 当前节点替换原中间节点
        value = leftChild.value;

        // 将原中间节点的原右子树嫁接到右旋节点的左子树上
        tmpNode.leftChild = leftChild.rightChild;

        // 右旋节点的左子树保持不变
        tmpNode.rightChild = rightChild;

        // 将原中间节点的左子树嫁接到当前顶节点的左子树
        leftChild = leftChild.leftChild;

        // 右旋顶端节点
        rightChild = tmpNode;
    }


    /**
     * 左旋
     */
    public void leftRotate() {
        // 克隆当前节点(顶节点)后面右旋, 当前节点降级为中间节点
        AvlTreeNode tmpNode = new AvlTreeNode(this.value);

        // 废弃原中间节点, 当前节点替换中间节点
        value = rightChild.value;

        // 将原中间节点的左子树调整到左旋节点的右子树上
        tmpNode.rightChild = rightChild.leftChild;

        // 左旋节点的左子树保持不变
        tmpNode.leftChild = leftChild;

        // 将原中间节点的右子树嫁接到当前顶节点的左子树
        rightChild = rightChild.rightChild;

        // 左旋顶端节点
        leftChild = tmpNode;
    }

    /**
     * 获取子树深度
     * @return
     */
    public int getSubDeep() {
        int leftDeep = 0;
        int rightDeep = 0;
        if(leftChild != null) {
            leftDeep = leftChild.getSubDeep();
        }
        if(rightChild != null) {
            rightDeep = rightChild.getSubDeep();
        }
        int subDeep = leftDeep >= rightDeep ? leftDeep : rightDeep;
        return subDeep + 1;
    }

    /**
     * 前序遍历
     */
    public void print() {
        if(leftChild != null) {
            leftChild.print();
        }

        System.out.println("value: " + value + " bf: " + calBf());

        if(rightChild != null) {
            rightChild.print();
        }
    }
}

public class AvlTree {
    AvlTreeNode rootNode = null;

    public void addNode(AvlTreeNode node) {
        if(null == rootNode) {
            rootNode = node;
            return;
        }
        rootNode.addNode(node);
    }

    /**
     * 前序遍历
     */
    public void print() {
        rootNode.print();
    }

}

public class TreeTest {

    public static void main(String[] args) {
        AvlTree tree = new AvlTree();

        // 先左旋 后右旋
        tree.addNode(new AvlTreeNode(20));
        tree.addNode(new AvlTreeNode(10));
        tree.addNode(new AvlTreeNode(5));
        tree.addNode(new AvlTreeNode(30));
        tree.addNode(new AvlTreeNode(40));
        tree.addNode(new AvlTreeNode(25));

        tree.print();
    }
}