免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: OwnWaterloo

[算法][C]二叉搜索树的两路二分查找 [复制链接]

论坛徽章:
0
发表于 2012-04-23 14:18 |显示全部楼层
回复 20# yulihua49


我跟本就不生气,于我何干。你还是看看你自己都说写什么再说吧。那些话都是你说的,我没冤枉你吧?

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2012-04-23 14:20 |显示全部楼层
本帖最后由 yulihua49 于 2012-04-23 14:21 编辑
OwnWaterloo 发表于 2012-04-23 13:29
很多概念对你来说根本就是一团浆糊。

1. 比如前你提到过的用二叉搜索树完成O(lgN)排序。.

那个我早就宣布投降了。
这次我也想投降,但你们要拿出真东西来。

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-04-23 14:22 |显示全部楼层
yulihua49 发表于 2012-04-23 14:10
现在差不多都是2 .几G的X86,差不多的。-50%,+100%,都无所谓,看看数量级即可。
源代码肯定是要公布的,别着急。


我估计你所说的平衡树,本质上依然是朴素的二叉搜索树。 只是采用了不同的平衡方式(rb/avl/splay...)而已。
那么数量级都是O(lgN)……  没跑的……

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2012-04-23 14:23 |显示全部楼层
walleeee 发表于 2012-04-23 14:18
回复 20# yulihua49

你根本就没有了解其中的含义所以才闹出两页废话,咱们还是在那个帖子拼,别污染了这个帖子。

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2012-04-23 14:24 |显示全部楼层
本帖最后由 yulihua49 于 2012-04-23 14:40 编辑
OwnWaterloo 发表于 2012-04-23 14:22
我估计你所说的平衡树,本质上依然是朴素的二叉搜索树。 只是采用了不同的平衡方式(rb/avl/splay...)而 ...

对。我要一个这样的程序,而不是理论。
你的程序挺复杂的,还需要特殊的构造。
能不能直接在平衡二叉树上作呢?
递归一下,几行代码就行了。(不必像你的程序,那么复杂)
我另外那个帖子里有一个“递归一下,几行代码”就可以实现此功能的例子(就是那谁谁谁指责我不着边际的例子),但那不是O(log(N))的。
就是说,你如果给出的不是O(log(N))的就不必了,我原来就有。

论坛徽章:
0
发表于 2012-04-23 14:39 |显示全部楼层
回复 24# yulihua49


滚。我想起来了,你就是那个发明“cu基于比较的logn时间排序”的?

瞎眼了

论坛徽章:
0
发表于 2012-04-23 14:40 |显示全部楼层
回复 25# yulihua49


ow别和他扯了,小心扯破了挡中央

他这几句依然不懂你意思,瞎扯

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-04-23 14:41 |显示全部楼层
本帖最后由 OwnWaterloo 于 2012-04-23 14:42 编辑

回复 25# yulihua49

>> 能不能直接在平衡二叉树上作呢?

你让我怎么说你……

查找等价区间(或者说rb/avl吧,不提splay那种奇葩)的算法只与二叉搜索树的性质 —— 左子树所有节点 <= 根 <= 右子树所有节点 —— 有关。
平衡树也满足这个性质, 直接用直接用就是了……

该算法的效率是O(lgN)还是O(N),与这个算法没关系。
只要平衡,自然就是O(lgN)。


1. "左子树所有节点 <= 根 <= 右子树所有节点" => 可用于查找等价区间
2. 平衡 => 可在O(lgN)时间内完成

这是两个正交正交的概念。

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2012-04-23 14:50 |显示全部楼层
本帖最后由 yulihua49 于 2012-04-23 14:57 编辑
OwnWaterloo 发表于 2012-04-23 14:41
回复 25# yulihua49

>> 能不能直接在平衡二叉树上作呢?

谈远了。
我原本不想扯上什么平衡不平衡的,因为你给了我一个歪树的算法,我不能用这个歪树。
我只想用最少的比较次数,最少也就是那个数了。只有平衡才能得到。
平衡树,只是一个应用场景。
谁能拿出一个最少比较次数的二叉树不等查找程序来?从stl里抄来的也行。

论坛徽章:
0
发表于 2012-04-23 14:57 |显示全部楼层
一个一心想要代码的二货,他哪里肯听ow你在这里跟他啰嗦,你还没看出来么?





您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。




----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP