免费注册 查看新帖 |

Chinaunix

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

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

论坛徽章:
0
发表于 2012-04-29 00:32 |显示全部楼层
回复 50# pandaiam


    算了,免得再次被封。你全部看完,然后你就明白

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


唉,现在好了,遭此大劫,必有后福

论坛徽章:
0
发表于 2012-04-29 00:38 |显示全部楼层
回复 50# pandaiam


还有,我不知道你到底是说ow的那个帖子,还是yulihua49的那个帖子。这是2马事情。你整体看看,就明白为什么会有你说的,真的很疯。它们逼的

论坛徽章:
0
发表于 2012-04-29 00:48 |显示全部楼层
好深奥啊~!!!

论坛徽章:
0
发表于 2012-06-01 16:38 |显示全部楼层
排序:n*logn
有序二分查找:logn

论坛徽章:
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-08-03 21:03 |显示全部楼层
本帖最后由 yulihua49 于 2012-08-04 22:56 编辑
OwnWaterloo 发表于 2012-04-21 18:04
bst_t* bst_upper(bst_t** t, ptrdiff_t cmp(void* e, void* k), void* k) {

      bst_t* bound  = bst_max(t);

      bst_t* middle = bound->p[0]//找到正根

      while (middle)

            cmp(middle,k) <= 0

                  ? middle = middle->p[1]

                  : (bound = middle, middle = middle->p[0]);

      return bound;

}

...

边界哨兵还是去掉吧,找不到就是NULL别给人家错误的结果。
我的需求与STL稍有差异,不是重码,而是在一个序列中找到>,>=.<,<= 的值。下面的程序多简单,一次搜索定乾坤,而且肯定是最短路径。不需要父节点(平衡树,平衡旋转时带爹不好转),也没必要搞个边界什么的,没有符合条件的,返回NULL即可。否则,我要求这个树既有>也有<,你还弄两个边界不成?
  1. T_Tree * BB_Tree_GT(T_Tree *sp,void *content_key,int len,
  2.                 int (*Cmp_rec)(void *s1,void *s2,int len))
  3. {//比K大的最小节点
  4. T_Tree *t;
  5.        return !sp?sp:(0>=Tree_Cmp(sp->Content,content_key,len,Cmp_rec))?
  6.                 BB_Tree_GT(sp->Right,content_key,len,Cmp_rec)://一直往右,肯定NULL
  7.                 (t=BB_Tree_GT(sp->Left,content_key,len,Cmp_rec))?t:sp;//只要向左,必有结果。
  8. }
复制代码
这已经是生产中使用的程序了,而且使用频度很高,所以非常注重效率。

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

回复 56# yulihua49

bst_t* bst_max(bst_t** self) { return (bst_t*)self; }

你认为这是一次搜索。

bst_t* bst_lower(bst_t** t, ptrdiff_t cmp(void* e, void* k), void* k)

你问我怎么又有<又能小于又有>又能大于。看到cmp参数了没?


和你讨论怎么就这么累呢?真是替你捉急。。。
除了复制粘贴、不懂举一反三、一点理论基础都没有,别侮辱码农的称号了好吗?

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-04 20:14 |显示全部楼层
回复 56# yulihua49

对这问题最后给你科普一次。

1. 二分的基础条件是有序。
对数组,前趋一定小于(小于等于/大于/大于等于)后继。
对树(包括数组模拟的),左子树小于根小于右子树。

2. 通常人们在说二分时,实际指的是三分: 小于区间、中点、大于区间。
对有相等的key的情况, 三分是不能准确找出相当区间的边界的。
真正的二分只分成两个区间, 然后选其一; 重复这个过程直到区间只有一个元素时退出(而不是三分的相等就退出)。 这样就可以找到相等区间的边界。
这贴就是在介绍树的真正二分。
重要的话我再多说一遍: 二分(无论哪种)只依赖有序性质。  所以你说我这不是平衡树,不如你的快,反而是在暴露你的无知。

3. 对树,二分的效率取决与高度。
这时才需要(自)平衡树。
而对数组来说,类似节点是密集的情况,所以不存在这个问题。
重要的话我继续多说: 二分搜索找边界与二分搜索的效率是不相干的两个问题。同样的算法, 树平衡了就是对数时间, 不平衡就可能导致线性时间。
始终认为这是一个问题(快速搜索边界)而不是两个不同问题(二路保证边界+平衡保证速度)的你, 一直在晒你的无知。

4. 另外一些杂项。
(自)平衡树与AVL树是不同的概念。log2(N)与lg(N)与O(lg(N))也是不同的概念 —— 你搞不清楚就不要随口说。 你以为显得你很懂? 其实是显得你很无知。
还有,拜托,以后不要不断在其他人问排序的贴里说用平衡树排序, 吃饱了撑得慌? 有这么多inplace算法非要去建颗树? 很笑人的你知道吗。 还是说你只会这招?

论坛徽章:
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-08-04 22:51 |显示全部楼层
本帖最后由 yulihua49 于 2012-08-04 23:27 编辑
OwnWaterloo 发表于 2012-08-03 23:00
回复 56# yulihua49

反序比较器是可以的,STL可以接收提供的比较器吗?
另外,有用户不太认可更换比较器的方法,还是要求提供>,>=,<,<=的方法,反正也不费事就都给做了。
科普一下没害处,收了。
bst_max与bst_max_的区别,没看清。抱歉。
习惯问题,一般把有序数组叫二分法,二叉链表叫二叉树,以示方法上的区别,习惯了你的称谓方法,理解上也没问题。
系统的Binary_search(怎么拼写的一时忘了)也是指的对数组的查找。
试了各种方法,就是二叉树快,所以就向人推荐,也没有错啊。这也不涉及我会什么,不会什么,即使我什么都不会,各种工具系统里都有,拿来用就是。
你从文件里读出一堆数据,把他们摆好了(摆也是个难事,不知道要多大空间),再排序;还是边读边往树里插(节点自动分配),读完了,序也排好了,哪个快?

论坛徽章:
1
技术图书徽章
日期:2014-03-06 15:32:30
发表于 2012-08-04 23:24 |显示全部楼层
yulihua49 发表于 2012-08-04 22:51
反序比较器是可以的,STL可以接收提供的比较器吗?
另外,有用户不太认可更换比较器的方法,还是要求提供>,>=,<,<=的方法,反正也不费事就都给做了。
科普一下没害处,收了。
bst_max与bst_max_的区别,没看清。抱歉。
习惯问题,一般把有序数组叫二分法,二叉链表叫二叉树,以示方法上的区别,习惯了你的称谓方法,理解上也没问题。
系统的Binary_search(怎么拼写的一时忘了)也是指的对数组的查找。


说句逆耳的话吧,你的基础有点差。大家都看得出,估计是半路出家做这行的吧。建议找本合适的《数据结构》读读,stl的书也挺多,找本看看。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

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

限时8.5折扣期:2019年9月30日前


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

大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP