BST Map & Set

由二分搜索树实现的 Map 映射(或称字典)和 Set集合

什么是Map?

我们完全可以把Map当作生活中的字典。查字典需要指定一个查询的单词，然后根据这个单词去字典里面查找对应的解释。Map 里面的key 就是查询的单词, 单词对应的解释 就是key对应的value。一本字典不可能在两个地方查到同一个单词, Map 也是如此，key不允许有重复。

Map 的主要功能就是 根据 key 去查询 对应的 value, 也应支持 增, 删, 改, 查等操作。

Map的实现

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

为了增强代码的复用性和解耦，我们不从头实现一个 Map。而是定义一个 Map 的接口, BST, AVL , 红黑树去实现这个接口即可。而事实上，通过我们上一节所学的 BST 来实现一个 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();
}

随后定义我们的BSTMap:

public class BSTMap <K extends  Comparable<K>, V> implements IMap<K,V> {
    private BST<K,V> bst;

    public BSTMap(){
        bst=new BST<>();
    }

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

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

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

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

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

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

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

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

测试一下我们的BSTMap

定义一个BSTMapTest，我们利用一个文件处理类FileOperation读取一本英文书，然后将里面的英文单词放入BSTMap里面，若单词存在，则value+1，否则新建一个节点 key 为单词，value为1。最后统计全过程用时。

public class BSTMapTest {
    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退化成链表
        //Collections.sort(words);


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

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

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

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

    }
}

输出结果

Total words : 122758
BST Map time : 0.092118 s.

什么是Set?

Set与Map类似，只不过每一个节点的value为NULL。我们可以把数据结构中的Set近似地理解为高中数学的集合，只不过Set内部的节点有一定顺序。

Set 的主要功能就是 查询 key 是否存在, 也应支持 增, 删, 改, 查等操作。

Set的实现

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

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

public interface ISet<E>{

    void add(E e);
    void remove(E e);
    boolean contains(E e);
    boolean isEmpty();
    int getSize();

}

随后定义我们的BSTSet

public class BSTSet <E extends Comparable<E>>  implements ISet<E> {
    private  BST<E,Object> bst;

    public BSTSet(){
        bst=new BST<>();
    }

    @Override
    public void add(E e) {
        bst.add(e,null);
    }

    @Override
    public void remove(E e) {
        bst.remove(e);
    }

    @Override
    public boolean contains(E e) {
        return bst.contains(e);
    }

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

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

测试一下我们的BSTSet

定义一个BSTSetTest，我们利用一个文件处理类FileOperation读取一本英文书，然后将里面的英文单词放入BSTSet里面，若单词存在，则跳过，否则新建一个节点 key 为单词。最后统计全过程用时。

public class BSTSetTest {
    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());

        //测试极端情况,BSTSet退化成链表
        //Collections.sort(words);

        BSTSet<String> bstSet=new BSTSet<>();

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

        for (String word :words){
            if (!bstSet.contains(word))
                bstSet.add(word );
        }

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

    }
}

输出结果:

Total words : 122758
BST Set time : 0.0512552 s.

可以看出 单词个数统计结果完全相同, 但BSTSet 用时较少，这是因为Set无需处理节点的value。