iT邦幫忙

2021 iThome 鐵人賽

DAY 15
0
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 15

【Day15】[資料結構]-二元搜尋樹Binary Search Tree, BST

二元搜尋樹(Binary Search Tree),也稱有序/排序二元樹,是一種特殊二元樹結構,而節點資料的排序具備一些特性。


特性如下

  • 左子樹任一節點的值一定小於根節點的值
  • 右子樹任一節點的值一定大於根節點的值
  • 任一節點的左、右子樹也分別為二元搜尋樹。
  • 每一個節點不能出現重複的資料。

如下面這棵樹,就是一棵合法的BST
https://ithelp.ithome.com.tw/upload/images/20210926/201210278DRvVFrlPp.jpg

下面這棵樹就不是一棵合法的BST,雖然節點11大於8是合法,大於6也是合法的。但是不能大於10這個節點。畢竟11這個節點還是屬於10節點的左子樹。因此不是一棵合法的二元搜尋樹。
https://ithelp.ithome.com.tw/upload/images/20210926/20121027EVkypo1bMq.jpg


新增節點

若目標值小於節點的值,則前往左子樹;若目標值大於節點的值,則前往右子樹;
https://ithelp.ithome.com.tw/upload/images/20210926/201210270lxK9JhbHC.jpg


搜尋節點

若目標值小於節點的值,則繼續在左子樹中搜尋;若目標值大於節點的值,則繼續在右子樹中搜尋;
https://ithelp.ithome.com.tw/upload/images/20210926/20121027wJbss1oGne.jpg


刪除節點

需要考慮節點的三種情況

  • 葉子節點(無子樹),直接刪除。
    https://ithelp.ithome.com.tw/upload/images/20210926/20121027r4HlHL1H5o.jpg
  • 節點有單邊子樹,用子樹代替該節點。
    https://ithelp.ithome.com.tw/upload/images/20210926/201210278r141V68fb.jpg
  • 節點有左右兩邊子樹,左子樹取最大值,右子樹取最小值。
    https://ithelp.ithome.com.tw/upload/images/20210926/20121027jXNlOV19Yz.jpg

上一篇
【Day14】[資料結構]-二元樹走訪Binary Tree Traversal
下一篇
【Day16】[資料結構]-二元搜尋樹Binary Search Tree-實作
系列文
資料結構與演算法,使用JavaScript與Python35

尚未有邦友留言

立即登入留言