免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 17902 | 回复: 130

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

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-04-21 18:04 |显示全部楼层
不知道二分查找的,可以出去补下课再回来……
而知道二分查找的,也别急着走…… 这东西太出名了…… 并且概念也十分易懂……
越是如此,谈论的人就越多,谈论的质量就越参差不齐……
就像singleton,基本一听就懂……
然而如果自认为这样就懂了, 里面的很多道道就没机会懂了……
当然, 提到singleton也只是因为两者在懂得人多精得人少这点上很像, 两者自身的价值是不具可比性的……


------ 废话完毕 ------ ------ 开始正题 ------


首先,关于两路与三路(2-way/3-way)术语……
如果有人知道出处,那出处就是它;
如果没人知道出处,那就是我杜撰的……


举例来说,C 的 bsearch 就是三路,而 C++ 的 std:: lower_bound 系列就是两路。

实现上的本质区别是如何对待相等的情况:

* 相等用作退出条件

这其实是将整个搜索区间分为了左半、中点、右半共三部分
相等则返回该记录并退出,否则根据大小关系在剩下两半中继续。

* 相等不作退出条件

这其实只将整个搜索区间分为了两半,根据比较关系,包括在相等时也选择其中一个区间继续,仅仅在区间满足某些边界条件时才退出。
这才是折半查找啊亲……


当区间中可能含有相同的键时,两者功能上的最大差异就能体现出来了:
三路只能返回相同键中的某一个,但不能确定是哪一个。
两路可以找到相同键中的边界

例如:

  1. ... a, b0, b1, ... , bn, c ...
复制代码
并假设 bi (0 <= i && i<= n) 相等。
三路只会返回 bi 中的某一个,但不能确定是哪一个。
两路可以找到 b0 与 bn 。


1. STL begin/end/lower_bound/upper_bound 规范

因为:
* begin/end 长度不匹配
* lower_bound/upper_bound 太长
* 讨论的是有序序列

所以下面叙述时改用 min/max 与 lower/upper 。

STL 用 [min..max) 表示有序序列, max 是 sentinel , min==max 表示空序列。
lower(t,k) 返回序列中首个不小于 k 的元素。
upper(t,k) 返回序列中首个大于 k 的元素。

常见用法如:

p = lower(t,k)
p == max? 没找到: 找到且 p 是首个不小于 k 的元素 —— p==min || prev(p) < k;

q = upper(t,k)
[p..q) 就是[min..max)中所有与 k 等价的元素的构成的有相同顺序的子序列。


2. max/sentinel/infinite/root 节点

为简化边界条件,不妨设树总有一个 root 节点:
* 它的键值是 infinite
* 它是整个树中是最大元素
* 并且作为树所表示的序列的 sentinel

实现时其实也有一些技巧让这个节点只占用一个指针大小。

那么, 所有有效节点其实都在 root 的左子树:

  1.   i
  2. L?    L? ++ [i)
复制代码
L? 是可能为空的左子树(大写表示子树、小写表示节点、附带问号表示可空)。
整个树表示的序列是由子树 L? 中序遍历产生的序列 inorder(L?) (不引起混淆的情况下简写为 I(L?) 或 L?)与空序列 [i) 的连接(++)。


3. 搜索区间表示法

一种方法是用子树 S? 的根 s 表示搜索区间 I(S?)。
这样可以快速获取区间中的一点(树根s), 并且根据键k与s的关系推断k与S的所有前趋(左子树)与后继(右子树)之间的关系, 以满足二分搜索的条件。

此处使用另一种表示法:使用子树 Middle 与一个节点 bound 表示搜索区间 Middle ++ [bound)。

显然 Middle 与 bound 不能随意选择, Middle ++ [bound) 必须是 [min..max) 的子序列。
即中序遍历中 bound 是 Middle 的后继, bound 是 middle 的首个左父节点。

例如:

  1. b        b              b                  b
  2. M      p          g                      g
  3.         M           p                 p    A
  4.                       M                M
复制代码
上图中前3个都满足条件, 但最后一个不行。
因为中序序列是 ... ++ [p] ++ M ++ [g] ++ A ++ [b) , M 与 [b) 之间还夹有 [g] ++ A 。

相比前面一种表示法, 只是将子树称作 Middle 并增加了一个 bound 作为 sentinel 。


4. lower

定义 lower_r(M?,b,k), 它应当返回 M? ++ [b) 中首个不小于 k 的元素:
a) 如果 M? 中存在不小于 k 的元素, 该函数返回它们中的首个
b) 否则 M? 中所有元素都小于 k , 该函数返回 b

