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

OwnWaterloo

davidfoxhu 发表于 2012-08-10 10:06
如果大家闲的没事还觉得自己很牛,给linux内核帮点忙,写的NB的代码,比在这儿无聊强多了!
我们中国这些码农主要是没时间,还得养家糊口.

我不觉得在这儿做的是很无聊的事 —— 按我自己的标准，没主动去做无聊的事。
你觉得这很无聊？ 干嘛主动参合进来做无聊的事？ 你这人得多无聊？

BTW： 除了linux你眼里还看得见啥？

__BlueGuy__

OwnWaterloo 发表于 2012-08-10 16:58
为什么你总是喜欢来充当我的素材呢？

对那些茶余饭后又希望研究点技术、提升自己的层次、跟上潮流的人 ...

OO 我承认求不得，

OO 就像写字一样， 想写的一手好字，是需要日积月累的磨练

OwnWaterloo

__BlueGuy__ 发表于 2012-08-10 17:41
OO 我承认求不得，

OO 就像写字一样， 想写的一手好字，是需要日积月累的磨练

草书越练越潦草啊！为什么不明白！！！

KanonInD

回复 114# hbmhalley

不过很好奇，除了那几个专利问题，要是整套平衡树的操作都用函数式的语言完成，会长成什么模样？

还真有平衡树的Haskell实现：http://hackage.haskell.org/package/AvlTree

__BlueGuy__

OwnWaterloo 发表于 2012-08-10 22:33
草书越练越潦草啊！为什么不明白！！！

我是 c 出身的，对 OO有着清醒的认识 ,!

OO 真的很博大精深

OwnWaterloo

__BlueGuy__ 发表于 2012-08-11 18:17
我是 c 出身的，对 OO有着清醒的认识 ,!

OO 真的很博大精深

C出身与对OO有清醒认识之间有什么联系？
OO与勃大茎深之间又有什么联系？

yulihua49

OwnWaterloo 发表于 2012-08-04 23:33
回复 59# yulihua49
1. > k 的元素是[m.upper_bound(k), m.end())
2. >= k 的元素是[m.lower_bound(k), m.end())
3. < k 的元素是[m.begin(), m.lower_bound(k))
4. <= k 的元素是[m.begin(), m.upper_bound(k))



stl接口比较保守。比较器的粒度是map的类型，也就是instances的整个生命周期。

说实在的，原先对你的程序不是很懂，前两个月左右看懂了。
并对我的程序有所改进。感谢你的耐心。
不过上述四个条件，就是理论上可行，实际不那么好用了，所以我还是老老实实提供四个函数。

_GT();
_GE();
_LT();
_LE();

在正序树上进行反序比较是不可以的。
我要求的是<KEY的最大的那一个节点。
相当于3，不要集合，只要一个。

yulihua49

starwing83 发表于 2012-08-08 10:13
回复 74# OwnWaterloo

看了你的说明：
1.v一定在[left, right)范围内（由定义可得）。
实际的应用不完全符合你的理论定义。
我们并不知道符合>=KEY的节点是否存在，我们的用户需求是：如果不存在，请返回NULL。
OW的算法基本是可以的，取消哨兵，用NULL取代即可。
ow 完全可以写教科书，出习题了。
题目有点不直观，直接叫二叉树不等查找的方法。

starwing83

回复 128# yulihua49


    我没说清楚，应该说，由定义得，v一定在[left, right]范围内。这句话的意思是，v的值比left大，比right 小，但是未必就在那个数组里面。

yulihua49

OwnWaterloo 发表于 2012-08-09 20:13
回复 98# starwing83

尤其是这楼本来就有潜在受众，写成尾递归然后说这能够被优化为循环，肯定会被yulihua49当成小白的啊。那时候再解释就无力了啊。。。

哈，我有那么凶恶吗？