Chinaunix

标题: 二叉树不等查找的算法谁清楚？前些日子发表CSTL的大侠说说看 [打印本页]

作者: yulihua49 时间: 2012-04-19 14:50
标题: 二叉树不等查找的算法谁清楚？前些日子发表CSTL的大侠说说看
本帖最后由 yulihua49 于 2012-04-20 12:25 编辑

在二叉树里查找大于指定值的最小节点或小于指定值的最大节点。
树不含横向链（不是B+树），没有父节点指针。
谁能给出一个算法？

在网上搜了一下“二叉树不等查找”，居然只有我这一贴。
难道别人没有这个需求吗？未见到相关报道，我要是做出来了，可以申请专利吗？

需要的功能：
tree_find_EQ 这个实现了。
tree_find_GT 大于KEY中最小的一个。
tree_fine_GTEQ    >=
tree_find_LT  小于KEY中最大的一个。
tree_find_LTEQ    <=
.......

作者: walleeee 时间: 2012-04-19 15:11
查找二叉树

作者: _Rayx 时间: 2012-04-19 15:15
看得看这个二叉树满足什么条件了，如果这个树就是一个平常的，那么就只能遍历记录了。
当然上面那种如果二叉树的结构不会改变的吧，可以把树拆成结点排序，再二分查找就行了。

如果二叉树满足左儿子小于父结点，右儿子大于父结点就分情况讨论就行了。

作者: yulihua49 时间: 2012-04-19 15:41
本帖最后由 yulihua49 于 2012-04-19 15:41 编辑

_Rayx 发表于 2012-04-19 15:15
看得看这个二叉树满足什么条件了，如果这个树就是一个平常的，那么就只能遍历记录了。
当然上面那种如果二 ...

二叉树满足左儿子小于父结点，右儿子大于父结点，没有值重复的节点。有算法么？

作者: zhaohongjian000 时间: 2012-04-19 15:41
正常查找，把遇到的最后一个大于要查的key的节点和最后一个小于要查的key的节点记下来就是了。

作者: yulihua49 时间: 2012-04-19 15:42
本帖最后由 yulihua49 于 2012-04-19 15:44 编辑

zhaohongjian000 发表于 2012-04-19 15:41
正常查找，把遇到的最后一个大于要查的key的节点和最后一个小于要查的key的节点记下来就是了。

遍历？
希望按深度查找，实现O（log2（N））。

作者: zhaohongjian000 时间: 2012-04-19 15:44

yulihua49 发表于 2012-04-19 15:42
遍历？
希望按深度查找，实现O（log2N）。

就是正常的查找啊，难道这个二叉树不是有序的？

作者: 鸡丝拌面 时间: 2012-04-19 15:45
遍历＋前驱后继。

作者: yulihua49 时间: 2012-04-19 15:46

zhaohongjian000 发表于 2012-04-19 15:44
就是正常的查找啊，难道这个二叉树不是有序的？

正常查找是递归的，记不住上下文。

作者: yulihua49 时间: 2012-04-19 15:47
本帖最后由 yulihua49 于 2012-04-19 15:49 编辑

鸡丝拌面发表于 2012-04-19 15:45
遍历＋前驱后继。

没有前驱后继，不是B+树。
正常查找：

T_Tree * BB_Tree_Find(T_Tree *sp,void *content_key,int len,
int (*Cmp_rec)(void *s1,void *s2,int len))
{
int rc;
//rc=sp-key
return !sp?sp:!(rc=Tree_Cmp(sp->Content,content_key,len,Cmp_rec))?sp:
(rc>0)?BB_Tree_Find(sp->Left,content_key,len,Cmp_rec):
BB_Tree_Find(sp->Right,content_key,len,Cmp_rec);
}

复制代码

作者: zhaohongjian000 时间: 2012-04-19 15:48
本帖最后由 zhaohongjian000 于 2012-04-19 15:52 编辑

yulihua49 发表于 2012-04-19 15:46
正常查找是递归的，记不住上下文。

你不会加两个变量记住啊。

反应过来了，非递归查找呗。

作者: yulihua49 时间: 2012-04-19 15:52
本帖最后由 yulihua49 于 2012-04-19 15:54 编辑

zhaohongjian000 发表于 2012-04-19 15:48
你不会加两个变量记住啊。

