跳去內容

二元搜尋樹

出自維基百科,自由嘅百科全書
一樖二元搜尋樹

二元搜尋樹ji6 jyun4 sau2 cam4 syu6英文binary search tree,BST)係一種二元樹數據結構。喺一樖唔係空嘅二元搜尋樹裏面[1]:Ch. 7

  • 喺根左邊嗰樖子樹subtree)入面嗰啲數值,冚唪唥都細過根節點嘅數值;
  • 喺根右邊嗰樖子樹入面嗰啲數值,冚唪唥都大過根節點嘅數值;
  • 兩樖子樹本身都係二元搜尋樹。

概論

[編輯]

如果用家想加個新數值 落一樖二元搜尋樹 bst 度,可以噉做[1]:p. 42

  • 如果 bst 係空嘅,將 設做根節點;
  • 如果 數值細過根節點嘅,將 擺落去左邊嗰樖子樹度;
  • 如果 數值大過根節點嘅,將 擺落去右邊嗰樖子樹度;
  • 如果 數值等同根節點嘅,出 error
  • 上述嘅演算法可以配合遞歸嚟用。

二元搜尋樹有好多好處,例如令搜尋演算法行起上嚟快(同廿一世紀初嘅基本數據結構比起嚟)-用家摷數據嗰陣可以假設啲數據經已按數值由細至大排好咗。

睇埋

[編輯]

[編輯]
  1. 1.0 1.1 John Bullinaria, (2019). Lecture Notes for Data Structures and Algorithms (PDF). School of Computer Science, University of Birmingham.

[編輯]