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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package edu.caltech.cs2.datastructures;
import edu.caltech.cs2.interfaces.*;
import java.util.Iterator;
public class BSTDictionary<K extends Comparable<K>, V> implements IDictionary<K, V> {
private static int LEFT = 0;
private static int RIGHT = 1;
protected BSTNode<K, V> root;
protected int size;
@Override
public V get(K key) {
return null;
}
@Override
public V remove(K key) {
return null;
}
@Override
public V put(K key, V value) {
return null;
}
@Override
public boolean containsKey(K key) {
return false;
}
@Override
public boolean containsValue(V value) {
return false;
}
@Override
public int size() {
return 0;
}
@Override
public ICollection<K> keySet() {
return null;
}
@Override
public ICollection<V> values() {
return null;
}
@Override
public Iterator<K> iterator() {
return null;
}
@Override
public String toString() {
if (this.root == null) {
return "{}";
}
StringBuilder contents = new StringBuilder();
IQueue<BSTNode<K, V>> nodes = new ArrayDeque<>();
BSTNode<K, V> current = this.root;
while (current != null) {
contents.append(current.key + ": " + current.value + ", ");
if (current.children[0] != null) {
nodes.enqueue(current.children[0]);
}
if (current.children[1] != null) {
nodes.enqueue(current.children[1]);
}
current = nodes.dequeue();
}
return "{" + contents.toString().substring(0, contents.length() - 2) + "}";
}
protected static class BSTNode<K, V> {
public final K key;
public final V value;
public BSTNode<K, V>[] children;
public BSTNode(K key, V value) {
this.key = key;
this.value = value;
this.children = (BSTNode<K, V>[]) new BSTNode[2];
}
public BSTNode(BSTNode<K, V> o) {
this.key = o.key;
this.value = o.value;
this.children = (BSTNode<K, V>[]) new BSTNode[2];
this.children[LEFT] = o.children[LEFT];
this.children[RIGHT] = o.children[RIGHT];
}
public boolean isLeaf() {
return this.children[LEFT] == null && this.children[RIGHT] == null;
}
public boolean hasBothChildren() {
return this.children[LEFT] != null && this.children[RIGHT] != null;
}
}
}