整个树的序列可用 t.left ++ [t.max) 表示。
那么 lower(t,k) = lower_r(t.left , t.max , k) 。

当 M? 为空时, 区间是 [b) , 首个大于 k 的元素是 b, 因此:
lower_r(nil,b,k) = b

当 M? 非空时:

  1.      b
  2. ...
  3.   m
  4. L? R?    L? ++ [m] ++ R? ++ [b)

  5. lower_r(b,m,k)
  6. m >  k        k         = lower_r(m.left , m , k)
  7. m == k          k       = lower_r(m.left , m , k)
  8. m <  k            k     = lower_r(m.right, b , k)
复制代码
i) m > k 时

m 是 [m] ++ R? ++ [b) 中首个不小于 k 的元素, 所以 R? ++ [b) 不符合条件。
首个比 k 大的元素只可能在 L? ++ [m] 闭区间中。

使用 lower_r(m.left , m , k) 继续查找 L ++ [m) 开区间。
注意, lower_r(M?,b,k) 只是不会触碰 b , 但它存在返回 b 的可能性, 可用于查找闭区间 L? ++ [m]。
根据定义, 当 m.left 中所有元素都小于 k 时, 返回端点 m 。

ii) m < k 时

L? ++ [m] 中所有元素都小于 k , 首个比 k 大的元素只可能出现在 R? ++ [b) 中。
使用 lower_r(m.right, b, k) 继续查找。

iii) m == k 时

同 i)。

注意此时没有返回 m 并退出查找,而是继续缩小区间范围。
概念上是将整个区间 L? ++ [m] ++ R? ++ [b) 划分为两半
a) L? ++ [m]
b) R? ++ [b)

每次选择其中的一半继续搜索, 直到达到递归边界。


5. upper

同理,定义 upper_r(M?,b,k), 它返回 M? ++ [b) 中首个大于 k 的元素:
a) M? 中存在大于 k 的元素, 该函数返回它们中的首个
b) M? 中所有元素都小于 k , 该函数返回 b

那么 upper(t,k) = upper_r(t.left , t.max , k)
并且 upper_r(nil,b,k) = b

当 M? 非空时:

  1.      b
  2. ...
  3.   m
  4. L? R?    L? ++ [m] ++ R? ++ [b)

  5. upper_r(b,m,k)
  6. m >  k        k         == upper_r(m.left , m , k)
  7. m == k          k       == upper_r(m.right, b , k)
  8. m <  k            k     == upper_r(m.right, b , k)
复制代码
upper_r 也是折半搜索两个子区间之一:
a) L? ++ [m]
b) R? ++ [b)

与 lower_r 不同的是当 m == k 时, 首个比 k 大的元素不会出现在 L? ++ [m] 中,所以递归搜索另一个子区间 R? ++ [b) 。


6. 递归边界可达到性

还需要证明对有限区间 M? ++ [b) , 一定能在有限步内到达边界条件 [b) 得出结果 b 。

根据 M? 是否为空, 其左右子树是否为空, 可分为如下形态:


  1.      0        1        2        3        4
  2.      b        b        b        b        b
  3. ...      ...      ...      ...      ...
  4. nil       m        m        m        m
  5.         nil nil  nil R     L nil     L R

  6. form    sequence     expect  result                                     next
  7. 0 )     [b)             b == search (nil,b,k) == b                      exit

  8. 1 )          [m , b)
  9. m >  k      k           m == search (m.left , m , k) == search (nil,m)  0
  10. m <  k          k       b == search (m.right, b , k) == search (nil,b)  0
  11. m == k        k         m == lower_r(m.left , m , k) == lower_r(nil,m)  0
  12.                         b == upper_r(m.right, b , k) == upper_r(nil,b)  0

  13. 2 )          [m] ++ R ++ [b)
  14. m >  k      k           m == search (m.left , m , k) == search (nil,m)  0
  15. m <  k          k            search (m.right, b , k)                    [1..4]
  16. m == k        k         m == lower_r(m.left , m , k) == search (nil,m)  0
  17.                              upper_r(m.right, b , k)                    [1..4]

  18. 3 )     L ++ [m] ++ [b)
  19. m >  k      k                search (m.left , m , k)                    [1..4]
  20. m <  k          k       b == search (m.right, b , k) == search(nil,b)   0
  21. m == k        k              lower_r(m.left , m , k)                    [1..4]
  22.                         b == upper_r(m.right, b , k) == search(nil,b)   0

  23. 4 )     L ++ [m] ++ R ++ [b)
  24. m >  k      k                search (m.left , m , k)                    [1..4]
  25. m <  k          k            search (m.right, b , k)                    [1..4]
  26. m == k        k              lower_r(m.left , m , k)                    [1..4]
  27.                              upper_r(m.right, b , k)                    [1..4]
