iT邦幫忙

2021 iThome 鐵人賽

DAY 15
0
自我挑戰組

30天不怕演算法:白話文版系列 第 15

Day 15:樹(tree)

樹是一種抽象資料結構,跟鏈結串列一樣是由節點組成的資料集合。它的形狀類似家族樹,或者說像向下生長的樹,最上面有一個根節點(如下圖A),每個節點都可以有零個或多的子節點。實作上可以像鏈結串列一樣,由每個節點指向子節點的位址。

圖片來源:維基百科

二分搜尋樹(binary search tree)

我們之前提到,陣列的隨機存取利於實現一些演算法,可是不太容易調整長度;鏈結串列的長度有彈性,但只能線性地存取元素。在一些情況下利用樹的結構,可以兼得兩者的優點:既可以保持資料順序、快速搜尋,又容易插入及刪除節點。

圖片來源:維基百科

二分搜尋樹(或稱二元搜尋樹),是二元樹的結構,也就是每個節點最多只會有兩個子節點。二分搜尋樹儲存資料的方式如上圖,每個節點的左邊子節點的值會比自己小,右邊子節點的值比自己大。

確保這樣的結構,就可以進行快速的二分搜尋。

從任一個節點來看,其左半邊的所有節點一定都比較小,右半邊的一定都比較大(如同二分搜尋中的有序陣列),所以從根節點開始搜尋,若目標較小則往左,不用再考慮樹的右半邊,也就是每次的搜尋都可以排除剩下一半的節點,達到O(log n)的搜尋。

值得注意的是,因為樹本身的結構也是將所有節點分為左右兩半,所以樹的高度也會log n。另外,這個結構也體現了二分搜尋中的遞迴概念,也就是樹中任一個節點的左右子結構也各是一個二分搜尋樹,也代表我們可以用程式的遞迴來實作二分搜尋樹。

來源:GeeksforGeeks
def search(root,key):
     
    # 基本情況: 樹不存在或目標在根結點
    if root is None or root.val == key:
        return root
 
    # 目標大於根結點的值
    if root.val < key:
        return search(root.right,key)
   
    # 目標小於根結點的值
    return search(root.left,key)
    
# This code is contributed by Bhavya Jain

如果是要在樹中插入新節點,步驟跟搜尋一樣,要從根節點開始找到新節點的位置,所以執行時間也可以達到O(log n),而且插入新節點只需改變原本節點的指向,不用更動到其他節點。

潛在問題

二分搜尋樹當然也不是集所有優點於一身,還是有一些實作上必須注意的事情。其中一個問題可能是空間,因為所有的節點都要有更多的空間來儲存參照。

另外一個問題是如果樹的結構不平衡,效能也會變差。想像如果根節點的值最小,後來加入的新節點的值越來越大,這樣整棵樹會只往右邊發展。如此一來,樹的高度就會變得非常高(n),搜尋或插入的執行時間也會變成O(n)。我們可以透過一些可以自己平衡結構的二分搜尋樹(例如B樹),來避免這個的問題。


上一篇
Day 14:安全雜湊演算法(SHA)
下一篇
Day 16:堆積(heap)與字首樹(trie)
系列文
30天不怕演算法:白話文版30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言