代码
Linux kernel 中也使用并实现了红黑树,但是查找算法没有自己实现,而是希望使用者去实现。如果只是实现一个精确查找的函数,这很简单,几乎每个人都能写出正确的代码:
这是 kernel 中 rbtree.h 中给出的示例代码,几乎所有的 kernel search 代码都遵循了这个模式。然而,这个代码的效率有问题,虽然仍是 O(logn) 的。
再看看 stl 中的实现(这只是个简化示例,不完全等同于 stl 中的实际代码):
分析
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 的这个代码更简洁,但稍微费脑子一点。
分享到:
相关推荐
二叉树 二叉树的递归遍历和非递归遍历 二叉树的迭代器 线索二叉树(中序)
C 语言二叉树 搜索 遍历 非递归
实验三 二叉树遍历与路径查找(二叉树实验) 实现功能:建立二叉树存储结构、求二叉树的先序遍历、求二叉树的中序遍历、求二叉树的后序遍历、求二叉树的层次遍历、求根到给定结点的路径。 主控菜单: 1.建立二叉树...
二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树
4) 将二叉树中所有结点的左、右子树相互交换 输入: 扩展二叉树先序序列:ab#d##ce###。其中#代表空指针。 输出: 二叉树的凹入表示 二叉树的先序序列、中序序列、后序序列 二叉树叶子结点个数 左、右子...
(1)输入字符序列,建立二叉链表。...(6)对于树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间。 (8)借助队列实现二叉树的层次遍历。 (9)在主函数中设计一个简单的菜单,分别调试上述算法。
在Linux底下,使用二叉树 读取文档并排序
二叉树排序二叉树排序二叉树排序二叉树排序二叉树排序二叉树排序二叉树排序
设二叉树具有n个带权值的叶子节点,从根节点到叶子节点的路径长度与相应的叶子节点权值的乘积之和叫做二叉树的带权路径长度,记为: WPL=EWkLk 哈夫曼树 给定一组具有确定权值的叶子结点,可以构造出不同的二叉树,...
python编写 实现 快速排序 和 二叉树排序 并对比速度
代码见附件 2 实验内容 ...提示:可以使用 STL 中的 stack 来辅助实现。 2、若二叉树的每一个结点具有数值,如何搜索二叉树,找到指定值的叶子结点? 3、若已知叶子结点的指针,如何输出从根到该叶子的路径?
二叉树的深度优先搜索与广度优先搜索的非递归方法实现
二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树
在二叉树类binarytree中增加一个功能,判断是否为完全二叉树(使用自定义的队列类完成)
每棵子树又都是二叉树,所以构造一棵子树的过程与构造整棵二叉树的过程完全相同(采用递归形式直到叶子结点为止)。 2) 先序序列的输入:从键盘输入任意一棵二叉树的先序序列,用#代表空指针,如下图所示的二叉树,...
树与二叉树_习题树与二叉树_习题树与二叉树_习题
二叉树的建立与遍历,包括二叉树的定义,有参和无参,前序,中序,后序的遍历。
1、 定义链接存储的二叉树类。...3) 在二叉树中搜索给定结点的父结点; 4) 搜索二叉树中符合数据域条件的结点; 3、 由教师随机指定树结构,测试上述功能; 判别给定二叉树是否为完全二叉树。两个要求写了一份代码
2 输出形式和输出值的范围:在所有功能中,二叉树的遍历和查找,输出的是字符型数据,在其他的功能如计算宽度,深度,结点数和叶结点数输出的是整型数据。 3 程序所能达到的功能:生成一个新的二叉树,实现对二叉树...
数据结构 二叉树 用C语言创建与遍历 前序 中序遍历 后序遍历