复制代码
一些说明:
* expect 列是区间小到足够推断出的结果
* result 列是函数定义计算的结果
* lower_r 与 upper_r 的区别在于相等的情况, 它们的共部分用 search 代替

可见区间总是在这5种形态之内转换。

最后, 无论是 lower_r 还是 upper_r , 每次折半并排除掉的都不是空区间
a) L? ++ [m] 左半至少包含 m
b) R? ++ [b) 右半至少包含 b

综上, 总是能在有限步内达到递归边界。


7. 代码

临时写的……  命名神马的……

  1. #include <stddef.h>
  2. #include <stdlib.h>
  3. #include <stdio.h>


  4. #ifdef __cplusplus
  5. extern "C" {
  6. #endif

  7. typedef struct bst_ {struct bst_*p[3];} bst_t;  /* lower  upper  parent */

  8. static bst_t* bst_max_(bst_t* x)                /*      x               */
  9. {                                               /*     ? r  = max_(r)   */
  10.       while (x->p[1]) x = x->p[1];              /*                      */
  11.       return x;                                 /*      x   = x         */
  12. }                                               /*     ? nil            */

  13. static bst_t* bst_min_(bst_t* x)                /*      x               */
  14. {                                               /*     l ?  = min_(l)   */
  15.       while (x->p[0]) x = x->p[0];              /*                      */
  16.       return x;                                 /*      x   = x         */
  17. }                                               /*   nil ?              */

  18. bst_t* bst_next(bst_t* x)                       /*      x               */
  19. {                                               /*     ? r  = min_(r)   */
  20.       if (x->p[1]) return bst_min_(x->p[1]);    /*                      */
  21.       while (x->p[2]->p[1] == x) x = x->p[2];   /*      a   = a         */
  22.       return x->p[2];                           /*   ls                 */
  23. }                                               /*     x                */
  24.                                                 /*    ? nil             */

  25. bst_t* bst_prev(bst_t* x)                       /*      a   = a         */
  26. {                                               /*        rs            */
  27.       if (x->p[0]) return bst_max_(x->p[0]);    /*       x              */
  28.       while (x->p[2]->p[0] == x) x = x->p[2];   /*    nil ?             */
  29.       return x->p[2];                           /*                      */
  30. }                                               /*      x               */
  31.                                                 /*     l ?  = max_(l)   */

  32. bst_t* bst_max(bst_t** self) { return (bst_t*)self; }
  33. bst_t* bst_min(bst_t** self) { return bst_min_( bst_max(self) ); }

  34. void bst_insert(bst_t** t, bst_t* x, ptrdiff_t cmp(void* e, void* k), void* k)
  35. {
  36.       bst_t* n = bst_max(t);
  37.       int d = 0;
  38.       while (n->p[d]) {
  39.             n = n->p[d];
  40.             d = cmp(n,k) <= 0;
  41. /*         L? ++ [n] ++ R?
  42.    n >  x       x             = insert(n.left , x)
  43.    n == x         x           = insert(n.right, x)  ; stable
  44.    n <  x           x         = insert(n.right, x)  ; ascending */
  45.       }
  46.       n->p[d] = x;
  47.       x->p[2] = n;
  48.       x->p[0] = x->p[1] = 0;
  49. }

  50. /*
  51. lower(t,k) = n ; n >= k and (n==min or prev(n) <  k)
  52. upper(t,k) = n ; n >  k and (n==min or prev(n) <= k)
  53. search(m,b,k)  ; search_tree(t,k) = search(t.left , t.max , k)
  54.      b
  55. ...
  56.   m
  57. L? L?     L? ++ [m] ++ L? ++ [b)
  58. m == nil                      = b
  59. m >  k         k              = search_r(m.left , m , k)
  60. m == k           k            = lower_r (m.left , m , k)
  61.                               = upper_r (m.right, b , k)
  62. m <  k             k          = search_r(m.right, b , k) */
  63. bst_t* bst_lower(bst_t** t, ptrdiff_t cmp(void* e, void* k), void* k) {
  64.       bst_t* bound  = bst_max(t);
  65.       bst_t* middle = bound->p[0];
  66.       while (middle)
  67.             cmp(middle,k)  < 0
  68.                   ? middle = middle->p[1]
  69.                   : (bound = middle, middle = middle->p[0]);
  70.       return bound;
  71. }
  72. bst_t* bst_upper(bst_t** t, ptrdiff_t cmp(void* e, void* k), void* k) {
  73.       bst_t* bound  = bst_max(t);
  74.       bst_t* middle = bound->p[0];
  75.       while (middle)
  76.             cmp(middle,k) <= 0
  77.                   ? middle = middle->p[1]
  78.                   : (bound = middle, middle = middle->p[0]);
  79.       return bound;
  80. }

  81. #define container_of(link, type, field)   \
  82.       ( (type*)( (char*)link - offsetof(type, field) ) )

  83. #ifdef __cplusplus
  84. }
  85. #endif


  86. typedef struct {
  87.       int k;
  88.       int v;
  89.       bst_t n;
  90. } node_t;

  91. static node_t* node(bst_t* x) { return container_of(x, node_t, n); }

  92. ptrdiff_t cmp(void* e, void* k) {
  93.       node_t* elem = container_of(e,node_t,n);
  94.       int key = *(int*)k;
  95.       return elem->k - key;
  96. }


  97. #ifdef TEST_TRAVERSAL
  98. int main(int argc, char* argv[])
  99. {
  100.       int i, total = abs( atoi(argc>1? argv[1]: "12") );
  101.       node_t *nodes = (node_t*)calloc(total, sizeof *nodes);
  102.       node_t *it, *beg, *end;
  103.       bst_t *tree = 0;

  104.       for ( i=0; i<total && scanf("%d%d", &nodes[i].k, &nodes[i].v)==2; ++i )
  105.             bst_insert(&tree, &nodes[i].n, cmp, &nodes[i].k);

  106.       beg = node( bst_min(&tree) );
  107.       end = node( bst_max(&tree) );
  108.       for ( it = beg; it != end; it = node( bst_next(&it->n) ) )
  109.             printf("%d %d\n", it->k, it->v);

  110.       printf("\n");
  111.       for ( it = end; it != beg; ) {
  112.             it = node( bst_prev(&it->n) );
  113.             printf("%d %d\n", it->k, it->v);
  114.       }

  115.       free(nodes);
  116.       return 0;
  117. }

  118. #else
  119. int main(int argc, char* argv[])
  120. {
  121.       int i, total = 12, lower_, *lower = 0, upper_, *upper = 0;
  122.       bst_t *tree = 0;
  123.       node_t *nodes, *interval[4];

  124.       for ( i=0; i<argc; ++i )
  125.             switch(argv[i][0])
  126.             {
  127.             case 'l': lower = (lower_ = atoi(argv[i]+1), &lower_);
  128.                   break;
  129.             case 'u': upper = (upper_ = atoi(argv[i]+1), &upper_);
  130.                   break;
  131.             case 'n': total = abs( atoi(argv[i]+1) );
  132.                   break;
  133.             }

  134.       nodes = (node_t*)calloc(total, sizeof *nodes);
  135.       for ( i=0; i<total && scanf("%d", &nodes[i].k)==1; ++i )
  136.             bst_insert(&tree, &nodes[i].n, cmp, &nodes[i].k);

  137.       interval[0] = node( bst_min(&tree) );
  138.       interval[1] = lower? node( bst_lower(&tree, cmp, lower) ): interval[0];
  139.       interval[3] = node( bst_max(&tree) );
  140.       interval[2] = upper? node( bst_upper(&tree, cmp, upper) ): interval[3];

  141.       i = 0;
  142.       do {
  143.             node_t *beg = interval[i], *end = interval[i+1];
  144.             for (; beg != end; beg = node( bst_next(&beg->n) ) )
  145.                   printf("%d ", beg->k);
  146.       } while ( printf("%s", ++i!=3? "| ": "\n")!=1 );

  147.       free(nodes);
  148.       return 0;
  149. }

  150. #endif
