Chapter 7 二元搜尋樹 - Ian-Liu-1990/Data-Structure GitHub Wiki
二元搜尋樹
1. 定義需要滿足那些條件，何謂二元搜尋樹(變相問法?)
- 一定要是一棵二元樹[所有二元樹的特性都包含]
- 是有序二元樹
- 樹根的左子樹中的後代鍵值皆小於樹根
- 樹根的右子樹中的後代鍵值皆大於樹根
- 樹根的左子樹和右子樹也是二元搜尋樹
- 二元搜尋樹鍵值不重複
2. 給序列找二元搜尋樹後序列or前序列，給序列問是否為正確搜尋結果
3. 時間複雜度特性
假設一棵二元搜尋樹有N節點或還是一串N筆的資料(未排序)
| 操作 | 最差時間複雜度 | 最差時機 | 最好(平均)時間複雜度 | 最好時機 |
|---|---|---|---|---|
| 建立 | O(N^2) | 資料已被排序過(歪斜樹) | O(NlogN) | 完滿(整)二元樹 |
| 插入 | O(N) | 歪斜樹 | O(logN) | 平衡高度 |
| 搜尋 | O(N) | 歪斜樹 | O(logN) | 完滿(整)二元樹 |
| 刪除 | O(N) | 歪斜樹 | O(logN) | 完滿(整)二元樹 |
| 空間 | O(N) | 歪斜樹 | O(N) | 完滿(整)二元樹 |
二元搜尋樹的插入
二元搜尋樹的刪除
"兩種"方法
二元搜尋樹的排序
- 建立二元搜尋樹並以中序追蹤輸出結果維由小到大的排序
- 建立一棵樹的時間決定時間複雜度
二元搜尋的優點
- 搜尋優化 : N個節點的二元搜尋數平均高度為LogN的等級，故可以使得資料搜尋平均時間為O(LogN)