1. 简介

AVL树得名于它的发明者---前苏联的数学家G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 "An algorithm for the organization of information" 中发表了它。

2. 定义

AVL树其实是一棵高度平衡的二叉搜索树，它是依靠平衡因子来维持树的高度。

对于每个结点来说，它的左右子树高度差的绝对值（平衡因子）不会超过1。

它具有和二叉搜索树一样的性质，也就是说除了二叉搜索树中那些会改变树的高度的操作（插入，删除），其他的操作都可以用在AVL树中。

3. 实现

因为AVL树除了插入，删除这些可能改变树高度的操作之外，其他操作的与二叉搜索树无异，所以这里只讲插入和删除操作。

每个叶子结点的高度都为1

每个结点都有高度，其高度为左右孩子中最高孩子的高度加上1

每个结点的高度差为左子树的高度减去右子树的高度

每当插入或删除一个结点后，可能导致某个结点的平衡因子超过1，这时候就需要对以这个结点进行旋转操作来维持平衡。

旋转操作：

1. 左左旋转：

如上图，当插入一个

0001这个结点后，导致

0003的平衡因子超过1，此时

0003结点需要通过左左旋转来维持平衡。因为破坏平衡的结点在发现不平衡的结点的左孩子的左孩子上，取名左左旋转，旋转后的结果如下图：

代码实现：

//左左旋转private Node rotationLeft(Node node){        Node x = node.left;        node.left = x.right;        x.right = node;        updateHeight(node);        return x;    }复制代码

2. 右右旋转：

如上图，当插入一个

0003这个结点后，导致

0001的平衡因子超过1，此时

0003结点需要通过右右旋转来维持平衡。因为破坏平衡的结点在发现不平衡的结点的右孩子的右孩子上，取名右右旋转，旋转后的结果如下图：

代码实现：

//右右旋转    private Node rotationRight(Node node){        Node x = node.right;        node.right = x.left;        x.left = node;        updateHeight(node);        return x;    }复制代码

3. 右左旋转：

如上图，当插入一个

0002这个结点后，导致

0001的平衡因子超过1，此时

0001结点需要通过右左旋转来维持平衡。因为破坏平衡的结点在发现不平衡的结点的右孩子的左孩子上，取名右左旋转，旋转后的结果如下图：

代码实现：

//右左旋转    private Node rotationRightLeft(Node node){        node.right = rotationLeft(node.right);        updateHeight(node.right);        return rotationRight(node);    }复制代码

4.左右旋转：

如上图，当插入一个

0002这个结点后，导致

0003的平衡因子超过1，此时

0003结点需要通过左右旋转来维持平衡。因为破坏平衡的结点在发现不平衡的结点的左孩子的右孩子上，取名左右旋转，旋转后的结果如下图：

代码实现：

//左右旋转private Node rotationLeftRight(Node node){        node.left = rotationRight(node.left);        updateHeight(node.left);        return rotationLeft(node);    }复制代码

4. 时间复杂度

由于AVL树是一个高度平衡的二叉搜索树，所以树的高度几乎是lgN，所以无论查找，插入还是删除操作最坏情况的时间复杂度为O(lgN)。

5. 代码实现

其中的插入删除操作都是用递归来实现的

import java.util.*;public class AVL 
    
     , Value>{    private class Node{        Key key;        Value value;        int height;        Node left;        Node right;        public Node(Key key, Value value, int height, Node left, Node right){            this.key = key;            this.value = value;            this.height = height;            this.left = left;            this.right = right;        }    }    private Node root;    private int size;    public int size(){        return size;    }    //获取树高度    public int height(Node node){        return node == null ? 0 : node.height;    }    //高度差    private int altitude(Node node){        return height(node.left) - height(node.right);    }    //更新树高度    private void updateHeight(Node node){        node.height = Math.max(height(node.left), height(node.right)) + 1;    }    //右旋    private Node rotationRight(Node node){        Node x = node.right;        node.right = x.left;        x.left = node;        updateHeight(node);        return x;    }    //左旋    private Node rotationLeft(Node node){        Node x = node.left;        node.left = x.right;        x.right = node;        updateHeight(node);        return x;    }    //左右旋转    private Node rotationLeftRight(Node node){        node.left = rotationRight(node.left);        updateHeight(node.left);        return rotationLeft(node);    }    //右左旋转    private Node rotationRightLeft(Node node){        node.right = rotationLeft(node.right);        updateHeight(node.right);        return rotationRight(node);    }    //平衡    private Node balance(Node node, int altitude){        if (altitude == 2)            node =  height(node.left.left) > height(node.left.right) ? rotationLeft(node) : rotationLeftRight(node);        else if (altitude == -2)            node =  height(node.right.left) > height(node.right.right) ? rotationRightLeft(node) : rotationRight(node);        updateHeight(node);        return node;    }    //插入    public void put(Key key, Value value){        root = put(key, value, root);        ++size;    }    private Node put(Key key, Value value, Node node) {        if (node == null)            return new Node(key, value, 1, null, null);        int cmp = key.compareTo(node.key);        if (cmp < 0)            node.left = put(key, value, node.left);        else if (cmp > 0)            node.right = put(key, value, node.right);        else {            node.value = value;            return node;        }        return balance(node, altitude(node));    }    private Node max(Node node){        if (node == null)            return null;        while (node.right != null)            node = node.right;        return node;    }    public Value max() {        return root == null ? null : max(root).value;    }    public void deleteMax(){        if (root != null) {            root = deleteMax(root);            --size;        }    }    private Node deleteMax(Node node){        if (node.right == null)            return node.left;        node.right = deleteMax(node.right);        return balance(node, altitude(node));}    private Node deleteMin(Node node){        if (node.left == null)            return node.right;        node.left = deleteMin(node.left);        return balance(node, altitude(node));    }    public void deleteMin(){        if (root != null) {            root = deleteMin(root);            --size;        }    }    public Value delete(Key key){        Node node = delete(key, root);        if (node != null)            return node.value;        return null;    }    private Node delete(Key key, Node node){        if (node == null)            return null;        int cmp = key.compareTo(node.key);        if (cmp < 0)            node.left = delete(key, node.left);        else if (cmp > 0)            node.right = delete(key, node.right);        else {            --size;            if (node.left == null)                return node.right;            if (node.right == null)                return node.left;            Node x = max(node.right);            node.key = x.key;            node.value = x.value;            node.right = deleteMax(node.right);        }        return balance(node, altitude(node));    }    //中序遍历    private void inorderTraverse(Node node, Set
     
       keySet){        if (node == null)            return;        inorderTraverse(node.left, keySet);        keySet.add(node.key);        inorderTraverse(node.right, keySet);    }    //返回一个把键从小到大排序的迭代器    public Iterable
      
        keySet(){        Set
       
         keySet = new TreeSet<>();        inorderTraverse(root, keySet);        return keySet;    }    public static void main(String[] args){        AVL
        
          tree = new AVL<>();        Random random = new Random();        for (int i = 0; i < 500; ++i)            tree.put(random.nextInt(), "naoko" + i);        tree.deleteMax();        tree.deleteMin();        for (int i : tree.keySet())            System.out.println(i);        System.out.println("符号表的大小：" + tree.size());    }}复制代码