Lab6 - BSTMap
实现以二叉搜索树为底层的Map
- 该类需要有两个泛型K, V表示键值对
- 其中键K要是Comparable的实现
创建类
创建实现文件并修改开头
1
| public class BSTMap<K extends Comparable<K>, V> implements Map61B<K, V>
|
即BSTMap要是Map61B的实现，且泛型K是Comparable的extends
因为要实现一个二叉搜索树，故我们需要嵌套一个节点类用于储存数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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;
}
}
|
同时写构造函数
1
2
3
4
5
6
| public BSTMap(){
root = null;
}
...
private BSTNode root;
private int size = 0;
|
size()与clear()
1
2
3
4
5
6
7
8
9
10
| @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类的作用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| @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;
}
return N;
}
|
get()
同理，我们创建一个递归辅助函数，通过递归方法遍历左右子树，将给定的key与途径的节点比较
- 若小于则向左子树递归查找
- 若大于则向右子树递归查找
- 若相等则说明找到对应键，返回对应值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
| @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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| @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并取出所有键，而若要实现按序，我们采用中序遍历，这样可以保证比节点小的先放入，比节点大的后放入，实现有序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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的性质又能实现删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| @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;
}
|
