树与层次结构
二叉搜索树
二叉搜索树是一棵多出一条承诺、从而变得可查找的二叉树：对每个节点而言，它左子树中的所有键都比该节点的键小，右子树中的所有键都比它大。这条排序不变式在每个节点、一直到底都成立。它就是有序数组在树形上的表亲。
仅凭这一条规则，你就能像玩“猜大小”游戏一样找键。从根出发；如果目标更小就往左，更大就往右，直到命中或走到底端为止。每一步都丢掉整整一棵子树，所以当树平衡时，你每次都把候选范围减半，于是查找、插入或删除的开销都是 O(log n)。按“左、自身、右”的顺序遍历这棵树，甚至能免费地把键按升序读出来。
问题在于：这种速度完全依赖于树保持枝繁叶茂。如果你把已经排好序的数据插入一棵普通的二叉搜索树，每个新键都比上一个大，树就会长成一条又长又细的单枝——也就是退化树——查找随即跌回 O(n)，并不比扫一遍列表更快。正是这种脆弱催生了平衡搜索树：它们在插入时多做一些工作，无论数据以什么顺序到来，都把树高维持在接近 log n。
Node* find(Node* root, int key) {
while (root != nullptr) {
if (key == root->value) return root;
root = (key < root->value) ? root->left
: root->right;
}
return nullptr; // not found
}迭代式二叉搜索树查找——树平衡时为 O(log n)。
平衡的二叉搜索树查找为 O(log n)；退化成藤蔓状的二叉搜索树则跌到 O(n)——不变式只保证顺序，不保证形状。
又称
另见