Lab6 - BSTMap

实现以二叉搜索树为底层的Map

该类需要有两个泛型K, V表示键值对
其中键K要是Comparable的实现

创建类

创建实现文件并修改开头

public class BSTMap<K extends Comparable<K>, V> implements Map61B<K, V>

即BSTMap要是Map61B的实现，且泛型K是Comparable的extends

因为要实现一个二叉搜索树，故我们需要嵌套一个节点类用于储存数据

private class BSTNode{
    K key;
    V val;
    BSTNode l_child;
    BSTNode r_child;
    int size;
    BSTNode(K k, V v){
        key = k;
        val = v;
        l_child = null;
        r_child = null;
        size = 0;
    }
}

同时写构造函数

public BSTMap(){
    root = null;
}
...
private BSTNode root;
private int size = 0;

size()与clear()

@Override
public int size() {
    return size;
}

@Override
public void clear() {
    size = 0;
    root = null;
}

size即返回树的size，clear将树根置为null，且要把size置零

put()

实现放入节点

这里我们需要在根节点的基础上使用递归向下添加节点，具体可以创建一个递归辅助函数，传入每次准备插入的节点进行递归

若传入节点为空节点，则创建一个新节点并传入键值，并将size+1表示多一个节点
若不为空，则比较当前节点的键与传入的键的大小
- 若小于，则按照BST的性质应该作为该节点的左子树，因此向左递归
- 若大于，则按照BST的性质应该作为该节点的右子树，因此向右递归
- 若相等，则更新键处的值为最新
返回更新的节点

注意：这里的键不能直接比较，需要使用CompareTo函数，这也是继承Comparable类的作用

@Override
public void put(K key, V value) {
    root = put_assist(key, value, root);
}

private BSTNode put_assist(K key, V value, BSTNode N){
    if (N==null){
        size++;
        return new BSTNode(key, value);
    }
    if (key.compareTo(N.key)<0){
        N.l_child = put_assist(key, value, N.l_child);
    }
    else if (key.compareTo(N.key)>0){
        N.r_child = put_assist(key, value, N.r_child);

    }
    else{
        N.val = value;
    }
    //N.size = 1+ size(N.l_child) +size(N.r_child);
    return N;
}

get()

同理，我们创建一个递归辅助函数，通过递归方法遍历左右子树，将给定的key与途径的节点比较

若小于则向左子树递归查找
若大于则向右子树递归查找
若相等则说明找到对应键，返回对应值即可

@Override
public V get(K key) {
    return get_assist(key, root);
}

private V get_assist(K key, BSTNode N){
    if (N==null) {
        return null;
    }
    if (key.compareTo(N.key)<0) return get_assist(key, N.l_child);
    else if (key.compareTo(N.key)>0) return get_assist(key, N.r_child);
    else return N.val;
}

ContainsKey()

判断map中是否含有指定的键

一开始的想法是直接调用get，但是问题是是否包含键与值没有关系，当键存在而值为空时，get返回的仍为null，会造成误判

故我们仿照get重新写一个辅助函数，但是返回布尔值，若键为空返回false，若找到对应键返回true

@Override
public boolean containsKey(K key) {
    return contains(key, root);
}

private boolean contains(K key, BSTNode N){
    if (N==null){
        return false;
    }
    if (key.compareTo(N.key)<0) return contains(key, N.l_child);
    else if (key.compareTo(N.key)>0) return contains(key, N.r_child);
    else return true;

}

Iterator()

实现按序迭代键的功能

我们可以单独把键存入一个列表，并且返回该列表自带的迭代器

这时需要一个辅助函数遍历BST并取出所有键，而若要实现按序，我们采用中序遍历，这样可以保证比节点小的先放入，比节点大的后放入，实现有序

public Iterator<K> iterator() {
    List<K> iterKeys = new ArrayList<>();
    iterMid(root, iterKeys);
    return iterKeys.iterator();
}
private void iterMid(BSTNode N, List<K> Array){
    if (N==null){
        return ;
    }
    iterMid(N.l_child, Array);
    Array.add(N.key);
    iterMid(N.r_child, Array);

}

KeySet()

暂时搁置

remove()

删除操作，仍采用递归逻辑

首先判断是否含有对应key，若没有直接返回null

若有则记录旧值，进行删除操作并返回旧值

删除通过辅助递归函数来进行：

若进入函数已经是空节点，则返回null
否则比较传入键与每个节点（注意，这里要将return的节点赋值到对应子树上，这样才能算连上）
- 小于则向左边递归
- 大于则向右边递归
- 若等于则发现待删除节点
找到后分情况进行删除
- 若本身为叶子节点，则直接置空
- 若有左孩子或有孩子，将其左孩子或右孩子直接替代当前节点即可
- 若都有，我们可以让一个辅助节点cur指向待删除节点左孩子，往下递归找到左孩子的最大节点，让要删除节点的右子树放在此时cur的右子树上，删除待删除节点，这样既能保持BST的性质又能实现删除

@Override
public V remove(K key) {
    if (!containsKey(key)){
        return null;
    }
    V oldValue = get(key);
    root = remove_assist(key, root);
    size--;
    return oldValue;
}
private BSTNode remove_assist(K key, BSTNode N){
    if (N == null) {
        return null;
    }
    if (key.compareTo(N.key)<0){
        N.l_child = remove_assist(key, N.l_child);
    }
    else if (key.compareTo(N.key)>0){
        N.r_child = remove_assist(key, N.r_child);
    }
    else if (key.compareTo(N.key)==0){
        if (N.l_child==null && N.r_child==null){
            return null;
        }
        else if (N.l_child == null){
            return N.r_child;
        }
        else if (N.r_child == null){
            return N.l_child;
        }
        else{
            BSTNode cur = N.l_child;
            while(cur.r_child!=null){
                cur = cur.r_child;
            }
            cur.r_child = N.r_child;
            return cur;
        }
    }
    return N;
}

红魔咖啡馆

【CS61B】Lab6-BSTMap