复制代码

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-04-21 18:06 |显示全部楼层
占楼吐个槽……  事情的起因在此:

yulihua49 发表于 2012-04-19 14:50
在网上搜了一下“二叉树不等查找”,居然只有我这一贴。
难道别人没有这个需求吗?未见到相关报道,我要是做出来了,可以申请专利吗?


两天时间, 一天看STL, 一天看CSTL, 怎么都够了…… 就那么几行代码……
专利……  笑尿了

论坛徽章:
0
发表于 2012-04-21 18:40 |显示全部楼层
好像是前面那个要上下界的帖子。我想起一个数据结构,线段树

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-04-21 19:55 |显示全部楼层
回复 3# walleeee

就是那个……

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2012-04-22 10:08 |显示全部楼层
本帖最后由 yulihua49 于 2012-04-22 10:58 编辑
OwnWaterloo 发表于 2012-04-21 18:06
占楼吐个槽……  事情的起因在此:

扔一板砖,砸出个大侠。
非常感谢,一定认真拜读。
问题已解决,下周发结果。

需求稍有不同,如果指定条件不满足,返回NULL,而非最接近的那一个。不过这不是原则问题。

算法已经有了,很简单,一句话即可,还是3行解决。

讨论一下:
为简化边界条件,不妨设树总有一个 root 节点:
* 它的键值是 infinite
* 它是整个树中是最大元素
* 并且作为树所表示的序列的 sentinel

