平衡二叉树（AVL）

1. 首先AVL树满足是二叉排序树，并且左右输的高度的绝对值不能超过1
2. 重点：树的高度，左旋、右旋、双旋

public class AVLTree {

    public static void main(String[] args) {
        //int[] array = {4, 3, 6, 5, 7, 8};
        //int[] array = {10, 8, 12, 7, 9, 6};
        int[] array = {10, 7, 11, 6, 8, 9};

        AVLTree avlTree = new AVLTree();
        for (int i = 0; i < array.length; i++) {
            avlTree.add(array[i]);
        }
        avlTree.showHeight();
    }

    public void showHeight() {
        System.out.println("AVL---HEIGHT---" + height());
        System.out.println("AVL---LEFT-HEIGHT---" + leftHeight());
        System.out.println("AVL---RIGHT-HEIGHT---" + rightHeight());
    }

    public Node root;

    public void add(int value) {
        Node curNode = new Node(value);
        if (root == null) {
            root = curNode;
            return;
        }
        root.add(curNode);
    }

    public int height() {
        return root.height();
    }

    public int leftHeight() {
        return root.leftHeight();
    }

    public int rightHeight() {
        return root.rightHeight();
    }

    public void leftRotate() {
        root.leftRotate();
    }
}


class Node {

    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    public int height() {
        return Math.max((this.left == null ? 0 : this.left.height()),
                (this.right == null ? 0 : this.right.height())) + 1;
    }

    public int leftHeight() {
        if (this.left == null) {
            return 0;
        }
        return this.left.height();
    }

    public int rightHeight() {
        if (this.right == null) {
            return 0;
        }
        return this.right.height();
    }

    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }

        if (rightHeight() - leftHeight() > 1) {
            if (this.right != null && this.right.leftHeight() > this.left.rightHeight()) {
                this.right.rightRotate();
            }
            leftRotate();
            return;
        }

        if (leftHeight() - rightHeight() > 1) {

            if (this.left != null && this.left.rightHeight() > this.left.leftHeight()) {
                this.left.leftRotate();
            }

            rightRotate();
            return;
        }
    }

    public void preOrder() {
        System.out.println(this.value);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.print(this.value + " ");
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    public void leftRotate() {
        Node newNode = new Node(this.value);
        newNode.left = this.left;
        newNode.right = this.right.left;
        this.value = this.right.value;
        this.left = newNode;
        this.right = this.right.right;
    }

    public void rightRotate() {
        Node newNode = new Node(this.value);
        newNode.left = this.right;
        newNode.right = this.left.right;
        this.value = this.left.value;
        this.left = this.left.left;
        this.right = newNode;
    }
    
    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("Node{");
        sb.append("value=").append(value);
        sb.append('}');
        return sb.toString();
    }
}