我一直在使用 C-ish C++ 代码实现各种基于节点的二叉搜索树。在对这些进行基准测试时，我注意到跨编译器和响应小的代码更改都存在令人惊讶的巨大性能差异。
当我专注于在允许重复的树中插入和删除时（就像 C++ 那样std::multiset<int>），我发现几乎所有的时间都花在像“find”和“lower_bound”这样的操作中沿着树的左指针和右指针进行锯齿形移动，而不是比插入和删除之后发生的概念上“昂贵”的重新平衡步骤更重要。
所以我开始特别关注一种情况：下界。
// Node is a binary tree node. It has the
// usual left and right links and an
// integral key.
struct Node {
int key;
Node* links[2];
};
// LowerBound returns the first node in
// the tree rooted at "x" whose key is
// not less than "key", or null if there
// is no such key.
Node* LowerBound(Node* x, int key) {
Node* lower = nullptr;
while …