AVL tree

1.定义

对于树中的任意一个节点，它的左子树和右子树的高度差(平衡因子balance factor)不超过1
平衡二叉树的高度和节点数量是O(logn)级别的
改进bst中可能会退化成链表的性质

2.目标

自平衡，减少树高

例子

3-1.基本操作

要完成一个AVL Tree，需要下面几个类，变量和函数

类：Node
私有变量：root，size
基本：getSize，isEmpty
基础操作：insert，search（get，set，contains），remove
判断有效性：isBST，isBalancedTree
旋转操作：LL，RR，LR，RL

3-2.LL, RR, LR, RL

AVL和BST最大的区别在于在insert节点时需要计算当前的balance factor，然后判断是否为LL，RR，LR，RL中的任意一种，进行旋转后再返回。

LL的意思: 当前节点的BF值>1且它的左节点BF>1。RR就是BF都小于1，LR，RL同理。

照着旋转的定义(图)写，L需要rightRotate，R需要leftRotate:

private Node rightRotate(Node y) {
    Node x = y.left;
    Node newLeft = x.right;

    x.right = y;
    y.left = newLeft;

    // update height of y, x
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

    return x;
}

private Node leftRotate(Node y) {
    Node x = y.right;
    Node newRight = x.left;

    x.left = y;
    y.right = newRight;

    // update height of y, x
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

    return x;
}

Code

https://github.com/nyannko/leetcode-java/blob/master/src/ds/AVLTree/AVLTree.java

AVLTree