對空的二元搜尋樹依序插入 1, 2, 3, …, 1000（不做平衡的操作）。在這棵樹中尋找1000時，從根部開始比較，到找到為止要比較幾個節點？

正確答案：C. 1,000

依升冪插入時，新的值每次都成為之前最大值的右子節點，因此樹會變成只往右延伸的一條鏈（高度999）。1000位於最底部，因此要與 1, 2, …, 1000 共1,000個節點比較，與從開頭走訪鏈結串列相同，為 O(n)。若是平衡的樹，層數只有約 log₂ 1000 ≈ 10，因此使用 AVL 樹或紅黑樹這類在每次插入與刪除時調整形狀的平衡二元搜尋樹，最差也能維持 O(log n)。

• A. 若是平衡的樹約需10次，但這棵樹已變成一條鏈。
• B. 這接近尋找中間位置的值的次數，但1000位於末端。
• C. 正確。樹變成一條鏈，尋找1000要與所有節點比較。