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

二元搜尋樹

二元搜尋樹(Binary Search Tree)，是一種樹狀資料結構，並具有以下特性

1. 任意節點的左子樹不為空，則左子樹上所有節點的值均小於它的根節點的值

2. 任意節點的右子樹不為空，則右子樹上所有節點的值均大於它的根節點的值

二元搜尋樹的類型

1. full binary tree：除了樹葉外，其餘節點都有左、右子節點

2. complete binary tree：各層節點全滿，除了最後一層，最後一層節點全部靠左

3. perfect binary tree：各層節點全滿，同時也是full binary tree及complete binary tree

時間複雜度

搜尋資料的時候，從根節點開始查詢，比根節點小從左子樹找起，比根節點大從右子樹找起，所以時間複雜度是O(log n)

新增資料亦是，從根節點開始比大小，比根節點小從左子樹開始，比根節點大從右子樹開始，直到找到位置最插入，所以時間複雜度是O(log n)

刪除的情況就比較多元，以下參考 shenyun2304所寫的文章

1. 若是刪除葉節點，直接移除即可，不用做取代

2. 當刪除的節點只有一個子節點，則用該子節點取代刪除節點的位置

3. 移除其餘節點時，則選擇該節點中左子樹的最大值，或是右子樹的最小值來取代

參考資料：

• Binary Tree

• 二元搜尋樹

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

• [資料結構] 樹 Tree

• Binary Search Tree (BST) 二元搜尋樹