二元搜尋樹
閱讀設定
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/300px-Binary_search_tree.svg.png)
- 喺根左邊嗰樖子樹(subtree)入面嗰啲數值,冚唪唥都細過根節點嘅數值;
- 喺根右邊嗰樖子樹入面嗰啲數值,冚唪唥都大過根節點嘅數值;
- 兩樖子樹本身都係二元搜尋樹。
概論
[編輯]如果用家想加個新數值 落一樖二元搜尋樹 bst
度,可以噉做[1]:p. 42:
- 如果
bst
係空嘅,將 設做根節點; - 如果 數值細過根節點嘅,將 擺落去左邊嗰樖子樹度;
- 如果 數值大過根節點嘅,將 擺落去右邊嗰樖子樹度;
- 如果 數值等同根節點嘅,出
error
; - 上述嘅演算法可以配合遞歸嚟用。
二元搜尋樹有好多好處,例如令搜尋演算法行起上嚟快(同廿一世紀初嘅基本數據結構比起嚟)-用家摷數據嗰陣可以假設啲數據經已按數值由細至大排好咗。
睇埋
[編輯]攷
[編輯]- ↑ 1.0 1.1 John Bullinaria, (2019). Lecture Notes for Data Structures and Algorithms (PDF). School of Computer Science, University of Birmingham.
拎
[編輯]- Binary Search Tree. GeeksForGeeks.