AVL Map & Set

由 AVL 实现的 Map 映射(或称字典)和 Set 集合

Map的实现

Map 的实现有多种方式，最简单的就是BST, 还有 AVL, 红黑树，后面章节将会详解。

为了增强代码的复用性和解耦，我们不从头实现一个 Map。而是定义一个 Map 的接口, BST, AVL , 红黑树去实现这个接口即可。而事实上，通过我们上一节所学的 AVL 来实现一个 Map 是非常简单的。

public interface IMap<K,V> {

    void add(K key, V value);
    V remove(K key);
    boolean contains(K key);
    V get(K key);
    void set(K key, V newValue);
    int getSize();
    boolean isEmpty();
}

随后定义我们的 AVLMap:

public class AVLMap<K extends  Comparable<K>, V> implements IMap<K,V> {
    private AVLTree<K,V> avl;

    public AVLMap(){
        avl=new AVLTree<>();
    }

    @Override
    public void add(K key, V value) {
        avl.add(key, value);
    }

    @Override
    public V remove(K key) {
        return avl.remove(key);
    }

    @Override
    public boolean contains(K key) {
        return avl.contains(key);
    }

    @Override
    public V get(K key) {
        return avl.get(key);
    }

    @Override
    public void set(K key, V newValue) {
        avl.set(key,newValue);
    }

    @Override
    public int getSize() {
        return avl.getSize();
    }

    @Override
    public boolean isEmpty() {
        return avl.isEmpty();
    }
}

可以看出，所有AVLMap的操作, 都可以直接调用 BST 的方法进行实现。

测试一下我们的AVLMap

定义一个AVLMapTest，我们利用一个文件处理类FileOperation读取一本英文书，然后将里面的英文单词放入BSTMap里面，若单词存在，则value+1，否则新建一个节点 key 为单词，value为1。最后统计全过程用时。我们特意增加了一个对比，拿BST和AVL做对比。

public class AVLMapTest {
    public static void main(String[] args) {
        ArrayList<String> words  =new ArrayList<>();
        FileOperation.readFile("./pride-and-prejudice.txt",words );
        System.out.println("Total words : "+ words .size());

        //测试极端情况,BSTMap退化成链表,AVLMap依然稳定
        //Collections.sort(words);

        AVLMap<String,Integer> avlMap = new AVLMap<>();
        BSTMap<String,Integer> bstMap= new BSTMap<>();


        //测试AVL性能
        long startTime=System.nanoTime();

        for (String word :words){
            if (avlMap.contains(word))
                avlMap.set(word, avlMap.get(word)+1);
            else
                avlMap.add(word,1);
        }

        for (String word :words){
           avlMap.remove(word);
        }



        long endTime=System.nanoTime();
        double time=(endTime-startTime)/1000000000.0;
        System.out.println("AVL Map time : "+ time+" s.");


        //测试BST 性能
        startTime=System.nanoTime();

        for (String word :words){
            if (bstMap.contains(word))
                bstMap.set(word, bstMap.get(word)+1);
            else
                bstMap.add(word,1);
        }

        endTime=System.nanoTime();
        time=(endTime-startTime)/1000000000.0;
        System.out.println("BST Map time : "+ time+" s.");

    }
}

输出结果:

Total words : 122758
AVL Map time : 0.1474229 s.
BST Map time : 0.1185719 s.

是不是很意外，我们费了这么大的力气进行维护平衡，到头来竟然性能不如BST。这是为什么呢？

这是因为AVL维护平衡的过程需要一定的性能开销。对于完全随机的数据，BST性能已经足够好了，AVL额外的平衡维护是一种负担。

那我们还要AVL做什么呢？

AVL的优势在于时时刻刻维护树的平衡，尤其是对于完全有序或是近似有序的数据，AVL的时间复杂度都趋于稳定，而不像BST。对于完全有序的数据, 可以想象BST 的树型结构会退化成一个链表结构，导致时间复杂度越级成O(N)。另外AVL在查询的时候性能非常稳定，因为整一棵树足够的平衡。

我们可以将上面的这一句代码注释掉

Collections.sort(words);

这句代码会对数据进行排序，随后加入BST, AVL的数据都是完全有序的了，我们再来观察运行结果。

Total words : 122758
AVL Map time : 0.1021732 s.
BST Map time : 12.6293168 s.

我们可以看到BST的时间增加了100多倍，而AVL时间依然稳定，几乎不变。这就是AVL的优势！

AVLSet

大家可以参考BSTSet的写法和AVLMap的对比测试，自己来写这一部分代码。代码非常的简单，我这里就不演示了。也可以访问我的 github代码仓库。大家加油！