在栈里，每个变量都在不同的层，全局变量不能用，要求线程安全。
查找程序，那个rc就在栈里，每层都是单独的，没有共享变量。

T_Tree * BB_Tree_Find(T_Tree *sp,void *content_key,int len,
int (*Cmp_rec)(void *s1,void *s2,int len))
{
int rc;
//rc=sp-key
return !sp?sp:!(rc=Tree_Cmp(sp->Content,content_key,len,Cmp_rec))?sp:
(rc>0)?BB_Tree_Find(sp->Left,content_key,len,Cmp_rec):
BB_Tree_Find(sp->Right,content_key,len,Cmp_rec);
}

复制代码

作者: zhaohongjian000 时间: 2012-04-19 15:54

yulihua49 发表于 2012-04-19 15:52
在栈里，每个变量都在不同的层，全局变量不能用，要求线程安全。

刚才呆了，非递归查找呗，也就多写点代码。

作者: yulihua49 时间: 2012-04-19 15:56
本帖最后由 yulihua49 于 2012-04-19 16:04 编辑

zhaohongjian000 发表于 2012-04-19 15:54
刚才呆了，非递归查找呗，也就多写点代码。

麻烦了。
上边的代码只能查找相等的，在查找过程中不一定能够碰上比他大还是比他小的节点。

而且他的父节点可能是大的或小的之一，另一个可能离得很远。

作者: zhaohongjian000 时间: 2012-04-19 16:00

yulihua49 发表于 2012-04-19 15:56
麻烦了。

这样也嫌麻烦，你是想要啥样的算法呀。。。

还是递归，用来记录的变量在最外层函数中分配在栈上。

作者: yulihua49 时间: 2012-04-19 16:07
本帖最后由 yulihua49 于 2012-04-19 16:19 编辑

zhaohongjian000 发表于 2012-04-19 16:00
这样也嫌麻烦，你是想要啥样的算法呀。。。

还是递归，用来记录的变量在最外层函数中分配在栈上。

作为地址带下去？
你能写一个试试看？我等着，多谢。
查找大于或小于之一即可。