如果以递归的思路考虑,这是否意味着树退化为一个左链表,root是这个链表的最大值指针?
是一个左树,其下一个结点可以是平衡树?
我的使用条件是平衡树。要求是速度。


看的晕死了,i+1?i+l? 1与小写的L。。。。。。

我理解的对否?
一棵不保证平衡的树,在里边进行二分查找。确定结果集的区间。
其间每一次计算都是一个迭代的过程。
理论上行得通。所以我再搞出什么东西,理论上也无新意。
这也就是为什么大多数研究者止于理论。

你测一下时间吧,下周我们比一比。
65535个节点的树,查找一个值需要多少时间。
使用gettimeofday就可以测到微秒级。
1微秒是允许的上限。


论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-04-22 10:54 |显示全部楼层
回复 5# yulihua49

只有root是特殊的,只有左子节点,没有右子节点,也没有父节点。
于是root其实只是一个指针, 被当作3个指针用, 其余两个在正常操作下不会被碰到( 比如可以prev(max(t))  但不能 next(max(t)) ), 否则就完蛋了。

其他节点都是正常的,有3个域。
父节点只是为了: 1) 示例代码得输出点东西 2) 用回调写起来很麻烦 3) 于是就加了个父节点并用常数空间遍历
与搜索没什么关系, 搜索没读, 更没写父节点。

bst而不是某种平衡树也只是为了insert写起来方便。
搜索本身与平衡关系不大。


至于 1(one) 与 l(el) ……
因为我编辑器专门用的是能区分两者的字体(yahei mono), 浏览器也跟着用, 所以一时间忘了这个问题。。。

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-04-22 10:58 |显示全部楼层
回复 5# yulihua49

测时间……   这只是用来说明lower_bound与upper_bound的裸体bst示例代码好么……
从以前写的rb里面扣出来的, 附带想了想怎么将 lower/upper 解释清楚。

时间的话, 与map(sgi stl)相当, 比rbtree.h(linux) 稍慢。 并且比较都没有用回调函数。

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2012-04-22 11:01 |显示全部楼层
本帖最后由 yulihua49 于 2012-04-22 11:07 编辑
OwnWaterloo 发表于 2012-04-22 10:58
回复 5# yulihua49

测时间……   这只是用来说明lower_bound与upper_bound的裸体bst示例代码好么……

啊,没有关系的。随便你想不想研究,咱们只是做个探讨。如果有兴趣就练练。
我是要一个产品,而不限于理论,你会我有帮助的,

那个晕,我慢慢晕吧,好歹还能分得出来哪里是1哪里是l。
有点事走了,下周见。

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-04-22 11:13 |显示全部楼层
回复 8# yulihua49

普遍意义上的研究大部分都已经被前人吃干抹净了。至少rb与avl是如此。
还比如基于比较的排序,比较次数下限是n*log(n),不可能会是log(n)。

大多数人搞其实是在针对自己的special case做performance tuning。

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2012-04-23 11:54 |显示全部楼层
本帖最后由 yulihua49 于 2012-04-23 12:31 编辑
OwnWaterloo 发表于 2012-04-22 11:13
回复 8# yulihua49

普遍意义上的研究大部分都已经被前人吃干抹净了。至少rb与avl是如此。

对于我的special case, 在那个帖子里,陆陆续续的讲了。
是一个内存数据库的核心组件。
含义是:1.数据量巨大。2功能众多,这只是其中之一。3.性能要求高,否则用关系数据库即可,别费这个劲。
所以,没空间也没时间进行数据重组。不可能为这一个功能重组数据。数据库可以达到80-150微秒,低于这个速度没意义。
你这个程序作为知识学习一下是可以的。不能用。
一个平衡的二叉树,还有必要使用二分法吗?

鉴于问题已经解决,这个问题转化成一个考题:
在一个平衡二叉树里,如何实现不等查找:
以[O(log2(N))]的代价,找到大于指定值的最小节点。
提示一下,41楼的方法可以,可惜没写成程序。
http://bbs.chinaunix.net/thread-3725768-5-2.html
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,8.5折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时8.5折扣期:2019年9月30日前


----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP