純數據結構Java實現(4/11)(BST)
- 2019 年 10 月 3 日
- 筆記
個人感覺，BST(二叉查找樹)應該是眾多常見樹的爸爸，而不是弟弟，儘管相比較而言，它比較簡單。
二叉樹基礎
理論定義，代碼定義，滿，完全等定義
不同於線性結構，樹結構用於存儲的話，通常操作效率更高。就拿現在說的二叉搜索樹(排序樹)來說，如果每次操作之後會讓剩餘的數據集減少一半，這不是太美妙了么？(當然不當的運用樹結構存儲，也會導致從 O(logN) 退化到 O(n))。
- 值得說明，O(logN) 其實並不準確，準確來說應該說 O(樹的高度)
定義&性質&行話
樹裏面常見的二叉樹: BST, AVL，特殊的AVL(比如2-3樹，即紅黑樹)。
不常見的有(包括多叉樹): 線段樹，Trie。(但我們說的不常見，不見得真的不常見，可能內核或者框架裏面有用到，而寫應用的沒有用到；所以常見或者不常見是沒有一個確定概率基準的，個人把一般寫應用的標準定義為基準)
二叉樹就是一個最多: 一個爸爸，倆孩子 的樹。
這樣說，不形象，那形象點兒，直接上代碼:
class Node { E e; Node left; Node right; }當然，理論教科書上肯定不會這麼傻帽的直接告訴你具體情況，它要繞一下，先來一個遞歸定義，把你繞暈，有圖有真相:
然後一個節點也是樹，空(null) 也是樹。
這裡有一些行話，包括上面的認為 logN 就是樹高(在一般性的時間複雜度分析時)，解釋:
- 深度為 n 的二叉樹，每層最多有 2^(n-1) 個節點
- 深度為 n 的二叉樹，總共元素，最多有 2^n -1 個節點
(深度從 1 開始，從上往下看)(自己畫一下圖，腦海中想一下就知道了)
其他行話，滿二叉樹，完全二叉樹，尤其完全二叉樹這個概念，後續樹結構中有很重要的意義。
- 滿的很好理解吧，圖上理解，就是所有父親都有倆孩子；數據上就是元素總共為 2^n-1
- 完全二叉樹: 如果你從上到下，從左到右給樹的節點編號，那麼樹應該是你看到的方向排布。
設二叉樹的深度為h，除第 h 層(最後一層)外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹。
個人經驗，直接看最後一層是否靠左。
BST基礎
BST 說白了也是一種查找樹，只是它的存儲是有序的。
- (刪除的時候要調整，就知道維護的代價了)
存入的值要麼是可比較的，要麼不能自身提供比較方法時，要主動傳入比較器(Comparator)
也就是說，任意一個節點(它作為根節點看待)，它的左子樹的值都比它要小，右子樹的值都比它大。（正是因為其存儲的時候就有序，所以取的時候也高效）
哦，BST 和滿二叉樹沒啥關係。
BST實現
基本框架
先設置好節點信息，大概如下:
package bst; //二分搜索樹 public class BST<E extends Comparable<E>> { //聲明節點類 private class Node { public E e; public Node left, right; public Node(E e) { this.e = e; left = null; right = null; } } //成員變量 private Node root; private int size; //構造函數 public BST() { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; } }清晰，簡介，然後來補充增刪查改，遍歷等方法。
先做一個規定，對於重複元素的處理是: do nothing。
(它已經在樹上了，就不要動了；或者你可以給 Node 增加一個屬性 count，專門記錄)
增加操作
想像一下，放一個元素到樹上，從根節點開始比較，以後的比較也是根據當前樹的根元素，從而決定放在左子樹，還是右子樹上。(上面已經說了，相等的元素，什麼也不幹)
上面的分析其實已經很清楚了，那麼下面考慮一下寫法:
- 遞歸怎麼寫: 每次切換當前 root 元素，即要搜索的子樹
- 終結條件(base condition): 找到了相關的位置(null)，然後放入元素，返回以該節點為根的子樹給上級樹，的左/右孩子接收
- 子樹不為空，且元素值不等，說明不是終極條件，那接着切換子樹找啊
- 循環怎麼寫: 思想類似上面，不斷下探的過程改成while循環的解法，即不斷遞推替換 currNode 為其左或者右子樹的根節點(就是孩子啦)
- 技巧是，在尋找合適位置時，不僅需要記錄 curr，還要記錄 parent
- 並且實際插入的時候，還是以 parent，即子樹的根為合適位置的依據(這根遞歸做法不同)
一般教科書上才會介紹循環的寫法，大致如下: 《算法-C描述》
OK，我們還是用 遞歸去寫吧，不是偷懶，而是遞歸更易於宏觀理解啊傻
遞歸的寫法: 不斷的切換每層調用的 root 節點的指向 (相當於切換到子樹)
大致寫法如下: (注意柯里化包裹 — 柯里化參考阮一峰的博客JS語言部分)
- 上面已經說了優化過的遞歸終止條件，但是也可以像下面這樣沒有優化(即還沒有判斷到底就開始分情況返回) — 作為思考的中間結果吧 — 優化的結果看最後面的實現。
//向二分搜索樹中添加元素 private void add(E e) { if(root == null) { root = new Node(e); size++; } else { //切換當前 root 節點進行遞歸調用 add(e, root); //第一次調用時已經確定 root != null 了 } } private void add(E e, Node node) { //這裡的 node 相當於一個子樹的 root //複雜的遞歸終止條件 if(e.equals(node.e)) { //已經存在了，do nothing return; } else if(e.compareTo(node.e)>0 && node.right == null) { //不存在子樹的情況 //右子樹為空，直接插入 node.right = new Node(e); size++; return; } else if(e.compareTo(node.e)<0 && node.left == null) { node.left = new Node(e); size++; return; } //一般的情況，即存在左或者右子樹的情況 //此時已經判斷 right 或者 left 不為 null 了 if(e.compareTo(node.e)>0) { //應該在右子樹上找位置 add(e, node.right); } else { //在左子樹上找位置 add(e, node.left); } }但是終止條件可以寫的更加簡單一點，即一直找到空位置再說插入的事兒，而不是分情況判斷時就作為終止條件:
- 找到那個空位置，就在那個位置插入
此時，可以看到，遞歸函數 add 也需要修改成有返回值了，然後讓這個返回值和原BST掛接。(返回以當前節點為根的子樹，掛接給上級才對；思想就是: 上級只關心完整的結果!)
//返回插入新節點後BST的根 (每層調用都是如此) private Node add(E e, Node root) { if (root == null) { size++; return new Node(e); } if (e.compareTo(root.e) > 0) { //放在右子樹 //因為add 函數返回的就是 插入新節點後BST的根 root.right = add(e, root.right); } else if (e.compareTo(root.e) < 0) { root.left = add(e, root.left); } //相等的情況？抱歉，啥也做 return root; }- 這裡的癥結就在於，給當前root的子樹(不管左右哪一個)，插入完成後，都會對當前 root 的左或者右孩子進行重新賦值（後半句是，所以才不關心左右子樹空不空）
而遞歸代碼中已經包含了 root == null 的情況，即空BST的情況，所以主調函數可以直接調用 private 的 add，而不必再判斷 root 為 null:
//client 調用 //向二分搜索樹中添加元素 private void add(E e) { root = add(e, root); }查詢操作
這就相當於二分查找，不斷的折半 — 這裡判斷是否存在即可
也可以分為用遞歸和非遞歸的寫法，然而遞歸的寫法會簡單很多，能寫遞歸也能寫循環。
遞歸的寫法
- 不斷的更換子樹 (以根為子樹的依據)
//查詢元素是否存在 public boolean contains(E e) { return contains(root, e); } //以 root 為根的BST中是否存在 e private boolean contains(Node root, E e) { if(root == null) { return false; } if (e.compareTo(root.e) > 0) { //去查右子樹 return contains(root.right, e); } else if (e.compareTo(root.e) < 0) { return contains(root.left, e); } //return root.e.compareTo(e) == 0; return true; }最後的root.e.compareTo(e) 沒有必要，因為除了 > 和 < 剩下的就是 == 的情況了。
遍歷操作(遞歸)
遍歷相對來說還是比較容易的，這裡先說深度優先。
深度優先: 先序遍歷，中序遍歷，後序遍歷；這些都是相對於根元素來說的。
以 先根遍歷 來舉個例子:
public void preOrder() { preOrder(root); } private void preOrder(Node root) { if(root == null) { return; } System.out.println(root.e); preOrder(root.left); preOrder(root.right); }到這裡可以簡單測試一下:
public static void main(String[] args) { BST<Integer> bst = new BST<>(); int[] nums = {5, 3, 6, 8, 4, 2}; for(int num: nums){ bst.add(num); } bst.preOrder(); //5 3 2 4 6 8 }其他的遍歷方式，其實就非常容易改寫了。
例如 中根遍歷:
//中序遍歷 public void inOrder() { inOrder(root); } private void inOrder(Node root) { if (root == null) { return; } inOrder(root.left); System.out.println(root.e); inOrder(root.right); } //測試輸出: 2 3 4 5 6 8 (相當於一個排序結果)從輸出的結果可以看到一個性質，BST的中序遍歷結果是一個排序結果。
例如 後序遍歷:
//後序遍歷 public void postOrder() { postOrder(root); } private void postOrder(Node root) { if (root == null) { return; } postOrder(root.left); postOrder(root.right); System.out.println(root.e); }先把孩子處理好，再來弄自己的事兒。。。可以聯繫到內存釋放，先釋放子窗口的，最後在關閉 main。
遍歷操作(非遞歸)
這裡用變量的迭代器換也能寫，不過我見過的比較高明的手段，用棧來寫。
用棧記錄後面需要操作(當前還不需要執行)，當前處理的則出棧(這裡運用上，有一些技巧)，我直接說了:
- 每次都出棧當前子樹根元素(打印操作)，然後把它的左右子節點反序放入棧中(反序是因為棧是後入先出的);
- 什麼時候結束，樹遍歷完畢的時候；即棧里沒有內容了
可以看下代碼實現:
//先序遍歷，非遞歸寫法 public void preOrderNR() { Stack<Node> stack = new Stack<>(); stack.push(root); //開始之前的準備，真正的根入棧 while (!stack.isEmpty()) { Node curr = stack.pop(); //出棧當前的根元素 System.out.println(curr.e); if (curr.right != null) { stack.push(curr.right); } if (curr.left != null) { stack.push(curr.left); } } }開始之前，根元素入棧，保證棧裏面有內容，然後第一次檢查棧，出棧一個元素，即真正的根元素，先打印它，接着其左右孩子反序入棧。下次循環，後入棧的左子樹根出棧，進行左邊子樹的整個操作，全部完畢後才輪到右子樹(的根出棧，然後完成類似結果)。
舉一個形象的例子:
16 出棧後，此時壓入 16 的右孩子 22，然後壓入左孩子 13。(遍歷的反序)
中序遍歷，後序遍歷的非遞歸實現？麻煩自己寫一下，貌似沒有太多實際參考。
層序遍歷
就是廣度優先啦，這個概念貌似應該用於圖，但樹也可以用到。
廣度優先覺得更應該用於決策，因為它會避免你一條路走到黑。(不至於把一棵子樹全部找完，然後發現沒找到，才去找另一個子樹。。。)
這個我比較熟悉，一般需要藉助隊列，寫非遞歸實現:
- 每次出隊一個元素(當前的根節點)時，把其孩子也先後放入隊列中(等待後續遍歷)
- 從結果來看，就是層序遍歷了 (可以想像一下文件夾的遍歷，把當前文件夾的子文件夾放入隊列的尾部)
在腦海中可以想像一下，現實司令級別的班子先過，每次檢查到一個司令(出隊)，就把他手下的軍長排在隊列的尾部(即所有司令的後部)，這樣一直不斷，知道司令外部出去，檢查第一個軍長，同理把他手下的師長全部入隊(即所有軍長的後面)…直到隊列為空，全部遍歷完畢。
直接寫代碼:
//廣度優先-層序遍歷 public void levelOrder() { Queue<Node> queue = new LinkedList<>(); //util linkedlist 實現了 queue 接口 queue.add(root); while((!queue.isEmpty()) { Node curr = queue.remove(); System.out.println(curr.e); if(curr.left != null) { queue.add(curr.left); } if(curr.right != null) { queue.add(curr.right); } } }忘了說了，層序遍歷，先左後右。
在圖中的遍歷還需要記錄某個節點是否訪問過，因為二叉樹的爸爸只有一個，但是圖中節點的前驅可能有多個的，為避免重複遍歷，所以必須標記一下是否訪問過。
刪除操作(重點)
整個 BST 的難點就在這裡，想也知道啊，我刪了一個元素，那麼以這個元素為根的樹怎麼調整才能與當前元素的上級掛接(嫁接)好呢？
(複雜可能在於，需要重新排序樹)
題外話:
我自個兒也是琢磨了一會兒，然後發現對付複雜，**先從特例上找規律，然後推廣到一般**。 特例的規律如若不能推廣到一般，那麼就按照第二種思路: 分分合合。 * 分: 詳細分析情況，不漏掉情況(暴力窮舉) * 合: 這些具體的，分情況的方案能否合併，上升到一個層級規律 這樣的好處，即便不能合，那麼分情況的窮舉(暴力解法)，我們也能保底。(解決的不優雅，但按性質劃分還是屬於已解決的分類，有政治優勢)直接說結論，這裡採用的是(找到元素)替換(覆蓋)要被刪除的元素
找一個怎麼樣的節點去替換啊? 找一個最接近被刪除元素大小的元素替換。
- 此時其實挪動和改變最少，且滿足刪除後該樹仍舊是一棵BST的要求
最接近的元素: 要刪除元素的左子樹上找最大，要刪除元素的右子樹上找最小。
先看看一棵子樹上怎麼找最大最小:(鋪墊)
- 查找最小值: 一直尋找左孩子，直到最左邊的一個節點沒有左孩子(null)。
- 查找最大值: 一直尋找右孩子，直到最右邊的一個節點沒有右孩子(null)。
大致實現如下:
//獲取樹的最小值 (遞歸寫法) public E getMin() { if(isEmpty()) { throw new IllegalArgumentException("Tree is Empty"); } return getMin(root).e;//調用遞歸的寫法 } private Node getMin(Node node) { if(node.left == null) { return node; } return getMin(node.left); } //樹的最大值 (非遞歸寫法) public E getMax() { if(isEmpty()) { throw new IllegalArgumentException("Tree is Empty"); } Node curr = root; while(curr.right != null) { curr = curr.right; } return curr.e; }這裡是拿到值，所以簡單，但是刪除的話，處理的是 Node，而不僅僅是值。
所以拿到最小元素的節點(當然順帶也要刪除這個值)，以及拿到最大元素的節點(順帶也要刪除這個值)，這兩個值一定是最接近當前元素的，用它們中的一個，來覆蓋當前被刪除的元素的位置即可。
找到並刪除(當前元素相關的)最小元素:
- 最小元素: 向左找沒有左節點的最終節點
- 該節點沒有孩子，(左子樹一定為空了)，直接刪除 —— 葉子節點的情況
- 該節點有右子樹，直接返回該右節點 (作為子樹的根，進行下一次循環或者遞歸起點) —— 非葉子節點
- 維護 size 的大小
代碼實現:
//刪除最小值 (遞歸寫法) public E removeMin() { E ret = getMin(); //不需要 isEmpty判斷了 root = removeMin(root); //操作完畢返回新樹的根 return ret; } //刪除以 node 為根的子樹的最小節點；返回該子樹的根 private Node removeMin(Node node){ //base 情況 if(node.left == null) { //當前子樹的左子樹為空(不管右子樹如何)，說明當前節點最小 //當然，如果有右子樹，要把右子樹嫁接到父節點(返回右子樹的根給上級即可) //刪除同時還要把當前節點的孩子置空 Node rightNode = node.right; //當前節點的左子樹可能為空 node.right = null; //(當前節點的左子樹已經為空了) size--; return rightNode;//返回給上級(具體說，上級的左子樹) } //一般情況 (以 node 為根，還有左子樹) node.left = removeMin(node.left); //遞歸過程返回調整後的子樹(根節點) return node; //每次都返回該子樹刪除最小值之後的結果 }找到並刪除(當前元素相關的)最大元素:
此過程類似於刪除最小元素，遞歸操作時，每次都返回刪除該node為根的子樹的根節點，讓上級節點的右節點接收。(末尾節點(右子樹一定空)如果沒有子節點，即左節點也為空，那麼 base 就返回 null，否則把左子樹嫁接到上級，具體說就是上級節點的右子樹)
代碼實現:
//刪除最大值 (遞歸寫法) public E removeMax() { E ret = getMax(); root = removeMax(root); return ret; } //返回刪除最大值後的根節點(子樹)給上級節點 private Node removeMax(Node root) { //Base 情況(末尾節點) if(root.right == null) { //沒右子樹了 //判斷其是否還有左子樹，然後把左子樹返回給上級節點(的右子樹接收) //同上，不必判斷，因為 root.left 即便為 null 也包含在這種情況中 Node leftNode = root.left; root.left = null; size--; return leftNode; } root.right = removeMax(root.right);//有右子樹那就在右子樹上找 return root; }從上面刪除最大，最小的邏輯，可以推廣到一般情況，具體來說，舉個例子:
- 刪除 58 很容易，直接把 60 這個節點返回給右子樹 (因為 41 為根的這棵樹已經有左子樹)
- 刪除 22 則情況至少有兩種(左右都有節點)，一種 15 上位(作為 41 的左子樹)，然後 33 接在 15 的右子樹上，另外一種則是 33 上位，然後 15 接在 33 的左子樹上
- 這裡 22 的子樹比較特殊(只有半邊子樹)，所以可以很容易看出兩種情況
- 也就是說，可以在左邊找前驅，也可以在右邊找後繼
- 葉子節點更簡單，不必單獨拿出來，直接返回給上級一個 null 即可作為子樹即可
若某節點的子樹都是滿的，則不那麼容易，以後繼為例，講一下思路:
其實就是在右子樹上找一個最節點最接近當前值的節點，替代當前要刪除的節點。即 min(d->right)。換句話說，右子樹中找到最小元素(其實是刪除掉這個元素)，然後在 d 的位置填補這個元素，圖例如下:
上面把 s 的一切設置好(left, right)，此時 s 就是整個調整完畢的子樹根，把它返回給上級樹的右子樹即可。
這裡已經可以看出，結論如下:
- 但凡有一邊子樹是空的，就是特殊情況，方便處理(下面代碼也會證明這一點)
- 整整困難的是兩邊都是滿的，此時需要 找前驅或者後繼，替換 這種思路(至於用前驅還是後繼，隨意; 因為都能保證之後的樹是一棵BST)
那麼代碼實現: (參考刪除最大最小的邏輯，推到刪除的一般邏輯，以後繼為例)
/*找後繼的實現*/ //用戶指定刪除某個值 e 的節點 public void remove(E e) { root = remove(root, e); //每次遞歸都是返回操作後的子樹(根節點) } /* 刪除以 root 為根的子樹中值為 e 的節點 返回操作完畢後子樹的根 */ private Node remove(Node root, E e) { //先要找到這個元素 //base 情況 (前一次遞歸調用返回的是 null 的情況) if (root == null) { return null; //這個空值最終會作為上級樹的孩子 } //(分情況在子樹上找) if (e.compareTo(root.e) > 0) { //在右子樹上找 root.right = remove(root.right, e); } else if (e.compareTo(root.e) < 0) { //在左子樹上找 root.left = remove(root.left, e); } else { // 找到的情況 e.compareTo(root.e) == 0 //從其左右子樹上找替換元素 (這裡採用後繼進行替換) //同時需要返回新的根節點給上級 /* 1.左右子樹都在 (融合的情況) -- 找到右子樹上最小元素進行替代 2.左子樹在，但是沒有右子樹 (類似於刪除最大值的邏輯) 3.右子樹在，但是沒有左子樹 (類似於刪除最小值的邏輯) 4.左右子樹都空了，葉子節點(直接 return null) 即把空子樹返回給上級節點(這一種情況已經包含在2, 3的寫法中了) 先寫 2, 3, 4 這類簡單的情況 (返回值接在上層左子樹還是右子樹不確定，這要看上層的遞歸調用是哪種情況) */ if (root.right == null) { Node leftNode = root.left; root.left = null; size--; return leftNode; //包含了 leftNode 也為 null 的情況 } if (root.left == null) { //類似於查找最小值的情況 Node rightNode = root.right; root.right = null; size--; return rightNode; } //左右子樹都不空的情況(先找到替代節點 successorNode ) Node successorNode = getMin(root.right); successorNode.right = removeMin(root.right); //返回的是刪除最小元素後的根節點 successorNode.left = root.left; //置空原來 root 的 left 和 right root.left = root.right = null; return successorNode; //返回設置好的元素給上級 } return root; }上面的代碼，找到要替換的元素時，分情況分析，即:
1.左右子樹都在 (融合的情況) — 找到右子樹上最小元素進行替代
2.左子樹在，但是沒有右子樹 (類似於刪除最大值的邏輯) — 代碼類似
3.右子樹在，但是沒有左子樹 (類似於刪除最小值的邏輯) — 代碼類似
4.左右子樹都空了，葉子節點(直接 return null) 即把空子樹返回給上級節點(這一種情況已經包含在2, 3的寫法中了)
這相當於在暴力窮舉了，然後發現貌似確實不能合併，所以就這樣劃分了。
BST總結
這裡會總一些可能有用的結論:
最重要的一條，BST的有序性(放入其中的元素，有序存儲)是有維護代價的
- 遍歷：中序遍歷，所有元素是升序排列。
- 最大值，最小值: 不斷向左找左子樹，不斷向右找右子樹。
- 前驅和後繼(節點): 左子樹中找最大值就是前驅(predecessor)，右子樹中找最小值就是後繼(successor)。
- 每個節點Node可以維護額外的屬性，比如 count, rank, depth 等，適用於業務查詢
- floor 和 ceil: 尋找某個值的 floor 和 ceil
- 該元素可以不在樹上
整個看下來，也就是刪除上要仔細考慮好幾種情況以及破天荒的有 替換 的思維。
它的實現基本上就先這樣(應用上有很多變形，但這與其實現無關，後面再說)。
老規矩，代碼請參考 gayhub。
