一條改變一切的規則
一棵普通二元樹只是個形狀；它對一個值*該住在哪裡*隻字未提。[[binary-search-tree|二元搜尋樹]]（BST）加上一條單一而嚴格的排序規則，而這條規則就是全部的魔法所在：對每一個節點，它左子樹裡的一切都更小，右子樹裡的一切都更大。 就這樣。這條規則不僅對一個節點的直接孩子成立，對它下面整棵子樹都成立。
(8)
/ \
(3) (10)
/ \ \
(1) (6) (14)
left of 8 -> {3,1,6} all < 8
right of 8 -> {10,14} all > 8
...and the same holds at 3, at 10, everywhere.查找：每一步都砍掉一半
在 BST 裡查找，就是 [[binary-search|二分搜尋]] 的樹版本。從根開始比較。相等？找到了。比這個節點小？規則保證你的目標只可能在左邊，於是往左走，把整棵右子樹忘掉。更大？往右走。每一次比較都丟掉剩餘部分的一整側——正是讓有序陣列上的二分搜尋如此之快的那種「砍半」，如今表現為順著樹往下走。插入走的是一模一樣的路徑：去查找這個值，在你從底部掉出去（`nullptr`）的地方，新節點就掛在那兒。
// search: returns the node holding key, or nullptr
Node* find(Node* n, int key) {
while (n != nullptr && n->value != key)
n = (key < n->value) ? n->left : n->right;
return n; // each step drops one whole subtree
}
// insert: walk to the empty slot, hang the new node there
Node* insert(Node* n, int key) {
if (n == nullptr) return new Node{key};
if (key < n->value) n->left = insert(n->left, key);
else if (key > n->value) n->right = insert(n->right, key);
return n; // key already present -> no change
}一共有多少層？如果這棵樹是平衡的——每一步左右兩邊節點數大致相同——那麼 n 個節點就裝進大約 log₂ n 層裡。一次查找每層碰一個節點，所以查找、插入、刪除全都花 O(log n)。一百萬個元素，約二十次比較就找到。這就是 BST 存在的全部理由。
當樹爛成了一條鏈結串列
那個 O(log n) 帶著三個你絕不能跳過的字：*當它平衡時*。BST 對一串糟糕的插入順序毫無內建防禦。往一棵空 BST 裡依次插入 1、2、3、4、5：每個值都比之前所有的大，所以總是往右走。你完全得不到分叉——一棵其實是一條單邊鏈子的樹。
insert 1,2,3,4,5 in order:
(1)
\
(2)
\
(3)
\
(4)
\
(5) <- height = n-1, not log n!
searching for 5 now visits all 5 nodes -> O(n)自平衡，以及標準函式庫的饋贈
修法是一棵 [[balanced-tree|自平衡樹]]：每次插入或刪除後，它做一點局部重整（叫作*旋轉*），讓左右兩邊大致持平，於是無論資料以什麼順序到來，高度都貼近 log n。你現在還不需要那套機械，只要這個想法和兩個有名的名字。AVL 樹讓兩側的高度相差不超過 1——平衡得很嚴，所以查找很快。紅黑樹給節點染上紅或黑，並遵守一套染色規則，使它*夠好就行*——比 AVL 略不平衡一點，但維護起來更便宜。
下面是實用的頭條：你幾乎從不親手寫平衡樹。C++ 標準函式庫已經備好了。`std::map` 和 `std::set` 就是平衡二元搜尋樹（實踐中是紅黑樹），所以它們讓鍵保持有序，並保證查找、插入、刪除都是 O(log n)——自動完成，沒有退化情形可怕。當你需要一個有序、可查找的集合時，伸手去拿它們，把平衡的事交給函式庫去做。
#include <map>
std::map<std::string, int> ages; // a balanced BST under the hood
ages["Ana"] = 30; // O(log n) insert
ages["Bo"] = 25;
if (ages.count("Ana")) /* O(log n) lookup */ ;
for (auto& [name, age] : ages) // iterates in SORTED key order
std::cout << name << ' ' << age << '\n';
// prints Ana then Bo, alphabetically -- for free, like in-order.