二元搜尋樹

一樖二元搜尋樹

二元搜尋樹ji6 jyun4 sau2 cam4 syu6（英文：binary search tree，BST）係一種二元樹數據結構。喺一樖唔係空嘅二元搜尋樹裏面，

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

概論

睇埋：數據結構同二元樹

如果用家想加個新數值 $v$ 落一樖二元搜尋樹 bst 度，可以噉做：

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

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

睇埋

• 二元樹
• B-樹
• 搜尋演算法
• 排序演算法

拎

• Binary Search Tree. GeeksForGeeks.