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

walleeee

回复 20# yulihua49


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

yulihua49

OwnWaterloo 发表于 2012-04-23 13:29
很多概念对你来说根本就是一团浆糊。

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

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

OwnWaterloo

yulihua49 发表于 2012-04-23 14:10
现在差不多都是2 .几G的X86，差不多的。-50%,+100%,都无所谓，看看数量级即可。
源代码肯定是要公布的，别着急。

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

yulihua49

walleeee 发表于 2012-04-23 14:18
回复 20# yulihua49

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

yulihua49

OwnWaterloo 发表于 2012-04-23 14:22
我估计你所说的平衡树，本质上依然是朴素的二叉搜索树。 只是采用了不同的平衡方式(rb/avl/splay...)而 ...

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

walleeee

回复 24# yulihua49


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

瞎眼了

walleeee

回复 25# yulihua49


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

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

OwnWaterloo

回复 25# yulihua49

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

你让我怎么说你……

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

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


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

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

yulihua49

OwnWaterloo 发表于 2012-04-23 14:41
回复 25# yulihua49

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

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

walleeee

一个一心想要代码的二货，他哪里肯听ow你在这里跟他啰嗦，你还没看出来么？