1. 簡(jiǎn)介

AVL樹得名于它的發(fā)明者---前蘇聯(lián)的數(shù)學(xué)家G.M. Adelson-Velsky 和 E.M. Landis，他們?cè)?1962 年的論文 "An algorithm for the organization of information" 中發(fā)表了它。

2. 定義

AVL樹其實(shí)是一棵高度平衡的二叉搜索樹，它是依靠平衡因子來(lái)維持樹的高度。

• 對(duì)于每個(gè)結(jié)點(diǎn)來(lái)說(shuō)，它的左右子樹高度差的絕對(duì)值（平衡因子）不會(huì)超過(guò)1。
• 它具有和二叉搜索樹一樣的性質(zhì)，也就是說(shuō)除了二叉搜索樹中那些會(huì)改變樹的高度的操作（插入，刪除），其他的操作都可以用在AVL樹中。

3. 實(shí)現(xiàn)

因?yàn)锳VL樹除了插入，刪除這些可能改變樹高度的操作之外，其他操作的與二叉搜索樹無(wú)異，所以這里只講插入和刪除操作。

• 每個(gè)葉子結(jié)點(diǎn)的高度都為1
• 每個(gè)結(jié)點(diǎn)都有高度，其高度為左右孩子中最高孩子的高度加上1
• 每個(gè)結(jié)點(diǎn)的高度差為左子樹的高度減去右子樹的高度
• 每當(dāng)插入或刪除一個(gè)結(jié)點(diǎn)后，可能導(dǎo)致某個(gè)結(jié)點(diǎn)的平衡因子超過(guò)1，這時(shí)候就需要對(duì)以這個(gè)結(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)操作來(lái)維持平衡。

旋轉(zhuǎn)操作：

1. 左左旋轉(zhuǎn)：

需要進(jìn)行左左旋轉(zhuǎn)

左左旋轉(zhuǎn)后

//左左旋轉(zhuǎn)
private Node rotationLeft(Node node){
        Node x = node.left;
        node.left = x.right;
        x.right = node;
        updateHeight(node);
        return x;
    }

2. 右右旋轉(zhuǎn)：

需要進(jìn)行右右旋轉(zhuǎn)

右右旋轉(zhuǎn)后

//右右旋轉(zhuǎn)
    private Node rotationRight(Node node){
        Node x = node.right;
        node.right = x.left;
        x.left = node;
        updateHeight(node);
        return x;
    }

3. 右左旋轉(zhuǎn)：

需要進(jìn)行右左旋轉(zhuǎn)

右左旋轉(zhuǎn)后

//右左旋轉(zhuǎn)
    private Node rotationRightLeft(Node node){
        node.right = rotationLeft(node.right);
        updateHeight(node.right);
        return rotationRight(node);
    }

4.左右旋轉(zhuǎn)：

image.png

左右旋轉(zhuǎn)后

//左右旋轉(zhuǎn)
private Node rotationLeftRight(Node node){
        node.left = rotationRight(node.left);
        updateHeight(node.left);
        return rotationLeft(node);
    }

4. 時(shí)間復(fù)雜度

由于AVL樹是一個(gè)高度平衡的二叉搜索樹，所以樹的高度幾乎是lgN，所以無(wú)論查找，插入還是刪除操作最壞情況的時(shí)間復(fù)雜度為O(lgN)。

5. 代碼實(shí)現(xiàn)

其中的插入刪除操作都是用遞歸來(lái)實(shí)現(xiàn)的

import java.util.*;

public class AVL <Key extends Comparable<Key>, 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;
    }

    //左右旋轉(zhuǎn)
    private Node rotationLeftRight(Node node){
        node.left = rotationRight(node.left);
        updateHeight(node.left);
        return rotationLeft(node);
    }

    //右左旋轉(zhuǎn)
    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<Key> keySet){
        if (node == null)
            return;
        inorderTraverse(node.left, keySet);
        keySet.add(node.key);
        inorderTraverse(node.right, keySet);
    }

    //返回一個(gè)把鍵從小到大排序的迭代器
    public Iterable<Key> keySet(){
        Set<Key> keySet = new TreeSet<>();
        inorderTraverse(root, keySet);
        return keySet;
    }




    public static void main(String[] args){
        AVL<Integer, String> 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("符號(hào)表的大?。? + tree.size());
    }

}