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