- 论坛徽章:
- 2
|
不知道二分查找的，可以出去补下课再回来……
而知道二分查找的，也别急着走…… 这东西太出名了…… 并且概念也十分易懂……
越是如此，谈论的人就越多，谈论的质量就越参差不齐……
就像singleton，基本一听就懂……
然而如果自认为这样就懂了， 里面的很多道道就没机会懂了……
当然， 提到singleton也只是因为两者在懂得人多精得人少这点上很像， 两者自身的价值是不具可比性的……
------ 废话完毕 ------ ------ 开始正题 ------
首先，关于两路与三路(2-way/3-way)术语……
如果有人知道出处，那出处就是它；
如果没人知道出处，那就是我杜撰的……
举例来说，C 的 bsearch 就是三路，而 C++ 的 std:: lower_bound 系列就是两路。
实现上的本质区别是如何对待相等的情况：
* 相等用作退出条件
这其实是将整个搜索区间分为了左半、中点、右半共三部分。
相等则返回该记录并退出，否则根据大小关系在剩下两半中继续。
* 相等不作退出条件
这其实只将整个搜索区间分为了两半，根据比较关系，包括在相等时也选择其中一个区间继续，仅仅在区间满足某些边界条件时才退出。
这才是折半查找啊亲……
当区间中可能含有相同的键时，两者功能上的最大差异就能体现出来了：
三路只能返回相同键中的某一个，但不能确定是哪一个。
两路可以找到相同键中的边界。
例如：
- ... a, b0, b1, ... , bn, c ...
三路只会返回 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 的左子树：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 的首个左父节点。
例如：
- b b b b
- M p g g
- M p p A
- M M
因为中序序列是 ... ++ [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? 非空时：
- b
- ...
- m
- L? R? L? ++ [m] ++ R? ++ [b)
- lower_r(b,m,k)
- m > k k = lower_r(m.left , m , k)
- m == k k = lower_r(m.left , m , k)
- m < k k = lower_r(m.right, b , 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? 非空时：
- b
- ...
- m
- L? R? L? ++ [m] ++ R? ++ [b)
- upper_r(b,m,k)
- m > k k == upper_r(m.left , m , k)
- m == k k == upper_r(m.right, b , k)
- m < k k == upper_r(m.right, b , k)
a) L? ++ [m]
b) R? ++ [b)
与 lower_r 不同的是当 m == k 时， 首个比 k 大的元素不会出现在 L? ++ [m] 中，所以递归搜索另一个子区间 R? ++ [b) 。
6. 递归边界可达到性
还需要证明对有限区间 M? ++ [b) ， 一定能在有限步内到达边界条件 [b) 得出结果 b 。
根据 M? 是否为空， 其左右子树是否为空， 可分为如下形态：
- 0 1 2 3 4
- b b b b b
- ... ... ... ... ...
- nil m m m m
- nil nil nil R L nil L R
- form sequence expect result next
- 0 ) [b) b == search (nil,b,k) == b exit
- 1 ) [m , b)
- m > k k m == search (m.left , m , k) == search (nil,m) 0
- m < k k b == search (m.right, b , k) == search (nil,b) 0
- m == k k m == lower_r(m.left , m , k) == lower_r(nil,m) 0
- b == upper_r(m.right, b , k) == upper_r(nil,b) 0
- 2 ) [m] ++ R ++ [b)
- m > k k m == search (m.left , m , k) == search (nil,m) 0
- m < k k search (m.right, b , k) [1..4]
- m == k k m == lower_r(m.left , m , k) == search (nil,m) 0
- upper_r(m.right, b , k) [1..4]
- 3 ) L ++ [m] ++ [b)
- m > k k search (m.left , m , k) [1..4]
- m < k k b == search (m.right, b , k) == search(nil,b) 0
- m == k k lower_r(m.left , m , k) [1..4]
- b == upper_r(m.right, b , k) == search(nil,b) 0
- 4 ) L ++ [m] ++ R ++ [b)
- m > k k search (m.left , m , k) [1..4]
- m < k k search (m.right, b , k) [1..4]
- m == k k lower_r(m.left , m , k) [1..4]
- 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. 代码
临时写的…… 命名神马的……
- #include <stddef.h>
- #include <stdlib.h>
- #include <stdio.h>
- #ifdef __cplusplus
- extern "C" {
- #endif
- typedef struct bst_ {struct bst_*p[3];} bst_t; /* lower upper parent */
- static bst_t* bst_max_(bst_t* x) /* x */
- { /* ? r = max_(r) */
- while (x->p[1]) x = x->p[1]; /* */
- return x; /* x = x */
- } /* ? nil */
- static bst_t* bst_min_(bst_t* x) /* x */
- { /* l ? = min_(l) */
- while (x->p[0]) x = x->p[0]; /* */
- return x; /* x = x */
- } /* nil ? */
- bst_t* bst_next(bst_t* x) /* x */
- { /* ? r = min_(r) */
- if (x->p[1]) return bst_min_(x->p[1]); /* */
- while (x->p[2]->p[1] == x) x = x->p[2]; /* a = a */
- return x->p[2]; /* ls */
- } /* x */
- /* ? nil */
- bst_t* bst_prev(bst_t* x) /* a = a */
- { /* rs */
- if (x->p[0]) return bst_max_(x->p[0]); /* x */
- while (x->p[2]->p[0] == x) x = x->p[2]; /* nil ? */
- return x->p[2]; /* */
- } /* x */
- /* l ? = max_(l) */
- bst_t* bst_max(bst_t** self) { return (bst_t*)self; }
- bst_t* bst_min(bst_t** self) { return bst_min_( bst_max(self) ); }
- void bst_insert(bst_t** t, bst_t* x, ptrdiff_t cmp(void* e, void* k), void* k)
- {
- bst_t* n = bst_max(t);
- int d = 0;
- while (n->p[d]) {
- n = n->p[d];
- d = cmp(n,k) <= 0;
- /* L? ++ [n] ++ R?
- n > x x = insert(n.left , x)
- n == x x = insert(n.right, x) ; stable
- n < x x = insert(n.right, x) ; ascending */
- }
- n->p[d] = x;
- x->p[2] = n;
- x->p[0] = x->p[1] = 0;
- }
- /*
- lower(t,k) = n ; n >= k and (n==min or prev(n) < k)
- upper(t,k) = n ; n > k and (n==min or prev(n) <= k)
- search(m,b,k) ; search_tree(t,k) = search(t.left , t.max , k)
- b
- ...
- m
- L? L? L? ++ [m] ++ L? ++ [b)
- m == nil = b
- m > k k = search_r(m.left , m , k)
- m == k k = lower_r (m.left , m , k)
- = upper_r (m.right, b , k)
- m < k k = search_r(m.right, b , k) */
- bst_t* bst_lower(bst_t** t, ptrdiff_t cmp(void* e, void* k), void* k) {
- bst_t* bound = bst_max(t);
- bst_t* middle = bound->p[0];
- while (middle)
- cmp(middle,k) < 0
- ? middle = middle->p[1]
- : (bound = middle, middle = middle->p[0]);
- return bound;
- }
- bst_t* bst_upper(bst_t** t, ptrdiff_t cmp(void* e, void* k), void* k) {
- bst_t* bound = bst_max(t);
- bst_t* middle = bound->p[0];
- while (middle)
- cmp(middle,k) <= 0
- ? middle = middle->p[1]
- : (bound = middle, middle = middle->p[0]);
- return bound;
- }
- #define container_of(link, type, field) \
- ( (type*)( (char*)link - offsetof(type, field) ) )
- #ifdef __cplusplus
- }
- #endif
- typedef struct {
- int k;
- int v;
- bst_t n;
- } node_t;
- static node_t* node(bst_t* x) { return container_of(x, node_t, n); }
- ptrdiff_t cmp(void* e, void* k) {
- node_t* elem = container_of(e,node_t,n);
- int key = *(int*)k;
- return elem->k - key;
- }
- #ifdef TEST_TRAVERSAL
- int main(int argc, char* argv[])
- {
- int i, total = abs( atoi(argc>1? argv[1]: "12") );
- node_t *nodes = (node_t*)calloc(total, sizeof *nodes);
- node_t *it, *beg, *end;
- bst_t *tree = 0;
- for ( i=0; i<total && scanf("%d%d", &nodes[i].k, &nodes[i].v)==2; ++i )
- bst_insert(&tree, &nodes[i].n, cmp, &nodes[i].k);
- beg = node( bst_min(&tree) );
- end = node( bst_max(&tree) );
- for ( it = beg; it != end; it = node( bst_next(&it->n) ) )
- printf("%d %d\n", it->k, it->v);
- printf("\n");
- for ( it = end; it != beg; ) {
- it = node( bst_prev(&it->n) );
- printf("%d %d\n", it->k, it->v);
- }
- free(nodes);
- return 0;
- }
- #else
- int main(int argc, char* argv[])
- {
- int i, total = 12, lower_, *lower = 0, upper_, *upper = 0;
- bst_t *tree = 0;
- node_t *nodes, *interval[4];
- for ( i=0; i<argc; ++i )
- switch(argv[i][0])
- {
- case 'l': lower = (lower_ = atoi(argv[i]+1), &lower_);
- break;
- case 'u': upper = (upper_ = atoi(argv[i]+1), &upper_);
- break;
- case 'n': total = abs( atoi(argv[i]+1) );
- break;
- }
- nodes = (node_t*)calloc(total, sizeof *nodes);
- for ( i=0; i<total && scanf("%d", &nodes[i].k)==1; ++i )
- bst_insert(&tree, &nodes[i].n, cmp, &nodes[i].k);
- interval[0] = node( bst_min(&tree) );
- interval[1] = lower? node( bst_lower(&tree, cmp, lower) ): interval[0];
- interval[3] = node( bst_max(&tree) );
- interval[2] = upper? node( bst_upper(&tree, cmp, upper) ): interval[3];
- i = 0;
- do {
- node_t *beg = interval[i], *end = interval[i+1];
- for (; beg != end; beg = node( bst_next(&beg->n) ) )
- printf("%d ", beg->k);
- } while ( printf("%s", ++i!=3? "| ": "\n")!=1 );
- free(nodes);
- return 0;
- }
- #endif
|
|
免费注册
发表于 2012-04-21 18:04
发表于 2012-04-21 18:40
