《算法》第三章部分程序 part 2

▶ 书中第三章部分程序，加上自己补充的代码，平衡二叉搜索树
● 平衡二叉搜索树
  1 package package01;
  2 
  3 import java.util.NoSuchElementException;
  4 import edu.princeton.cs.algs4.Queue;
  5 import edu.princeton.cs.algs4.StdIn;
  6 import edu.princeton.cs.algs4.StdOut;
  7 
  8 public class class01<Key extends Comparable<Key>, Value>
  9 {
 10     private class Node             // 二叉树节点
 11     {
 12         private Key key;
 13         private Value val;
 14         private Node left, right;
 15         private int size;          // 节点总数（包括根节点和子树）
 16 
 17         public Node(Key key, Value val, int size)
 18         {
 19             this.key = key;
 20             this.val = val;
 21             this.size = size;
 22         }
 23     }
 24 
 25     private Node root;             // 二叉树根节点
 26 
 27     public class01() {}
 28 
 29     public int size()
 30     {
 31         return size(root);
 32     }
 33 
 34     private int size(Node x)
 35     {
 36         if (x == null)
 37             return 0;
 38         return x.size;
 39     }
 40 
 41     public boolean isEmpty()
 42     {
 43         return size() == 0;
 44     }
 45 
 46     public Value get(Key key)                   // 查找
 47     {
 48         if (key == null)
 49             throw new IllegalArgumentException("
<get> key == null.
");
 50         return getKernel(root, key);
 51     }
 52 
 53     private Value getKernel(Node x, Key key)    // 查找内核，递归地向下找
 54     {
 55         if (x == null)
 56             return null;
 57         int cmp = key.compareTo(x.key);
 58         if (cmp < 0)
 59             return getKernel(x.left, key);
 60         if (cmp > 0)
 61             return getKernel(x.right, key);
 62         return x.val;
 63     }
 64 
 65     public boolean contains(Key key)            // 判断 key 是否在树中
 66     {
 67         if (key == null)
 68             throw new IllegalArgumentException("
<contains> key == null.
");
 69         return get(key) != null;
 70     }
 71 
 72     public void put(Key key, Value val)         // 插入
 73     {
 74         if (key == null)
 75             throw new IllegalArgumentException("
<put> key == null.
");
 76         if (val == null)                        // 空值插入作删除处理
 77             delete(key);
 78         else
 79             root = putKernel(root, key, val);
 80         //assert check();                         // 对树作修改时需要检查
 81     }
 82 
 83     private Node putKernel(Node x, Key key, Value val)  // 插入内核，插到适当的位置上去
 84     {
 85         if (x == null)
 86             return new Node(key, val, 1);
 87         int cmp = key.compareTo(x.key);
 88         if (cmp < 0)
 89             x.left = putKernel(x.left, key, val);
 90         else if (cmp > 0)
 91             x.right = putKernel(x.right, key, val);
 92         else
 93             x.val = val;
 94         x.size = 1 + size(x.left) + size(x.right);
 95         return x;
 96     }
 97 
 98     public void deleteMin()                         // 删除最小节点（先根序首节点）
 99     {
100         if (isEmpty())
101             throw new NoSuchElementException("
<deleteMin> underflow.
");
102         root = deleteMinKernel(root);
103         //assert check();
104     }
105 
106     private Node deleteMinKernel(Node x)            // 删除最小节点内核
107     {
108         if (x.left == null)                         // 左子树为空，返回右子树（相当于删除根节点）
109             return x.right;
110         x.left = deleteMinKernel(x.left);           // 左子树不空，继续往下找
111         x.size = size(x.left) + size(x.right) + 1;  // 重新计算输的大小
112         return x;
113     }
114 
115     public void deleteMax()                         // 删除最大节点（先根序末节点）
116     {
117         if (isEmpty())
118             throw new NoSuchElementException("
<deleteMax> underflow.
");
119         root = deleteMaxKernel(root);
120         //assert check();
121     }
122 
123     private Node deleteMaxKernel(Node x)
124     {
125         if (x.right == null)                        // 右子树为空，返回左子树（相当于删除根节点）
126             return x.left;
127         x.right = deleteMaxKernel(x.right);         // 右子树不空，继续往下找
128         x.size = size(x.left) + size(x.right) + 1;  // 重新计算输的大小
129 
130         return x;
131     }
132 
133     public void delete(Key key)                      // 删除指定 key 的节点
134     {
135         if (key == null)
136             throw new IllegalArgumentException("
<delete> key == null.
");
137         root = deleteKernel(root, key);
138         //assert check();
139     }
140 
141     private Node deleteKernel(Node x, Key key)       // 删除节点内核
142     {
143         if (x == null)
144             return null;
145         int cmp = key.compareTo(x.key);
146         if (cmp < 0)
147             x.left = deleteKernel(x.left, key);
148         else if (cmp > 0)
149             x.right = deleteKernel(x.right, key);
150         else                                        // 找到了目标键
151         {
152             if (x.right == null)                    // 右子树为空就返回左子树，左子树为空就返回右子树
153                 return x.left;
154             if (x.left == null)
155                 return x.right;
156             Node t = x;                             // 左右子树都不空，设这里中根序遍历为 x -> a -> b
157             x = min(t.right);                       // 找到 t 在中根序的下一个节点 a，赋给 x（结束后 x 的左子树一定为空）
158             x.right = deleteMinKernel(t.right);     // 删除节点 a，删除函数返回 a 的下一个节点 b，赋给 x 的右子树
159             x.left = t.left;                        // 原来的的左子树接到 x 的左子树
160         }
161         x.size = 1 + size(x.left) + size(x.right);
162         return x;
163     }
164 
165     public Key min()                                // 返回最小键
166     {
167         if (isEmpty())
168             throw new NoSuchElementException("
<delete> empty.
");
169         return minKernel(root).key;
170     }
171 
172     private Node minKernel(Node x)                  // 最小节点内核，需要递归
173     {
174         if (x.left == null)
175             return x;
176         return minKernel(x.left);
177     }
178 
179     public Key max()                               // 返回最大键
180     {
181         if (isEmpty())
182             throw new NoSuchElementException("
<max> empty.
");
183         return maxKernel(root).key;
184     }
185 
186     private Node maxKernel(Node x)                 // 最大节点内核，需要递归
187     {
188         if (x.right == null)
189             return x;
190         return maxKernel(x.right);
191     }
192 
193     public Key floor(Key key)                       // 返回不大于 key 的最大元素的键，不存在
194     {
195         if (key == null)
196             throw new IllegalArgumentException("
<floor> key == null.
");
197         if (isEmpty())
198             throw new NoSuchElementException("
<floor> empty.
");
199         Node x = floorKernel(root, key);
200         return (x == null) ? null : x.key;
201     }
202 
203     private Node floorKernel(Node x, Key key)       // floor 内核，需要递归
204     {
205         if (x == null)
206             return null;
207         int cmp = key.compareTo(x.key);
208         if (cmp == 0)
209             return x;
210         if (cmp < 0)
211             return floorKernel(x.left, key);
212         Node t = floorKernel(x.right, key);         // 目标键较大时需要递归搜索 
213         return (t == null) ? x : t;                 // 在母栈中保存了当前最好的结果 x，没有实现尾递归
214     }
215 
216     public Key floor2(Key key)                      // floor 的尾递归实现
217     {
218         return floor2Kernel(root, key, null);
219     }
220 
221     private Key floor2Kernel(Node x, Key key, Key best) // 调用时带上当前已经找到的最佳值
222     {
223         if (x == null)
224             return best;
225         int cmp = key.compareTo(x.key);
226         if (cmp == 0)
227             return x.key;
228         if (cmp < 0)
229             return floor2Kernel(x.left, key, best);
230         return floor2Kernel(x.right, key, x.key);
231     }
232 
233     public Key ceiling(Key key)                     // 返回不小于 key 的最大元素的键
234     {
235         if (key == null)
236             throw new IllegalArgumentException("
<ceiling> key == null.
");
237         if (isEmpty())
238             throw new NoSuchElementException("
<ceiling> empty.
");
239         Node x = ceilingKernel(root, key);
240         return (x == null) ? null : x.key;
241     }
242 
243     private Node ceilingKernel(Node x, Key key)     // ceiling 内核，需要递归
244     {
245         if (x == null)
246             return null;
247         int cmp = key.compareTo(x.key);
248         if (cmp == 0)
249             return x;
250         if (cmp > 0)
251             return ceilingKernel(x.right, key);
252         Node t = ceilingKernel(x.left, key);
253         return (t == null) ? x : t;
254     }
255 
256     public Key ceiling2(Key key)                    // ceiling 的尾递归实现
257     {
258         return ceiling2Kernel(root, key, null);
259     }
260 
261     private Key ceiling2Kernel(Node x, Key key, Key best)
262     {
263         if (x == null)
264             return best;
265         int cmp = key.compareTo(x.key);
266         if (cmp == 0)
267             return x.key;
268         if (cmp < 0)
269             return ceiling2Kernel(x.left, key, best);
270         return ceiling2Kernel(x.right, key, x.key);
271     }
272 
273     public Key select(int k)                        // 取出排第 k 的元素
274     {
275         if (k < 0 || k >= size())
276             throw new IllegalArgumentException("
<select> k < 0 || k >= size().
");
277         return selectKernel(root, k).key;
278     }
279 
280     private Node selectKernel(Node x, int k)        // 取元素内核，需要递归
281     {
282         if (x == null)
283             return null;
284         int t = size(x.left);                       // 树的元素数用于来计数
285         if (k < t)
286             return selectKernel(x.left, k);
287         if (k > t)
288             return selectKernel(x.right, k - t - 1);
289         return x;
290     }
291 
292     public int rank(Key key)                        // 计算键比 key 小的元素个数
293     {
294         if (key == null)
295             throw new IllegalArgumentException("
<rank> key == null.
");
296         return rankKernel(key, root);
297     }
298 
299     private int rankKernel(Key key, Node x)         // 计算函数内核，需要递归
300     {
301         if (x == null)
302             return 0;
303         int cmp = key.compareTo(x.key);
304         if (cmp < 0)
305             return rankKernel(key, x.left);
306         if (cmp > 0)
307             return 1 + size(x.left) + rankKernel(key, x.right);
308         return size(x.left);
309     }
310 
311     public Iterable<Key> keys()                     // 创建队列用于迭代器，中根序
312     {
313         if (isEmpty())
314             return new Queue<Key>();
315         Key lo = min(), hi = max();
316         if (lo == null)
317             throw new IllegalArgumentException("
<iterable> lo == null.
");
318         if (hi == null)
319             throw new IllegalArgumentException("
<iterable> hi == null.
");
320         Queue<Key> queue = new Queue<Key>();
321         keysKernel(root, queue, lo, hi);
322         return queue;
323     }
324 
325     private void keysKernel(Node x, Queue<Key> queue, Key lo, Key hi)   // 创建迭代器内核，需要递归
326     {
327         if (x == null)
328             return;
329         int cmplo = lo.compareTo(x.key);
330         int cmphi = hi.compareTo(x.key);
331         if (cmplo < 0)
332             keysKernel(x.left, queue, lo, hi);
333         if (cmplo <= 0 && cmphi >= 0)
334             queue.enqueue(x.key);
335         if (cmphi > 0)
336             keysKernel(x.right, queue, lo, hi);
337     }
338     
339     public Iterable<Key> levelOrder()           // 生成先根序队列
340     {
341         Queue<Key> keys = new Queue<Key>();
342         Queue<Node> queue = new Queue<Node>();
343         for (queue.enqueue(root); !queue.isEmpty();)
344         {
345             Node x = queue.dequeue();
346             if (x == null)
347                 continue;
348             keys.enqueue(x.key);
349             queue.enqueue(x.left);
350             queue.enqueue(x.right);
351         }
352         return keys;
353     }
354 
355     public int size(Key lo, Key hi)         // 计算键落在给定范围内的元素个数
356     {
357         if (lo == null)
358             throw new IllegalArgumentException("
<size> lo == null.
");
359         if (hi == null)
360             throw new IllegalArgumentException("
<size> hi == null.
");
361         if (lo.compareTo(hi) > 0)
362             return 0;
363         if (contains(hi))
364             return rank(hi) - rank(lo) + 1;
365         return rank(hi) - rank(lo);
366     }
367 
368     public int height()                     // 计算树的高度
369     {
370         return heightKernel(root);
371     }
372 
373     private int heightKernel(Node x)        // 计算树高度内核，需要递归，空树高度为 -1，根节点高度为 0
374     {
375         if (x == null)
376             return -1;
377         return 1 + Math.max(heightKernel(x.left), heightKernel(x.right));
378     }
379 
380     private boolean check()                     // 检查函数，用于 debug
381     {
382         if (!isBinarySearchST())
383             StdOut.println("
<check> Not in symmetric order.
");
384         if (!isSizeConsistent())
385             StdOut.println("
<check> Subtree counts not consistent.
");
386         if (!isRankConsistent())
387             StdOut.println("
<check> Ranks not consistent.
");
388         return isclass01() && isSizeConsistent() && isRankConsistent();
389     }
390 
391     private boolean isBinarySearchST()                     // 检查输的保序性
392     {
393         return isBinarySearchSTKernel(root, null, null);
394     }
395 
396     private boolean isBinarySearchSTKernel(Node x, Key min, Key max)
397     {
398         if (x == null)
399             return true;
400         if (min != null && x.key.compareTo(min) <= 0)
401             return false;
402         if (max != null && x.key.compareTo(max) >= 0)
403             return false;
404         return isBinarySearchSTKernel(x.left, min, x.key) && isBinarySearchSTKernel(x.right, x.key, max);
405     }
406 
407     private boolean isSizeConsistent()          // 检查树的 size 是否正确
408     {
409         return isSizeConsistentKernel(root);
410     }
411 
412     private boolean isSizeConsistentKernel(Node x)
413     {
414         if (x == null)
415             return true;
416         if (x.size != size(x.left) + size(x.right) + 1)
417             return false;
418         return isSizeConsistentKernel(x.left) && isSizeConsistentKernel(x.right);
419     }
420 
421     private boolean isRankConsistent()          // 检查 rank 和 select
422     {
423         for (int i = 0; i < size(); i++)        // 检查 rank 是否正确
424         {
425             if (i != rank(select(i)))
426                 return false;
427         }
428         for (Key key : keys())                  // 检查 select 是否正确
429         {
430             if (key.compareTo(select(rank(key))) != 0)
431                 return false;
432         }
433         return true;
434     }
435 
436     public static void main(String[] args)
437     {
438         class01<String, Integer> st = new class01<String, Integer>();
439         for (int i = 0; !StdIn.isEmpty(); i++)                  // 放进树中
440         {
441             String key = StdIn.readString();
442             st.put(key, i);
443         }
444 
445         for (String s : st.levelOrder())                        // 迭代器先根序遍历树
446             StdOut.println(s + " " + st.get(s));
447 
448         StdOut.println();
449         for (String s : st.keys())                              // 按键遍历树
450             StdOut.println(s + " " + st.get(s));
451     }
452 }