用Binary Search Tree來做搜尋

在一個陣列中,要找一個值存不存在,很直覺的寫法就是寫個for迴圈,從頭找到尾,這種搜尋法稱為線性搜尋(linear searching)。我們來用個更好的方法,二元搜尋樹(binary search tree, BST)。

二元搜尋樹是將資料放到一個二元樹裡面,在建立這個二元樹時,從樹根開始做比較,如果你要找的時比樹根大,就往樹根的右邊去找,否則就往樹根的左邊去找。假設比較大好了,現在我們就拿這個搜尋值,跟樹根右邊的第一個子節點去比對。然後繼續左小右大左小右大的進行比對與移動。

如果一路走到樹葉了,還是找不到這個值的話呢?依「左小右大」的原則,新增一個節點,把這個值放進這個節點,再把這個節點放入這個樹葉的左或是右。

執行結果如下:

bst_1

 

其實搜尋的速度很快的,我們把過程也印出來看看吧!

bst_2

 

先找樹根的0,再找右邊的22,再找右邊的83,再找左邊的73,再找左邊的48,再找左邊的33,再來就是右邊的25了。

我們這個例子其實並不好,我們預設樹根的值是0,因為所有的值都比0還大,所以樹根根本沒有左子樹,哈哈!不過到了樹根的右子樹以後就正常了啦。

二元搜尋樹並沒有保證搜尋時間複雜度一定是 O(lgn),因為樹的形狀有可能是個很誇張的偏斜樹。但是在平均情況下,速度還是優於線性搜尋的O(n)。

Leave a Reply

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *