1 package 查找;
2
3 import java.util.ArrayList;
4 import java.util.List;
5
6 public class BST<Key extends Comparable<Key>, Value> {
7 private class Node {
8 private Key key; // 键
9 private Value value;// 值
10 private Node left, right; // 指向子树的链接
11 private int n; // 以该节点为根的子树中的节点总数
12
13 public Node(Key key, Value val, int n) {
14 this.key = key;
15 this.value = val;
16 this.n = n;
17 }
18 }
19
20 private Node root;
21
22 public int size() {
23 return size(root);
24 }
25
26 private int size(Node x) {
27 if (x == null)
28 return 0;
29 else
30 return x.n;
31 }
32
33 /**
34 * 如果树是空的，则查找未命中 如果被查找的键小于根节点，则在左子树中继续查找 如果被查找的键大于根节点，则在右子树中继续查找
35 * 如果被查找的键和根节点的键相等，查找命中
36 *
37 * @param key
38 * @return
39 */
40 public Value get(Key key) {
41 return get(root, key);
42 }
43
44 private Value get(Node x, Key key) {
45 if (x == null)
46 return null;
47 int cmp = key.compareTo(x.key);
48 if (cmp < 0)
49 return get(x.left, key);
50 else if (cmp > 0)
51 return get(x.right, key);
52 else
53 return x.value;
54 }
55
56 /**
57 * 二叉查找树的一个很重要的特性就是插入的实现难度和查找差不多。
58 * 当查找到一个不存在与树中的节点（null）时，new 新节点，并将上一路径指向该节点
59 *
60 * @param key
61 * @param val
62 */
63 public void put(Key key, Value val) {
64 root = put(root, key, val);
65 }
66
67 private Node put(Node x, Key key, Value val) {
68 if (x == null)
69 return new Node(key, val, 1);
70 int cmp = key.compareTo(x.key);
71 if (cmp < 0)
72 x.left = put(x.left, key, val);
73 else if (cmp > 0)
74 x.right = put(x.right, key, val);
75 else
76 x.value = val;
77 x.n = 1 + size(x.left) + size(x.right); // 要及时更新节点的子树数量
78 return x;
79 }
80
81 public Key min() {
82 return min(root).key;
83 }
84
85 private Node min(Node x) {
86 if (x.left == null)
87 return x;
88 return min(x.left);
89 }
90
91 public Key max() {
92 return max(root).key;
93 }
94
95 private Node max(Node x) {
96 if (x.right == null)
97 return x;
98 return max(x.right);
99 }
100
101 /**
102 * 向下取整：找出小于等于该键的最大键
103 *
104 * @param key
105 * @return
106 */
107 public Key floor(Key key) {
108 Node x = floor(root, key);
109 if (x == null)
110 return null;
111 else
112 return x.key;
113 }
114
115 /**
116 * 如果给定的键key小于二叉查找树的根节点的键，那么小于等于key的最大键一定出现在根节点的左子树中
117 * 如果给定的键key大于二叉查找树的根节点，那么只有当根节点右子树中存在大于等于key的节点时，
118 * 小于等于key的最大键才会出现在右子树中，否则根节点就是小于等于key的最大键
119 *
120 * @param x
121 * @param key
122 * @return
123 */
124 private Node floor(Node x, Key key) {
125 if (x == null)
126 return null;
127 int cmp = key.compareTo(x.key);
128 if (cmp == 0)
129 return x;
130 else if (cmp < 0)
131 return floor(x.left, key);
132 else {
133 Node t = floor(x.right, key);
134 if (t == null)
135 return x;
136 else
137 return t;
138 }
139 }
140
141 /**
142 * 向上取整：找出大于等于该键的最小键
143 *
144 * @param key
145 * @return
146 */
147 public Key ceiling(Key key) {
148 Node x = ceiling(root, key);
149 if (x == null)
150 return null;
151 else
152 return x.key;
153 }
154
155 /**
156 * 如果给定的键key大于二叉查找树的根节点的键，那么大于等于key的最小键一定出现在根节点的右子树中
157 * 如果给定的键key小于二叉查找树的根节点，那么只有当根节点左子树中存在大于等于key的节点时，
158 * 大于等于key的最小键才会出现在左子树中，否则根节点就是大于等于key的最小键
159 *
160 * @param x
161 * @param key
162 * @return
163 */
164 private Node ceiling(Node x, Key key) {
165 if (x == null)
166 return null;
167 int cmp = key.compareTo(x.key);
168 if (cmp == 0)
169 return x;
170 else if (cmp > 0) {
171 return ceiling(x.right, key);
172 } else {
173 Node t = floor(x.left, key);
174 if (t == null)
175 return x;
176 else
177 return t;
178 }
179 }
180
181 /**
182 * 选择排名为k的节点
183 *
184 * @param k
185 * @return
186 */
187 public Key select(int k) {
188 return select(root, k).key;
189 }
190
191 private Node select(Node x, int k) {
192 if (x == null)
193 return null;
194 int t = size(x.left);
195 if (t > k)
196 return select(x.left, k);
197 else if (t < k)
198 return select(x.right, k - t - 1);// 根节点也要排除掉
199 else
200 return x;
201 }
202
203 /**
204 * 查找给定键值的排名
205 *
206 * @param key
207 * @return
208 */
209 public int rank(Key key) {
210 return rank(key, root);
211 }
212
213 private int rank(Key key, Node x) {
214 if (x == null)
215 return 0;
216 int cmp = key.compareTo(x.key);
217 if (cmp < 0)
218 return rank(key, x.left);
219 else if (cmp > 0)
220 return 1 + size(x.left) + rank(key, x.right);
221 else
222 return size(x.left);
223 }
224 /**
225 * 删除最小键值对
226 */
227 public void deleteMin(){
228 root = deleteMin(root);
229 }
230 /**
231 * 不断深入根节点的左子树直到遇见一个空链接，然后将指向该节点的链接指向该结点的右子树
232 * 此时已经没有任何链接指向要被删除的结点，因此它会被垃圾收集器清理掉
233 * @param x
234 * @return
235 */
236 private Node deleteMin(Node x){
237 if(x.left == null) return x.right;
238 x.left = deleteMin(x.left);
239 x.n = 1 + size(x.left)+size(x.right);
240 return x;
241 }
242
243 public void deleteMax(){
244 root = deleteMax(root);
245 }
246 private Node deleteMax(Node x){
247 if(x.right == null ) return x.left;
248 x.right = deleteMax(x.right);
249 x.n = size(x.left)+size(x.right) + 1;
250 return x;
251 }
252
253 public void delete(Key key){
254 root = delete(root,key);
255 }
256 private Node delete(Node x, Key key){
257 if(x == null) return null;
258 int cmp = key.compareTo(x.key);
259 if(cmp < 0) x.left = delete(x.left,key);
260 else if(cmp > 0) x.right = delete(x.right,key);
261 else{
262 if(x.right == null) return x.left;
263 if(x.left == null ) return x.right;
264 /**
265 * 如果被删除节点有两个子树，将被删除节点暂记为t
266 * 从t的右子树中选取最小的节点x，将这个节点x的左子树设为t的左子树
267 * 这个节点x的右子树设为t的右子树中删除了最小节点的子树，这样就成功替换了t的位置
268 */
269 Node t = x;
270 x = min(t.right);
271 x.right = deleteMin(t.right);
272 x.left = t.left;
273 }
274 x.n = size(x.left) + size(x.right) +1;
275 return x;
276 }
277
278 public String toString(){
279 StringBuilder sb = new StringBuilder();
280 toString(root,sb);
281 sb.deleteCharAt(sb.length()-1);
282 return sb.toString();
283 }
284 private void toString(Node x, StringBuilder sb){
285 if(x == null ) return;
286 toString(x.left,sb);
287 sb.append("<"+x.key+","+x.value+">,");
288 toString(x.right,sb);
289 }
290
291 public List<Key> keys(){
292 return keys(min(),max());
293 }
294 public List<Key> keys(Key lo, Key hi){
295 List<Key> list = new ArrayList<Key>();
296 keys(root, list, lo, hi);
297 return list;
298 }
299 private void keys(Node x, List<Key> list, Key lo, Key hi){
300 if(x == null) return;
301 int cmplo = lo.compareTo(x.key);
302 int cmphi = hi.compareTo(x.key);
303 if(cmplo < 0 ) keys(x.left,list,lo,hi);
304 if(cmplo <= 0 && cmphi >= 0) list.add(x.key);
305 if(cmphi > 0 ) keys(x.right,list,lo,hi);
306 }
307 public static void main(String[] args){
308 BST<Integer,String> bst = new BST<Integer,String>();
309 bst.put(5, "e");
310 bst.put(1, "a");
311 bst.put(4, "d");
312 bst.put(9, "i");
313 bst.put(10, "j");
314 bst.put(2, "b");
315 bst.put(7, "g");
316 bst.put(3, "c");
317 bst.put(8, "h");
318 bst.put(6, "f");
319 List<Integer> keys = bst.keys();
320 for(int key : keys){
321 System.out.print("<"+key+","+bst.get(key)+">,");
322 }
323 System.out.println();
324 bst.deleteMin();
325 System.out.println(bst.toString());
326 bst.deleteMax();
327 System.out.println(bst.toString());
328 bst.delete(7);
329 System.out.println(bst.toString());
330 }
331 }
树还是应该做成可视化的方便查看和调试，后续我将更新一个可视化的生成图的版本出来，恩，一定要记得这件事