代码
Linux kernel 中也使用并实现了红黑树，但是查找算法没有自己实现，而是希望使用者去实现。如果只是实现一个精确查找的函数，这很简单，几乎每个人都能写出正确的代码：
static inline struct page * rb_search_page_cache(struct inode * inode,
unsigned long offset)
{
struct rb_node * n = inode->i_rb_page_cache.rb_node;
struct page * page;
while (n)
{
page = rb_entry(n, struct page, rb_page_cache);
if (offset < page->offset)
n = n->rb_left;
else if (offset > page->offset)
n = n->rb_right;
else
return page;
}
return NULL;
}
这是 kernel 中 rbtree.h 中给出的示例代码，几乎所有的 kernel search 代码都遵循了这个模式。然而，这个代码的效率有问题，虽然仍是 O(logn) 的。
再看看 stl 中的实现(这只是个简化示例，不完全等同于 stl 中的实际代码)：
Node* rb_tree::lower_bound(const Key& k) {
Node* y = NULL;
Node* x = root;
while (x != 0)
if (k <= x->key)
y = x, x = x->left;
else
x = x->right;
return y;
}
Node* rb_tree::find(const Key& k) {
Node* y = lower_bound(k);
return y == NULL || k < y->key ? NULL : y;
}
分析
kernel 代码的每个循环中有两个条件判断，而 lower_bound 中只有一个条件判断，虽然在 stl 中，即使在找到相应结点后，可能还需要再继续搜索，然而，鉴于二叉树（平衡树）的结构，深度越深的结点，其数目越多，对于满二叉树，深度增一倍，结点数目就增一倍，最底层（深度最深的那层）结点的数目比所有其它层的总数还要多1。假定满二叉树的高度为k（仅一个结点时定义该高度为0），则结点总数=2^(k+1)-1，针对查找成功的情况，假定每个结点被查找的概率相同，在这两种算法中，满二叉树的平均查找长度为：
linux kernel 的实现
(1*1+2*2+...+(k+1)*2^k))/(2^(k+1)-1) = (1 + k*2^(k+1))/(2^(k+1)-1) = k +(k+1)/(2^(k+1)-1)
(k+1)/(2^(k+1)-1) 在 k 较大时会非常快地趋近于 0，我们可以忽略这一项，结果就是k。
从而，最坏情况下，循环内的判断总次数为 2*k，平均次数是
1.5*k
stl::rb_tree::lower_bound
每个结点的查找都一直到最底层，所以平均查找长度为 k+1，只多 1，然而，循环内的判断次数是 1，所以总的判断次数是 k+1，rb_tree::find 在 lower_bound 找到后需要再判断一次与key 是否相等，总的判断次数就是 K+2 了，但这仍然比 kernel 的判断次数少（k>2 的时候）。虽然这是针对满二叉树的分析，但这可以延伸至平衡的二叉树(log 的底数不再是 2，要比 2 稍微小一点)。
结论
现在应该看到了，虽然 std::lower_bound 没有在找到目标的第一时间就返回，看上去似乎比较傻，但实际上要更快，鉴于现在 CPU 有缓存，分支预测（这个例子循环内的分支预测无法起作用，但CPU还有 speculation，就是同时执行两个分支，然后丢弃错误的那个分支），指令预取等高级功能，lower_bound 比 kernel 快的没有分析的那么多。经过实测，stl 的 rb_tree::find 要比 kernel 的大约快 10% 。
范围查找
如果要范围查找， kernel 的那个实现就不行了，而 lower_bound 是专干这个的（当然，还有个对应的 upper_bound）！
另外，毋庸置疑，stl 的这个代码更简洁，但稍微费脑子一点。