一条改变一切的规则
一棵普通二叉树只是个形状；它对一个值*该住在哪里*只字未提。[[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.