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

walleeee

回复 50# pandaiam


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

walleeee

回复 47# yulihua49


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

walleeee

回复 50# pandaiam


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

jiyuwoaa

好深奥啊~！！！

lqfhvk357

排序：n*logn
有序二分查找：logn

yulihua49

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. }
   

复制代码

这已经是生产中使用的程序了，而且使用频度很高，所以非常注重效率。

OwnWaterloo

回复 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参数了没？


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

OwnWaterloo

回复 56# yulihua49

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

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

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

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

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

yulihua49

OwnWaterloo 发表于 2012-08-03 23:00
回复 56# yulihua49

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

selfrun

yulihua49 发表于 2012-08-04 22:51
反序比较器是可以的，STL可以接收提供的比较器吗？
另外，有用户不太认可更换比较器的方法，还是要求提供>,>=,<,<=的方法，反正也不费事就都给做了。
科普一下没害处，收了。
bst_max与bst_max_的区别，没看清。抱歉。
习惯问题，一般把有序数组叫二分法，二叉链表叫二叉树，以示方法上的区别，习惯了你的称谓方法，理解上也没问题。
系统的Binary_search(怎么拼写的一时忘了）也是指的对数组的查找。

说句逆耳的话吧，你的基础有点差。大家都看得出，估计是半路出家做这行的吧。建议找本合适的《数据结构》读读，stl的书也挺多，找本看看。