我做的是通用软件，不是简单的数字哦！
Content是应用定义的数据，由回调函数提供应用的比较器使用，比较结果只有>0(节点〉key），=0，〈0，没有具体值。
所以那个变量存的啥东西，不知道。

在做一个内存的数据库。现在都64位时代了，内存放数百万的数据供多线程共享使用完全是可行的。
动态的AVL树，增删改查。。。。。。

作者: zhaohongjian000 时间: 2012-04-19 16:18
本帖最后由 zhaohongjian000 于 2012-04-19 16:42 编辑

yulihua49 发表于 2012-04-19 16:07
作为地址带下去？
你能写一个试试看？我等着，多谢。
查找大于或小于之一即可。

T_Tree * BB_Tree_Find_Less_Max(T_Tree *sp,void *content_key,int len,
int (*Cmp_rec)(void *s1,void *s2,int len))
{
T_Tree *lessMax = NULL;
BB_Tree_Find_Less_Max_(sp, content_key, len, &lessMax);
return lessMax;
}
T_Tree * BB_Tree_Find_Less_Max_(T_Tree *sp,void *content_key,int len,
int (*Cmp_rec)(void *s1,void *s2,int len), T_Tree **lessMax)
{
if(/*key的值更大*/)
*lessMax = sp;
else if(/*key的值和当前节点相等*/)
;//返回左子树的最大节点
//以下略
}

复制代码

作者: yulihua49 时间: 2012-04-19 16:20
本帖最后由 yulihua49 于 2012-04-19 16:27 编辑

zhaohongjian000 发表于 2012-04-19 16:18

多谢，我读读看，再说。

你这个需要遍历，当数百万的记录，效率？

大概，一个节点，它值相邻的节点或是在查找的路径上，或是在左右儿子。

作者: zhaohongjian000 时间: 2012-04-19 16:26

yulihua49 发表于 2012-04-19 16:20
多谢，我读读看，再说。

你这个需要遍历，当数百万的记录，效率？

不需要啊，以下略的代码把你那个return那行贴过去就行了。这不就是二叉树的递归查找吗。

作者: yulihua49 时间: 2012-04-19 16:29
本帖最后由 yulihua49 于 2012-04-19 16:34 编辑

zhaohongjian000 发表于 2012-04-19 16:26
不需要啊，以下略的代码把你那个return那行贴过去就行了。这不就是二叉树的递归查找吗。

当是左右儿子的情况根本就找不到。
例如在15节点的满平衡树，12号节点的左右临近值，11号和13号都是12号的孙子。更深的后代也可能。
就是说仅仅找到相等节点时不够的，至少要遍历后代到底。
如果根本没有相等的值呢？

作者: zhaohongjian000 时间: 2012-04-19 16:33

yulihua49 发表于 2012-04-19 16:29
当是左右儿子的情况根本就找不到。

额，光考虑key查不到的情况了。

如果key查到了，那就返回左子树的最大节点/右子树的最小节点（这两个操作应该有现成函数吧）。如果又觉得麻烦，那我没办法了。

作者: yulihua49 时间: 2012-04-19 16:36

zhaohongjian000 发表于 2012-04-19 16:33
额，光考虑key查不到的情况了。

如果key查到了，那就返回左子树的最大节点/右子树的最小节点（这两个 ...

你能帮我动这个脑筋很好，办法一定会有的，而且不会太复杂。

作者: walleeee 时间: 2012-04-19 16:37
我不知道你还是看什么。我二楼不就说了，二叉查找树，也叫二叉排序树。

根据你的描述，就是找一个值的小于他的最大的值和大于他的最小的值，二叉排序树不就是左儿子小于他，右儿子大于他这种的递归定义么
比如1,3,7,8,5这个序列
建树
1

1
3

1
3
   7

1
3
   7
      8

1
3
   7
5    8

找7，直接就是（5，8）
，比如再加几个，6，4
1
3
   7
5    8
   6

1
3
   7
5    8
4 6
找5，直接就是（4，6）

我对你的问题理解就是这样。如果你觉得二叉查找树对于大量随机效率比较低，那你可以走平衡二叉查找树，比如avl，这些。

作者: walleeee 时间: 2012-04-19 16:45
回复 20# yulihua49

既然有没有在树中这个情况，那又是另外一说了

作者: zhaohongjian000 时间: 2012-04-19 16:45

yulihua49 发表于 2012-04-19 16:36
你能帮我动这个脑筋很好，办法一定会有的，而且不会太复杂。

办法还是那个，17层编辑过了。

作者: zhaohongjian000 时间: 2012-04-19 16:48

yulihua49 发表于 2012-04-19 16:29
当是左右儿子的情况根本就找不到。
例如在15节点的满平衡树，12号节点的左右临近值，11号和13号都是12号 ...

如果查找过程没找到，那么一定是遍历到底的，遇到的最后一个小于key的节点就是小于key的最大节点。

如果找到了key就简单多了，自然就是左子树的最大节点。

作者: yulihua49 时间: 2012-04-19 16:50
本帖最后由 yulihua49 于 2012-04-19 16:51 编辑

zhaohongjian000 发表于 2012-04-19 16:18

if(/*key的值更大*/)

*lessMax = sp;

if(node < key && node>lessMax) lessMax=node;

有点靠谱了。
沿着一个路径插到底。

作者: walleeee 时间: 2012-04-19 16:51
不知道这么行不行，没验证。

右递归，知道转折，比如
1
3
   7
5    8
   6
找4。递归到第一次左转，就是3，7之间，这时记录3，作为小于他的最大值。然后左递归，直到不能继续，就到了5，记录作为大于他的最小，于是就是（3，5）。这是对的。同样，你可以开始就左递归，但是一旦转折就立马右递归，这是第一个记录就成了大于他的最小值，第二次记录是小于他的最大值。
当然，还有一个情况就是前面说的，碰到正好匹配了，这个时候就是左右儿子。

留待验证

作者: yulihua49 时间: 2012-04-19 16:54
本帖最后由 yulihua49 于 2012-04-19 16:58 编辑

walleeee 发表于 2012-04-19 16:51
不知道这么行不行，没验证。

右递归，知道转折，比如

想法很好，不过你们见到有文献介绍这个算法的吗？我是比较孤陋寡闻，如果有给我个连接？
我见过的所有资料都有等值查找，没有不等式查找。
一般的需求，只要大于或小于之一即可，还有就是区间，可以由单个的大于或小于组合而成。

作者: zhaohongjian000 时间: 2012-04-19 16:54
本帖最后由 zhaohongjian000 于 2012-04-19 16:59 编辑

walleeee 发表于 2012-04-19 16:51
不知道这么行不行，没验证。

右递归，知道转折，比如

是这样的，我就是一直在向LZ解释这个...

但匹配的时候不是左右儿子，而是左子树的最大节点（最右节点）和右子树的最小节点（最左节点）。

话说，我好像重复了好多遍这句话了......

作者: walleeee 时间: 2012-04-19 16:56
回复 29# yulihua49

没有。我是临时想起，所以我标注了“留待验证”。你最好多实验一下，免得出问题。

作者: walleeee 时间: 2012-04-19 16:57
回复 30# zhaohongjian000

。。。。

作者: yulihua49 时间: 2012-04-19 17:04

walleeee 发表于 2012-04-19 16:56
回复 29# yulihua49

STL有没有提供map的不等查询？

作者: walleeee 时间: 2012-04-19 17:06
回复 33# yulihua49

你也别在这里纠结了，你二分查找吧。

其实二叉树就是二分思想的体现，前面说的那些，都是二分。你排序后二分吧。

作者: walleeee 时间: 2012-04-19 17:06
回复 33# yulihua49

stl好像有个sort，你完了在二分

作者: walleeee 时间: 2012-04-19 17:08
stl那个sort还是很快。你百万级别的数据根本就不是什么问题。

当然，对象的拷贝复制任然是一个问题。这些细节你要留心。

作者: _Rayx 时间: 2012-04-19 17:17
回复 4# yulihua49

算法导论里面有比较详细的解答

作者: yulihua49 时间: 2012-04-20 11:28

_Rayx 发表于 2012-04-19 17:17
回复 4# yulihua49

能提供一下吗？多谢了。

作者: yulihua49 时间: 2012-04-20 11:30
本帖最后由 yulihua49 于 2012-04-20 11:41 编辑

walleeee 发表于 2012-04-19 17:06
回复 33# yulihua49

下面的函数可以解决这个问题，但效率？等于是排序了。

//bt为根结点的指针，返回值为bt的节点数
// context为应用提供的上下文数据，由counter使用
//counter由应用提供，判断是否符合计数条件，不符合返回0.
int BB_Tree_Count(T_Tree * bt,void *context,
int (*counter)(T_Tree *bt,void *context))
{
return !bt?0:(BB_Tree_Count(bt->Left,context,counter) +
((counter)?counter(bt,context):1) +
BB_Tree_Count(bt->Right,context,counter));
}

复制代码

这个函数解决了 select count(*) from tree 的问题，也是内存数据库的一个核心组件。
它正序调用counter,你的counter把结果放在context里就是了。

作者: yulihua49 时间: 2012-04-20 11:39

walleeee 发表于 2012-04-19 17:06
回复 33# yulihua49

不行啊，数据是动态的，随时从数据库加载新的数据或删除旧的数据。
它是ORACLE的一个表的内存CACHE。

作者: _Rayx 时间: 2012-04-20 15:03
回复 38# yulihua49

给你一个提示吧：

假设现在以A为根，它的左右儿子为别为B，C。
我们现在要在里面找一个比a大且最小的元素，设V［A］表示A结点的值，它们比较关系用>,<,=来表示。（如果有重复元素，请稍作修改即可。）

1.比较V[A]与a，如果V[A]=a，那么就是它右儿子为根的最左结点
2.V［A］<a,所求和值一定要右儿子为根的子树中（或者不存在），故与原问题相同。
3.V［A］>a，我们现在就得到一个值V[A]是满足条件的，但它不一定是最小的，还有可能有更优的在它左儿子为根的子树中。以B为根的树再进行上面迭代，同时更新最优值即可。

这样复杂度就能达到O(logN)了，但是其中得保证这个二叉树足够随机，当时用其它一些结构也可以。

像前面提到的STL里面的MAP，一般是用Reb-Black Tree实现的，它就能保证N个结点的树的深度不超过log2N.
根据具体需求做就行了，大概就是上面这个意思。

作者: walleeee 时间: 2012-04-20 15:10
回复 40# yulihua49

你建表不能有序么？

有什么区别？

作者: walleeee 时间: 2012-04-20 15:18
回复 39# yulihua49

解决什么问题。

你这个函数是想计数么？你前面不是在find么？怎么这里又变成count了。

作者: yulihua49 时间: 2012-04-20 19:56

walleeee 发表于 2012-04-20 15:18
回复 39# yulihua49

count 是个原有的函数，利用它的回调函数，可以做任何查找，但效率低。
因为前边有人提出排序，我就说这个就等于排序。

作者: yulihua49 时间: 2012-04-20 19:59
本帖最后由 yulihua49 于 2012-04-20 20:01 编辑

_Rayx 发表于 2012-04-20 15:03
回复 38# yulihua49

这个差不多可以了。但是map里没提供现成的功能？

这样复杂度就能达到O(logN)了，但是其中得保证这个二叉树足够随机，当时用其它一些结构也可以。
我们的树是平衡树，查找效率应该比rb树好。

作者: walleeee 时间: 2012-04-20 20:00
回复 44# yulihua49

算了。你还是研究sort再查找。当然，你也可以直接遍历一遍来找min_max/max_min。我那个算法你也可以用，只是我没空去验证和证明，你要用就要多去实验。

作者: yulihua49 时间: 2012-04-20 20:05
本帖最后由 yulihua49 于 2012-04-20 20:07 编辑

walleeee 发表于 2012-04-20 20:00
回复 44# yulihua49

排序就算了，二叉树已经是有序的了，在排一次没必要。
我要的是速度。
在百万结点的数据库中（oracle），查找一次需要100－150微秒，mongodb需要80微秒。
人家认为慢的不可接受。
在这规模的二叉树里查询，1微秒是允许的极限。任何排序和重组数据的操作都不可以。

作者: walleeee 时间: 2012-04-20 20:06
回复 47# yulihua49

那你自己选择吧。这个你自己要进行调整

作者: yulihua49 时间: 2012-04-20 20:09
本帖最后由 yulihua49 于 2012-04-20 20:21 编辑

删帖的钮在哪？谁知道？原来有的，新版找不到了。

作者: walleeee 时间: 2012-04-20 20:10
回复 49# yulihua49

好啊，到时我一定看。你可以写个总结出来，新开一帖出来。看看大家是不是会提一些没考虑到的问题。

这个也是一个好事情

作者: yulihua49 时间: 2012-04-20 20:12
本帖最后由 yulihua49 于 2012-04-20 20:14 编辑

walleeee 发表于 2012-04-20 20:10
回复 49# yulihua49

最终是要搞一个内存数据库。这些是它的核心组件。
持久化由关系数据库构成，本地内存是cache。

作者: walleeee 时间: 2012-04-20 20:14
回复 51# yulihua49

随便你吧。内存数据库前面挺火的，很久没关注。

你到时总结出来，开新帖就好，其他没什么了

作者: yulihua49 时间: 2012-04-20 20:18

_Rayx 发表于 2012-04-20 15:03
回复 38# yulihua49

你那个思路可以，跟我想的差不多，下周可以有结果了，你感兴趣的话，下周来关注这个帖子。
我很奇怪，之前人们对此没有需求吗？为什么见不到相关的算法、文献和程序？

作者: _Rayx 时间: 2012-04-20 21:27
回复 53# yulihua49

应该是有的，这个就是基本的数据结构啊。

作者: selfrun 时间: 2012-04-21 08:18
map有lower bound

作者: yulihua49 时间: 2012-04-23 12:03
本帖最后由 yulihua49 于 2012-04-23 12:21 编辑

selfrun 发表于 2012-04-21 08:18
map有lower bound

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

测试结果已经有了：
查找一个65535节点的平衡树，耗时<0.3微秒。

MIN=3544227908739109,MAX=3544227908885454,n=65535
at 3544227908739109-3544227908885454,time=146345
input VAL:
3544227908739109
val=3544227908739166,time=2626 //10000次的微秒数
3544227908885450
val=3544227908885452,time=2610
q
Del 65535 TIMEVAL=34704

作者: yulihua49 时间: 2012-04-23 12:15
本帖最后由 yulihua49 于 2012-04-23 12:37 编辑

yulihua49 发表于 2012-04-23 12:03
好的。
鉴于问题已经解决，这个问题转化成一个考题：
在一个平衡二叉树里，如何实现不等查找：

测试程序如下(不是算法)：64位的。

main()
{
long a[NUM];
int i,n;
T_Tree *val,*root=NULL;
INT64 now,min,max;
for(i=0;i<NUM;i++) {
a[i]=now_usec()+i;
root=BB_Tree_Add(root,&a[i],sizeof(long),t_cmp,0);
}
val=BB_Tree_MIN(root);
min=val?*(INT64 *)val->Content:-1;
val=BB_Tree_MAX(root);
max=val?*(INT64 *)val->Content:-1;
n=BB_Tree_Count(root,NULL,NULL);
printf("MIN=%lld,MAX=%lld,n=%d\n",min,max,n);
printf("at %lld-%lld,time=%ld\ninput VAL:\n",a[0],a[NUM-1],a[NUM-1] - a[0]);
//debug=1;
while(1==scanf("%lld",&now)) {
// val=BB_Tree_Find(root,&now,sizeof(INT64),t_cmp);
// val=BB_Tree_GT(root,&now,sizeof(INT64),t_cmp);
// val=BB_Tree_GTEQ(root,&now,sizeof(INT64),t_cmp);
// val=BB_Tree_LT(root,&now,sizeof(INT64),t_cmp);
// val=BB_Tree_LTEQ(root,&now,sizeof(INT64),t_cmp);
min=now_usec();
for(i=0;i<10000;i++)
val=BB_Tree_GT(root,&now,sizeof(INT64),t_cmp);
min=now_usec()-min;
if(!val) printf("NULL,time=%lld\n",min);
else printf("val=%lld,time=%lld\n",*(INT64 *)val->Content,min);
}
debug=0;
now=now_usec();
for(i=0;i<NUM;i++) {
n=0;
root=BB_Tree_Del(root,&a[i],sizeof(long),t_cmp,0,&n);
// printf("a[%d]=%ld tier %ld\n",i,a[i],n);
}
printf("Del %d TIMEVAL=%lld\n",NUM,now_usec()-now);
}

复制代码

作者: walleeee 时间: 2012-04-23 12:37
回复 56# yulihua49

你不觉得你很有意思么？

在一个平衡二叉树里，如何实现不等查找：
以[O(log2(N))]的代价，找到大于指定值的最小节点。
建议直接用递归做。

你这个说了等于说了什么？我觉得你什么也没说。

就算朴素的，最普通的平衡二叉查找树找“大于指定值的最小节点”，难道不是log(n)时间么？

况且，你不加平衡，不知道你是漏加还是什么原因，你“建议直接用递归做”，我不知道你是怎么做得log(n)，说来听听？

作者: walleeee 时间: 2012-04-23 12:38
回复 57# yulihua49

你觉得你这个代码是给人欣赏的么？

你自己愿意看么？

作者: yulihua49 时间: 2012-04-23 12:39
本帖最后由 yulihua49 于 2012-04-23 12:42 编辑

walleeee 发表于 2012-04-23 12:37
回复 56# yulihua49

是啊是啊。
怎么查，给出程序来，就是那个普通的。
讨论到这，包括另一个帖子，也没人拿出一个像样的程序，网上查的也没有。
就算是STL里有，就另外那个帖子的说法，效率也很可怜。

作者: walleeee 时间: 2012-04-23 12:39
回复 60# yulihua49

不好意思，我没空。

作者: walleeee 时间: 2012-04-23 12:42
回复 58# walleeee

不知道你是编辑过还是我之前看花了，现在又有平衡二字

就你说的，朴素查找也是Log(n)

作者: yulihua49 时间: 2012-04-23 12:44

walleeee 发表于 2012-04-23 12:38
回复 57# yulihua49

我贴这个的目的是说，算法已经实现，经过测试了。

作者: walleeee 时间: 2012-04-23 12:45
回复 63# yulihua49

我们之前不是说新开一帖么？你当时也答应了。你现在搞什么搞？

再说，你贴个测试搞什么用？你不贴详细的算法描述和实现，你觉得对别人有任何哪怕一点意义么？

作者: yulihua49 时间: 2012-04-23 12:45

walleeee 发表于 2012-04-23 12:42
回复 58# walleeee

现在是平衡的。
朴素的也能做，但不保证性能。

作者: yulihua49 时间: 2012-04-23 12:47
本帖最后由 yulihua49 于 2012-04-23 12:48 编辑

walleeee 发表于 2012-04-23 12:45
回复 63# yulihua49

再给你一点时间，拿出你的程序。交流一下。
新开一贴，别人不知前因后果，弄不明白你说的是什么。

作者: walleeee 时间: 2012-04-23 12:47
回复 65# yulihua49

什么叫“平衡的也能做”，难道平衡二叉查找树这样不很正常么？你说法真奇怪。

作者: walleeee 时间: 2012-04-23 12:48
回复 66# yulihua49

再给你一点时间，拿出你的程序。交流一下

什么叫再给我一点时间？我为什么要搞这个？你真有趣

我之前不就和你交流过了，你自己翻帖子。你也自己看看你自己之前的话。真是浪费功夫

作者: yulihua49 时间: 2012-04-23 12:49

walleeee 发表于 2012-04-23 12:47
什么叫“平衡的也能做”，难道平衡二叉查找树这样不很正常么？你说法真奇怪。

没有啊，我说朴素的也能做。

作者: yulihua49 时间: 2012-04-23 12:51
本帖最后由 yulihua49 于 2012-04-23 12:55 编辑

walleeee 发表于 2012-04-23 12:48
回复 66# yulihua49

什么叫再给我一点时间？我为什么要搞这个？

随便你，怕是如果你不做，别人做不出来。
讨论到这，包括另一个帖子，也没人拿出一个像样的程序，网上查的也没有。
就算是STL里有，就另外那个帖子的说法，效率也很可怜。

作者: walleeee 时间: 2012-04-23 12:55
回复 69# yulihua49

那你又说朴素不保证效率？你不是自己在放屁么？

作者: yulihua49 时间: 2012-04-23 12:56

walleeee 发表于 2012-04-23 12:45
回复 63# yulihua49
你不贴详细的算法描述和实现，你觉得对别人有任何哪怕一点意义么？

没人感兴趣，贴它干嘛？有人有兴趣就会贴。

作者: yulihua49 时间: 2012-04-23 12:58
本帖最后由 yulihua49 于 2012-04-23 13:00 编辑

walleeee 发表于 2012-04-23 12:55
回复 69# yulihua49

说啥呢？
我的算法在平衡树保证O（log（N)),非平衡也可以做，但不保证O（log（N))。

