什麼是二元搜尋樹
對每個節點而言，左子樹的值都比該節點小、右子樹的值都比該節點大的二元樹。搜尋、插入與刪除的工作量與樹的高度成正比，以中序走訪時值會依升冪排列。
日文名稱: 二分探索木
「二元搜尋樹」出現在1領域的4道練習題中（資料結構與演算法等）。
這個名詞所屬的領域: 資料結構與演算法
搜尋、插入與刪除
搜尋從根部開始，要找的值比節點小就往左子節點、比節點大就往右子節點前進，重複到相符或沒有子節點為止。插入是在搜尋到沒有子節點的位置接上新節點。刪除時，若子節點為0或1個，就移除該節點並重新接上子節點；若有2個子節點，則以右子樹的最小值（或左子樹的最大值）取代後，再刪除那個節點。每種操作的工作量都與從根部到樹葉的層數（樹的高度）成正比。
偏斜的樹與平衡二元搜尋樹
有 n 個節點的二元搜尋樹若平衡，高度約為 log₂ n；但若像 1, 2, 3, … 這樣依已排序的順序插入，就會變成只往一側延伸的一條鏈，高度為 n−1。此時搜尋與鏈結串列相同，為 O(n)。AVL 樹與紅黑樹是在每次插入與刪除時以稱為旋轉的操作調整形狀、把高度維持在 O(log n) 的平衡二元搜尋樹，許多程式語言的有序字典與集合都使用它們。
走訪的種類
拜訪樹中所有節點的方法，有先拜訪節點的前序走訪、依左子樹、節點、右子樹順序的中序走訪、先拜訪子節點的後序走訪，以及逐層拜訪的廣度優先（層序）走訪。以中序走訪二元搜尋樹時，值會依升冪排列，可以得到排序後的清單。以後序走訪表示算式的樹，則得到逆波蘭表示法。
練習二元搜尋樹的題目
以中序走訪（依左子樹、該節點、右子樹的順序拜訪）走訪二元搜尋樹時，拜訪到的節點值會如何排列？假設所有值都不相同。
- A依升冪（由小到大）排列
- B依插入樹的順序排列
- C依離根部由近到遠（由淺到深）的順序排列
查看答案與解析
正確答案：A. 依升冪（由小到大）排列
在二元搜尋樹中，對任何節點而言，左子樹的值都比該節點小，右子樹的值都比該節點大。因此依左子樹、節點、右子樹的順序走訪，就會由小到大依序拜訪，結果為升冪。依離根部由近到遠排列，是逐層由左往右拜訪的廣度優先（層序）走訪。插入順序雖然會影響樹的形狀，但與走訪的順序並不一致。
對空的二元搜尋樹依序插入 50, 30, 70, 20, 40, 60, 80。以後序走訪（依左子樹、右子樹、該節點的順序拜訪）走訪此樹時，順序為下列何者？
- A50, 30, 20, 40, 70, 60, 80
- B20, 40, 30, 60, 80, 70, 50
- C20, 30, 40, 50, 60, 70, 80
查看答案與解析
正確答案：B. 20, 40, 30, 60, 80, 70, 50
根為50，左子節點為30（其子節點為20與40），右子節點為70（其子節點為60與80）。後序走訪先拜訪左子樹的 20, 40, 30 與右子樹的 60, 80, 70，最後才拜訪根部的50。50, 30, 20, 40, 70, 60, 80 是先拜訪節點的前序走訪，20, 30, 40, … 則是中序走訪的結果。後序走訪用於必須先處理子節點的情況，例如刪除整棵樹，或由算式樹產生後序式。
常見問題
二元搜尋樹與堆積有什麼不同？
二元搜尋樹遵循「左小右大」的條件，能搜尋任意值並依序列舉。二元堆積只遵循「父節點比子節點大（或小）」的條件，能立刻取出最大值（最小值），但不適合搜尋任意值。
二元搜尋樹與 B 樹該如何區分使用？
在記憶體中使用時用平衡二元搜尋樹；在磁碟或 SSD 這類以區塊為單位讀取的儲存裝置上，則使用讓1個節點存放多個鍵、使樹變矮的 B 樹（B+ 樹）。
解析中的「二元搜尋樹」
在二元搜尋樹中，對任何節點而言，左子樹的值都比該節點小，右子樹的值都比該節點大。
以中序走訪（依左子樹、該節點、右子樹的順序拜訪）走訪二元搜尋樹時，拜訪到的節點值會如何排列？假設所有值都不相同。若是平衡的樹，層數只有約 log₂ 1000 ≈ 10，因此使用 AVL 樹或紅黑樹這類在每次插入與刪除時調整形狀的平衡二元搜尋樹，最差也能維持 O(log n)。
對空的二元搜尋樹依序插入 1, 2, 3, …, 1000（不做平衡的操作）。在這棵樹中尋找1000時，從根部開始比較…二元搜尋樹在1億筆時至少需要約27層，若每層都讀取不同的區塊就會變慢。
資料庫與檔案系統的索引常使用 B 樹（包含 B+ 樹）而非二元搜尋樹，其主要原因為下列何者？
出現「二元搜尋樹」的題目（4題）
半導體、電子電路與資訊計算工具
相關名詞
鏈結串列 SSD(固態硬碟) 二元堆積 二分搜尋 佇列 時間複雜度（大O符號） 動態規劃 堆疊 深度優先搜尋 貪婪演算法