iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 13
0
Software Development

30天學演算法和資料結構系列 第 13

[資料結構] 二元搜尋樹 (Binary Search Tree)

講了二元樹的走訪,接下來要進入搜尋了,尋找森林深處的密寶~

先來說說 二元搜尋樹 (Binary Search Tree),又稱 有序二元樹排序二元樹。如若不是空樹,則有以下幾個特點:

  • 若任意節點的左子樹不空,則左子樹上所有節點的值均小於它的根節點的值
  • 若任意節點的右子樹不空,則右子樹上所有節點的值均大於它的根節點的值
  • 任意節點的左、右子樹也分別為二元搜尋樹
  • 沒有鍵值相等的節點

https://ithelp.ithome.com.tw/upload/images/20181028/20111557JbyLjpEgbp.jpg
簡單來說就是,任一個節點的左子樹都比父節點小,右子樹都比父節點大,且每一個節點的值都不重複。所以當我們要查找資料的時候,就可以從根節點開始,比根節點小的就從左子樹開始找,比較大的就從右子樹開始找。相對於其他資料結構而言,尋找、插入的時間複雜度較低,為O(logN)。

那有關節點的插入呢?和搜尋很像,從根節點開始比大小,比較小的往左子樹走,比較大的往右子樹走,一樣的則返回,直到插入為止。這邊就不多做解釋。

刪除節點的話就比較複雜了。刪除的節點要從右子樹中找到對大的值來接替。
https://ithelp.ithome.com.tw/upload/images/20181029/20111557rk44OrMotr.png
假設我們要刪除節點 6,就要找節點 5 來替換。如果找 2 的話,那 3~5 都比二大,卻在 2 的左子樹中,於定義相左。因此我們要找 6 的右子樹中,最大的節點來接替。
https://ithelp.ithome.com.tw/upload/images/20181029/20111557BsiRaF9ZC1.png
https://ithelp.ithome.com.tw/upload/images/20181029/20111557rm9gxejzUz.png
https://ithelp.ithome.com.tw/upload/images/20181029/20111557dHl4GrIXMe.png


上一篇
[資料結構] 二元樹走訪 (Binary Tree Traversal)
下一篇
[資料結構] 堆積 (Heap)
系列文
30天學演算法和資料結構31

尚未有邦友留言

立即登入留言