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

yulihua49

OwnWaterloo 发表于 2012-04-22 11:13
回复 8# yulihua49

还比如基于比较的排序，比较次数下限是n*log(n)，不可能会是log(n)。

我是平衡二叉树，没必要排序了吧？直接查找，应该是log(n);

starwing83

有这么复杂么……算法导论上有详尽的说明，顺便说一下，应用循环不变式这个很好写的

yulihua49

starwing83 发表于 2012-04-23 12:49
有这么复杂么……算法导论上有详尽的说明，顺便说一下，应用循环不变式这个很好写的

循环不变式?不懂。
哎，都说好做，都没有。

OwnWaterloo

很多概念对你来说根本就是一团浆糊。

1. 比如前你提到过的用二叉搜索树完成O(lgN)排序。 根本就是不可能的事情。

2.

yulihua49 发表于 2012-04-23 11:54
一个平衡的二叉树，还有必要使用二分法吗？

鉴于问题已经解决，这个问题转化成一个考题：
在一个平衡二叉树里，如何实现不等查找：
以[O(log2(N))]的代价，找到大于指定值的最小节点。

二叉搜索树的查找使用的就是二分法。 你以为只有数组那个才叫二分吗？
我只是告诉你在搜索树里，如何用两路二分法找到等价区间 —— 这个算法与二叉搜索树是否平衡根本没有关系。
平衡二叉搜索树也是二叉搜索树， 它在搜索时使用与二叉搜索树相同的技巧 —— 二分。
平衡了，自然就是O(lgN)；不平衡，最坏情况就是线性。

于是你说的考题，就是我这个楼的内容。 只是你自己将平衡树、 二分、O(lgN)这些概念搅和在了一起而已。

OwnWaterloo

yulihua49 发表于 2012-04-22 10:08
你测一下时间吧，下周我们比一比。
65535个节点的树，查找一个值需要多少时间。
使用gettimeofday就可以测到微秒级。
1微秒是允许的上限。

本来我以为你会公布源代码的。那这句话都还说得过去（我可是尽量把你往好的方向想啊）。
结果你根本就不给源代码。

yulihua49 发表于 2012-04-23 12:15
测试程序如下(不是算法)：64位的。

没你这样直接用绝对时间比较性能的。 CPU都不同，绝对时间对比较有意义吗？

OwnWaterloo

回复 12# starwing83

本来就是很基础的东西……  难的我也不会……
你去看我在2楼提到的起因……
8页了都……
还打算申请专利呢……

yulihua49

OwnWaterloo 发表于 2012-04-23 13:35
回复 12# starwing83

本来就是很基础的东西……  难的我也不会……

那是扔板砖的话，别当真。
本来就是很基础的东西，不错。
把你们的拿出来晒晒。
楼主的算一个。但我觉得不太理想，学学可以。

yulihua49

OwnWaterloo 发表于 2012-04-23 13:33
本来我以为你会公布源代码的。那这话都还说得过去（我可是尽量把你往好的方向想啊）。
结果你根本就 ...

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

walleeee

回复 17# yulihua49


莫虚伪，伤我眼，你先自己看你自己那个帖子再来说这些屁话

yulihua49

walleeee 发表于 2012-04-23 14:12
回复 17# yulihua49

把火烧到这啦？消消气。免得我又说废话。