免费注册 查看新帖 |

Chinaunix

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

二叉树不等查找的算法谁清楚?前些日子发表CSTL的大侠说说看 [复制链接]

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


    给你一个提示吧:

假设现在以A为根,它的左右儿子为别为B,C。
我们现在要在里面找一个比a大且最小的元素,设V[A]表示A结点的值,它们比较关系用>,<,=来表示。(如果有重复元素,请稍作修改即可。)

1.比较V[A]与a,如果V[A]=a,那么就是它右儿子为根的最左结点
2.V[A]<a,所求和值一定要右儿子为根的子树中(或者不存在),故与原问题相同。
3.V[A]>a,我们现在就得到一个值V[A]是满足条件的,但它不一定是最小的,还有可能有更优的在它左儿子为根的子树中。以B为根的树再进行上面迭代,同时更新最优值即可。

这样复杂度就能达到O(logN)了,但是其中得保证这个二叉树足够随机,当时用其它一些结构也可以。

像前面提到的STL里面的MAP,一般是用Reb-Black Tree实现的,它就能保证N个结点的树的深度不超过log2N.
根据具体需求做就行了,大概就是上面这个意思。

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


你建表不能有序么?

有什么区别?

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


解决什么问题。

你这个函数是想计数么?你前面不是在find么?怎么这里又变成count了。

论坛徽章:
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-20 19:56 |显示全部楼层
walleeee 发表于 2012-04-20 15:18
回复 39# yulihua49

count 是个原有的函数,利用它的回调函数,可以做任何查找,但效率低。
因为前边有人提出排序,我就说这个就等于排序。

论坛徽章:
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-20 19:59 |显示全部楼层
本帖最后由 yulihua49 于 2012-04-20 20:01 编辑
_Rayx 发表于 2012-04-20 15:03
回复 38# yulihua49

这个差不多可以了。但是map里没提供现成的功能?

这样复杂度就能达到O(logN)了,但是其中得保证这个二叉树足够随机,当时用其它一些结构也可以。
我们的树是平衡树,查找效率应该比rb树好。

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


算了。你还是研究sort再查找。当然,你也可以直接遍历一遍来找min_max/max_min。我那个算法你也可以用,只是我没空去验证和证明,你要用就要多去实验。

论坛徽章:
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-20 20:05 |显示全部楼层
本帖最后由 yulihua49 于 2012-04-20 20:07 编辑
walleeee 发表于 2012-04-20 20:00
回复 44# yulihua49

排序就算了,二叉树已经是有序的了,在排一次没必要。
我要的是速度。
在百万结点的数据库中(oracle),查找一次需要100-150微秒,mongodb需要80微秒。
人家认为慢的不可接受。
在这规模的二叉树里查询,1微秒是允许的极限。任何排序和重组数据的操作都不可以。

论坛徽章:
0
发表于 2012-04-20 20:06 |显示全部楼层
回复 47# 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-20 20:09 |显示全部楼层
本帖最后由 yulihua49 于 2012-04-20 20:21 编辑

删帖的钮在哪?谁知道?原来有的,新版找不到了。

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


好啊,到时我一定看。你可以写个总结出来,新开一帖出来。看看大家是不是会提一些没考虑到的问题。
这个也是一个好事情
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP