動畫 | 什麼是二分搜索樹（二叉查找樹）？
- 2019 年 12 月 23 日
- 筆記
二分搜索樹屬性
二分搜索樹的又名比較多，有的叫二叉排序樹，也有的叫二叉查找樹，或者有序二叉查找樹。是指一棵空樹或者具有下列性質的二叉樹：
1.若任意節點的左子樹不空，則左子樹所有節點的值均小於它根節點的值；
2.若任意節點的右子樹不空，則右子樹所有節點的值均大於它根節點的值；
3.任意節點的左、右子樹也分別為二叉查找樹；
4.沒有鍵值相等的節點。
它的查找、插入和刪除的時間複雜度都等於樹高，期望值是O(logn)，最壞時間複雜度是O(n)，比如樹退化成線性表。
查找元素
二分搜索樹是為了實現快速查找而生的，也支援快速添加和刪除一個數據。如何查找某個元素首先跟根節點去做比較，如果相等的話就返回；如果待查元素要比根節點小，就進行左子樹遞歸查找；如果待查元素要比根節點大，就進行右子樹的遞歸查找；如果查找到最後還沒有一個符合的元素，就返回null。
遞歸查找
遞歸查找的方式有很多，有層序遍歷、前序遍歷、中序遍歷和後序遍歷。我這裡就舉後面三個遍歷方式。
Code
如果程式碼是下面這樣寫的，那它遍歷過程是怎麼樣的？看下面動畫。
動畫：前序遍歷
（響應讀者的建議，動畫不放BGM了）
動畫：前中後遍歷
從上面動畫就發現，通過中序遍歷得到的正好是一個升序序列。如果不考慮升序，後序遍歷也能夠為二分搜索樹早點釋放記憶體，早點減少棧的使用空間。
Code
添加元素
對於二叉樹的添加和刪除元素，使用鏈表存儲形式比較好操作的，如果使用數組形式存儲，刪除某一個有子樹的元素會引發一系列的位置改變，涉及到交換元素的位置，性能也比鏈表的小。所以待會後面出現的偽程式碼都以鏈表存儲形式去操作。
Code
刪除元素：刪除最小和最大的元素
刪除最小和最大的元素很簡單，如果是刪除最小的元素，從二叉樹的頂點出發，一直遞歸它的左孩子，直到某節點的左孩子為空，這時候這個節點就是最小的元素。刪除最大的元素也是一樣的，一直遞歸它的右孩子，直到某節點的右孩子為空。
刪除任意元素
如果刪除任意元素，而這元素正好有左右子樹的，那該是怎麼般呢？
1962年，Hibbard提出了HibbardDeletion的解決方法。
看到Hibbard名字就想起來，我在希爾排序介紹過Hibbard增量序列，也把它相應的公式通過程式碼體現出來，代替希爾增量序列去進行希爾排序，最壞時間複雜度也比希爾增量序列的要小。
回到刪除有左右子樹的元素，想想它的左右子樹也屬於二叉排序樹（也是二分搜索樹），它左子樹的最大值比它小，它右子樹的最小值比它大。所以不管選擇左子樹的最大值還是選擇右子樹的最小值，替換掉要刪除的元素，整個二叉樹都是符合二分搜索樹的規則。
動畫：刪除元素
Code：刪除任意元素
支援重複元素的二分搜索樹
二分搜索樹有一個規則是：沒有鍵值相等的節點。那麼就不建議把待添加的元素跳過值相等的節點，到下一步繼續比較直到插入新的節點。比如我想插入23，插完之後上有23，下有23，那查找就沒有意義了，也破壞了時間複雜度上的O(logn)。
建議就是在節點上加一個屬性：count。當插入23的時候，count就可以自算++。這不僅滿足了沒有鍵值相等的規則，也滿足時間複雜度的期望值。
Code
——END——
推薦閱讀：
