二叉树不等查找的算法谁清楚？前些日子发表CSTL的大侠说说看

yulihua49

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

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

walleeee

回复 51# yulihua49


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

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

yulihua49

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

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

_Rayx

回复 53# yulihua49


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

selfrun

map有lower bound

yulihua49

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

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

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

1. main()
   
2. {
   
3. long a[NUM];
   
4. int i,n;
   
5. T_Tree *val,*root=NULL;
   
6. INT64 now,min,max;
   
7. 
   
8.         for(i=0;i<NUM;i++) {
   
9.                 a[i]=now_usec()+i;
   
10.                 root=BB_Tree_Add(root,&a[i],sizeof(long),t_cmp,0);
    
11.         }
    
12.         val=BB_Tree_MIN(root);
    
13.         min=val?*(INT64 *)val->Content:-1;
    
14.         val=BB_Tree_MAX(root);
    
15.         max=val?*(INT64 *)val->Content:-1;
    
16.         n=BB_Tree_Count(root,NULL,NULL);
    
17. printf("MIN=%lld,MAX=%lld,n=%d\n",min,max,n);
    
18. printf("at %lld-%lld,time=%ld\ninput VAL:\n",a[0],a[NUM-1],a[NUM-1] - a[0]);
    
19. //debug=1;
    
20.         while(1==scanf("%lld",&now)) {
    
21. //              val=BB_Tree_Find(root,&now,sizeof(INT64),t_cmp);
    
22. //              val=BB_Tree_GT(root,&now,sizeof(INT64),t_cmp);
    
23. //              val=BB_Tree_GTEQ(root,&now,sizeof(INT64),t_cmp);
    
24. //              val=BB_Tree_LT(root,&now,sizeof(INT64),t_cmp);
    
25. //              val=BB_Tree_LTEQ(root,&now,sizeof(INT64),t_cmp);
    
26.         min=now_usec();
    
27.         for(i=0;i<10000;i++)
    
28.                 val=BB_Tree_GT(root,&now,sizeof(INT64),t_cmp);
    
29.         min=now_usec()-min;
    
30.                 if(!val) printf("NULL,time=%lld\n",min);
    
31.                 else printf("val=%lld,time=%lld\n",*(INT64 *)val->Content,min);
    
32.         }
    
33. debug=0;
    
34. now=now_usec();
    
35.         for(i=0;i<NUM;i++) {
    
36.                 n=0;
    
37.                 root=BB_Tree_Del(root,&a[i],sizeof(long),t_cmp,0,&n);
    
38. //              printf("a[%d]=%ld tier %ld\n",i,a[i],n);
    
39.         }
    
40.         printf("Del %d TIMEVAL=%lld\n",NUM,now_usec()-now);
    
41. }
    

复制代码

walleeee

回复 56# yulihua49


你不觉得你很有意思么？

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

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

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

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

walleeee

回复 57# yulihua49


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

你自己愿意看么？

yulihua49

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

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