作者: walleeee 时间: 2012-04-23 13:00
回复 70# yulihua49

请不要重复编辑帖子好么？我看着累，你要重编也换个颜色

什么叫“怕是如果你不做，别人做不出来”，你觉得这是什么话？我早就跟你说了，我没你这个需求，我做他干嘛？这开始就是你自己的问题，我前面跟你说了下我的想法，你一会扯这个一会扯那个，然后你又说你有办法了，我说你去解决了回来开新贴拿实现，结果你搞个毛啊，你自己看看你的帖子再来说。还费ow那么多功夫，跟你搞毛啊，你一句“你那个不能用”，你知道什么是算法么？搞毛。

包括另一个帖子，也没人拿出一个像样的程序，网上查的也没有

算了，你继续码吧

效率也很可怜

你不要放屁。你说这句不如拿出测评。不然就不要放屁

作者: walleeee 时间: 2012-04-23 13:03
回复 73# yulihua49

我的算法在平衡树保证O（log（N)),非平衡也可以做，但不保证O（log（N))

你自己看看你是不是说了一句什么都没说的话。平衡树，我早就跟你说了，logn难道不该是本身就该的么？你扯后半句说“非平衡术可以做，但不保证...”你觉得什么意思？你这个最差情况不久是个n？你觉得有何意义，我真是不明白你在想些什么七界之外的事情。

作者: walleeee 时间: 2012-04-23 13:04
回复 72# yulihua49

你给我滚。

大家真是和你浪费功夫，算了，我闭嘴

作者: yulihua49 时间: 2012-04-23 13:09

walleeee 发表于 2012-04-23 13:00
回复 70# yulihua49

现在中国人****（三聚氰胺，瘦肉精什么的）吃多了，火气都很大。等消了火再说吧。

作者: walleeee 时间: 2012-04-23 13:12
回复 77# yulihua49

不是消火不消火的问题，你自己看，我开始对你态度如何？我对别人态度如何？我难道是一开始就这个态度？

你同时自己翻翻你自己前面说的话。你是自己在证明自己说屁话，难道不是么?

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)