複習我們都曾學過的 binary search tree
簡介
為了後面的 treap 和 skip list 所以決定先來寫一篇 binary search tree 作為複習,相信大家沒學過也聽過 binary search tree,是本科大學資結在學 tree 的時候最先學到的幾種之一,今天就來好好的重溫天真美好的大學時光吧。以下簡稱 binary search tree 為 BST。
先給大家最關心的時間與空間複雜度:
定義
我們先來說說 BST 的四條定義:
- 以左邊節點 ( left node ) 作為根的子樹 ( sub-tree ) 的所有值都小於根節點 ( root )
- 以右邊節點 ( right node ) 作為根的子樹 ( sub-tree ) 的所有值都大於根節點 ( root )
- 任意節點 ( node ) 的左、右子樹也分別符合 BST 的定義
- 不存在任何鍵值 ( key/value ) 相等的節點。
(謎之音):很多人會不記得第四點,但遇過面試有問,但想一下就會知道如果有相等值的節點就會違反第一點或第二點。
Binary Search
既然稱為 binary search tree,那想必跟 binary search 脫不了關係,沒錯 BST 便是基於 binary search 而建立的資料結構,BST 也可以說是為搜尋而生的,所以搜尋的時間複雜度當然也要能達成 O(log n),但不是說使用了 BST 做搜尋就一定可以穩定 O(log n),如同上圖所示,搜尋的最差情況是在 O(n) ,關鍵就在平衡,在講平衡之前,我們先來講樹高。
以 3 個 node 的 BST 為例,有三種排列可能(就不列 10 -> 20 -> 30 了,跟第二種差不多,只是左右反過來)
好,那今天如果我們要搜尋 10 這個鍵值:
- 第一種排列:只需要一次比較(從 root 進入,10 < 20,往左走,找到了)
- 第二種排列:需要兩次比較(從 root 進入,10 < 30,往左走,10 < 20,繼續往左走,找到了)
所以我們可以看到在一樣數量的 node 的情況之下,不一樣的樹高對搜尋產生的影響是很關鍵的,如果有平衡就可以讓樹高在最理想的情況,使搜尋可以達到 O(log n)。
如果平衡的話,假有共有 n 個節點,那麼樹高應該就是 ( log n ) + 1。
四種操作
接下來介紹搜尋、新增、改值、刪除四種操作
新增節點
假設我們今天要把值為 15 和 40 的節點新增進去
先做 15 的節點:
- 與 root 節點 ( 20 ) 比較,15 < 20,左子樹不為空,往左子樹走
- 與節點 ( 10 ) 比較,10 < 15,右子樹為空,就把 15 填進去
相信聰明的你已經知道怎麼新增節點了,試試看把 40 新增進去吧。
沒錯就是這樣,按照上面的邏輯 40 就應該放在 30 的右邊(右子樹)。
搜尋結點
假設我們要搜尋 15 這個節點,其實跟新增的步驟差不多,先逐一比大小,差在要確認經過的節點的值是不是 15 即可。
- 與 root 節點 ( 20 ) 比較,15 < 20,往左子樹走
- 與節點 ( 10 ) 比較,10 < 15,往右子樹走
- 與節點 ( 15 ) 比較,15 == 15,找到了!
修改節點的值
我上網查發現沒有什麼人講到如果要改值的話怎麼操作最有效率,但最簡單的方法應該是就把該舊值的節點刪除,然後插入更新值的節點。
刪除節點
我們先來列出刪除節點的四種可能:
- 該節點沒有左右子樹
- 該節點只有右子樹
- 該節點只有左子樹
- 該節點有左右子樹
第 1 種情況是最簡單的,只要直接刪掉就可以了。
再來是第 2 種,也是很簡單,只要刪掉節點,然後把父節點 ( 20 ) 連到右子樹的 root ( 15 ) 即可。
第 3 & 4 種其實做法是一樣的,就是要找被刪除的節點的左子樹中最大值的節點,然後取代被刪除節點的位置。
實作
又來到實作的時間啦
先來定義兩個 class,把操作方法定義在 BST 裡面
新增節點:
以 root 為起點開始比大小,直到發現空位就可插入,這邊是用 loop 的方法來寫,也可以用遞迴的方式來寫。
搜尋節點
基本上跟新增一樣,也是去比大小,找到的話就回傳。
刪除節點:
刪除就很麻煩了,記得我們上面說的四種可能:
- 該節點沒有左右子樹
- 該節點只有右子樹
- 該節點只有左子樹
- 該節點有左右子樹
我們需要分開處理:
第一和第二點跟上面說的差不多,只要記得檢查是不是 BST 的 root 即可,是的話要 update BST 中的 self.root。
第三和第四點就有一點複雜了,分成幾種情況:
被刪除的 node 的 left sub-tree 的 root 是否為該 sub-tree 最大值的 node
if true:
就把 left sub-tree 的 root 接上被刪除的 node 的位置,結束。
if false:
被刪除的 node 的 left sub-tree 的最大值的 node 是否有 left sub-tree,有的話要先接回 left sub-tree 的最大值的 node 的 parent node,才能把最大值的 node 取代原本刪除的 node
檢查被刪除的 node 是不是 BST 的 root,是的話要 update BST。
寫完覺得看起來還是很複雜,說不定直接看 code 最好懂。
後記
上一篇已經不知道隔了多久,養成一個好習慣果然是很困難的事啊。總之寫了兩篇基本的資料結構,下篇決定要來寫有趣一點的,請大家敬請期待啦。
感謝你/妳花時間讀這篇文章,如果你覺得這篇文章寫得不錯、有幫助到你,希望你能給我一點「拍手鼓勵」,也可以留言讓我知道你的想法,我會多加點油寫出更多內容的!
1. 拍「10下」:表示你喜歡這篇文章,謝謝你!
2. 拍「20下」:表示你覺得這篇文章很棒、願意分享給朋友!
3. 拍「30–40下」:希望未來我能寫更多這類主題的文章!
4. 拍好拍滿「50下」:給我最大的鼓勵,這將會支持我繼續寫作,並持續分享我的經驗!
拍手小秘訣: 只要將滑鼠(或手指)持續按著不放手掌的icon,就能夠連續拍手囉,試試看吧!