動畫 | 什麼是二分搜索樹(二叉查找樹)?

  • 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——

推薦閱讀:

動畫 | 什麼是希爾排序?

動畫 | 什麼是插入排序?

動畫 | 什麼是快速排序?

動畫 | 什麼是雞尾酒排序?

影片 | 動態規劃的由來