[关闭]
@quinn 2015-04-14T02:20:07.000000Z 字数 8899 阅读 2427

搜索(2):二叉搜索树 BST

搜索算法


1. 二分搜索

将分治法应用于基于数组符号表的顺序搜索中,可以大大降低大型数据集合的搜索时间。
把数据集合分成两部分,确定搜索关键字属于哪一部分,然后集中处理那一部分。划分依据的一种合理方式是:保持数据项有序。此方法称为二分搜索

  1. //基于数组的符号表的二分搜索
  2. Item Search(int l, int r, Key v);
  3. Item BinarySearch(Key v)
  4. {
  5. Search(0, N-1, v);
  6. }
  7. Item Search(int l, int r, Key v)
  8. {
  9. if(r < l)
  10. return NULLItem;
  11. int m = (l+r) / 2;
  12. //int m = l + (r-l) * (v-Key(l)) / (Key(a[r])-Key(a[l]));//改进--插值搜索
  13. if(eq(Key(st[m]), v)
  14. return st[m];
  15. if(r == l)
  16. return NULLItem;
  17. if(less(v, Key(st[m]))
  18. return Search(l, m-1, v);
  19. else
  20. return Search(m, r, v);
  21. }

二分搜索的一种改进方法:更精确的猜测搜索关键字将落入当前区间的什么位置,而不是盲目选择中间元素。这种方法称为插值搜索
将上述

  1. int m = (l+r) / 2;

改为

  1. int m = l + (r-l) * (v-Key(l)) / (Key(a[r])-Key(a[l]));//改进--插值搜索

2. 二叉搜索树

为解决插入开销高的问题,二叉搜索树允许我们使用一种搜索、插入、选择和排序的快速且性能中等的算法。
定义:二叉搜索树(binary search tree, BST)是一棵二叉树,它的每个内部节点都关联一个关键字。有以下性质:每个左节点都小于它的根节点,每个右节点都大于它的根节点。
性能特征:算法在二叉搜索树上的运行时间与树的形状无关。在树是完美平衡(完全二叉树)的情况下,根节节点与外部节点(叶节点)之间大约有lgN个节点;最坏情况下有N个节点。

2.1 二叉搜索树的初始化、插入、搜索

  1. typedef char Item;
  2. typedef int Key;
  3. typedef struct BSTree* Link;
  4. struct BSTree
  5. {
  6. Item item;
  7. Link left;
  8. Link right;
  9. int N; //引入计数,是为了实现select操作
  10. };
  11. static Link head, z;
  12. //=====新建一个节点=====
  13. Link NewItem(Item item, Link left, Link right, int N)
  14. {
  15. Link x = (Link)malloc(sizeof(*x));
  16. x->item = item;
  17. x->left = left;
  18. x->right = right;
  19. x->N = N;
  20. return x;
  21. }
  22. // ============初始化=================
  23. Link BSTreeInit()
  24. {
  25. //head是指向树的根节点的哑节点,尾节点 z 表示空树
  26. head = (z = NewItem(NULLItem, NULL, NULL, 0));
  27. if(head == NULL)
  28. {
  29. printf("内存不足,分配失败\n");
  30. exit(1);
  31. }
  32. return head;
  33. }
  34. // =============插入新项===========
  35. Link InsertR(Item item, Link h)
  36. {
  37. if(h == z)
  38. {
  39. return NewItem(item, z, z, 1);
  40. }
  41. Key v = key(item);
  42. Key t = key(h->item);
  43. if(less(v, t))
  44. h->left = InsertR(item, h->left); //注意要有 h->left= ,容易忘记,想象仅有一个节点时,
  45. //InsertR()仅仅是返回的是新项的链接
  46. else
  47. h->right = InsertR(item, h->right);
  48. (h->N)++;
  49. return h;
  50. }
  51. void BSTreeInsert(Item item)
  52. {
  53. head = InsertR(item, head);
  54. }
  55. //===========搜索====================
  56. Item SearchR(Key v, Link h);
  57. Item BSTreeSearch(Key v)
  58. {
  59. return SearchR(v, head);
  60. }
  61. Item SearchR(Key v, Link h)
  62. {
  63. if(h == z)
  64. return NULLItem;
  65. Key t = key(h->item);
  66. if(eq(v, t))
  67. return h->item;
  68. else if(less(v, t))
  69. return SearchR(v, h->left);
  70. else
  71. return SearchR(v, h->right);
  72. }

2.2 使用BST排序

只需要中序遍历该二叉树:先访问左节点,然后访问根节点,最后访问右节点。

  1. //=============排序===================
  2. void visit(Link h)
  3. {
  4. if(h != NULL)
  5. printf("%c\t", h->item);
  6. }
  7. void BSTreeSort()
  8. {
  9. BSTreeSortR(head);
  10. }
  11. void BSTreeSortR(Link h)
  12. {
  13. if(h == z)
  14. return;
  15. BSTreeSortR(h->left);
  16. visit(h);
  17. BSTreeSortR(h->right);
  18. }

2.3 BST上根节点的插入(insert)

将一个新的数据项插入到BST的根,使得最近插入的关键字在树的顶部附近。
新的数据项基本不能满足,既大于原BST的左子树,又小于原BST的右子树,因此我们插入时,仍然先插入到树的底部,通过旋转操作,将其提升到根部。旋转操作涉及2个节点3条链接,旋转不改变树的性质。
这里写图片描述
如上图所示,右旋操作将k2节点向上提升,左旋将k1向上提升。因此当插入到树的叶节点上时,当处于当前根的左侧时,右旋成根;当处于当前根的右侧时,左旋成根。

  1. //=====BST中的旋转============
  2. Link rotR(Link h)
  3. {
  4. Link x = h->left;
  5. h->left = x->right;
  6. x->right = h;
  7. h->N -= (h->left->N + 1);
  8. x->N += (h->right->N + 1);
  9. return x;
  10. }
  11. Link rotL(Link h)
  12. {
  13. Link x = h->right;
  14. h->right = x->left;
  15. x->left = h;
  16. h->N -= (h->right->N + 1);
  17. x->N += (h->left->N + 1);
  18. return x;
  19. }

BST上根的插入:

  1. // ===========BST中的根的插入============
  2. Link BSTreeInsertRoot(Item item)
  3. {
  4. head = InsertRoot(item, head);
  5. }
  6. Link InsertRoot(Item item, Link h)
  7. {
  8. if(h == z)
  9. return NewItem(item, z, z, 1);
  10. Key v = key(item);
  11. Key t = key(h->item);
  12. if(less(v, t))
  13. {
  14. h->left = InsertRoot(item, h->left);
  15. h = rotR(h);//在根的左侧,右旋
  16. }
  17. else
  18. {
  19. h->right = InsertRoot(item, h->right);
  20. h = rotL(h);//在根的右侧,左旋
  21. }
  22. return h;
  23. }

2.4 BST上的选择(select)操作,划分操作

select操作找到关键字第k小的数据项,假设k = 0对应最小的数据项。左子树节点个数为t:若 t == k,则第k小即当前根节点的项;t > k,则第k小在左子树中;t < k,在右子树中的第k-t-1个(多减的1是当前子树的根节点)。

  1. // ========select-选择第k小的数据项,第0小是最小=========
  2. Item BSTreeSelect(int k)
  3. {
  4. return SelectR(k, head);
  5. }
  6. Item SelectR(int k, Link h)
  7. {
  8. if(h == z)
  9. return NULLItem;
  10. int t = ( (h->left == z) ? 0 : h->left->N );
  11. if(k < t)
  12. return SelectR(k, h->left);
  13. else if(k > t)
  14. return SelectR(k-t-1, h->right); //-1,减的是根节点
  15. else
  16. return h->item;
  17. }

将select改造成划分操作,实现重排树,将第k小的数据项放在根节点。即2.3中的根插入法:递归的把所有所求的节点放到当前子树的根节点,通过一次旋转。

  1. // === 划分操作(根据select,递归后添加旋转)=======
  2. Link partR(Link h, int k)
  3. {
  4. if(h == z)
  5. return z;
  6. int t = (h->left == z)?0:h->left->N;
  7. if(k < t)
  8. {
  9. partR(h->left, k);
  10. h = rotR(h);
  11. }
  12. else if(k > t)
  13. {
  14. partR(h->right, k-t-1);
  15. h = rotL(h);
  16. }
  17. return h;
  18. }

2.5 BST上的删除(delete)操作

在BST上删除给定关键字的一个节点,如果删除的节点在根部,需要组合两棵子树,而要组合它们,需要将右子树通过划分操作,将最小的元素当做划分元素,使得右子树中最小的元素旋转到根节点,此时该根的左子树为空:然后将原左子树连接到该根的左节点上(右子树全部大于左子树)。

  1. // ==============删除给定关键字的节点=========
  2. void BSTreeDelete(Key v)
  3. {
  4. head = deleteR(head, v);
  5. }
  6. Link deleteR(Link h, Key v)
  7. {
  8. if(h == z)
  9. return z;
  10. Key t = key(h->item);
  11. if(less(v, t))
  12. h->left = deleteR(h->left, v);
  13. else if(less(t, v))
  14. h->right = deleteR(h->right, v);
  15. else
  16. {
  17. Link tmp = h;
  18. h = joinR(h->left, h->right);
  19. free(tmp);
  20. }
  21. return h;
  22. }
  23. //将两棵子树的组合(根节点为右子树的最小项)代替被删除节点
  24. Link joinR(Link leftChild, Link rightChild)
  25. {
  26. if(rightChild == z)
  27. return leftChild;
  28. rightChild = partR(rightChild, 0);//旋转成左子树为空
  29. rightChild->left = leftChild; //原右子树全部大于左子树
  30. return rightChild;
  31. }

其他的删除策略:
(1)当被删除节点的左链接为空,直接使右子树成为新的根节点;事实证明该方法和上述程序实现都有缺点:如果对此树进行大量的“删除-插入”操作,最终会倾向得到一棵稍微失去平衡的树。
(2)懒惰的删除策略:将被删除节点留在数据结构中但标记为“已删除”,但必须确保大量带标注的节点不会引起时间或空间的过度浪费:可以将标注删除的点重用于插入;可以周期性重建数据结构,删除带标注点

2.6 两棵BST的连接(join)

怎样将两棵BST连接成一棵BST?
(1)遍历其中一棵,将节点依次插入到另一棵BST上;每次插入线性,全部非线性
(2)将两棵BST的节点全部取出放入数组,构造一棵新的BST;占用额外空间,但时间线性
*(3)将其中一棵BST(t1)的根节点用根插入法插入到另一棵BST(t2)的根节点上:那么留下两棵大于t2根的子树,两棵小于t2根的子树(t1和t2的左右子树)。然后我们递归的连接BST左右子树。因为每个节点至多成为根一次,所以时间线性。以下为程序实现:

  1. //==============BST的join操作===================
  2. Link BSTreeJoin(Link a, Link b)
  3. {
  4. if(a == z)
  5. return b;
  6. if(b == z)
  7. return a;
  8. //每个节点至多成为根一次,时间线性
  9. BSTreeInsertRoot(b, a->item);
  10. b->left = BSTreeJoin(b->left, a->left);
  11. b->right = BSTreeJoin(b->right, a->right);
  12. free(a);
  13. return b;
  14. }

3. BST的优缺点

基本的BST操作search、insert 和 sort容易实现,且对大小适中的随机操作序列进行的很好,因而BST被广泛用于动态符号表中。
缺点:
(1)存储链接需要空间。常把链接和数据记录看做同样大小,即内存空间,链接占2/3, 关键字占1/3
(2)树的平衡性会变差,性能急剧降低

4.参考资料和所有代码

《算法:C语言实现》P318-342

  1. // 注意递归终止条件和返回值。
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #define NULLItem '\0'
  5. #define less(A, B) (A < B)
  6. #define eq(A, B) (A == B)
  7. #define key(A) (A - 'a')
  8. typedef char Item;
  9. typedef int Key;
  10. typedef struct BSTree* Link;
  11. struct BSTree
  12. {
  13. Item item;
  14. Link left;
  15. Link right;
  16. int N; //引入计数,是为了实现select操作
  17. };
  18. static Link head, z;
  19. //=====新建一个节点=====
  20. Link NewItem(Item item, Link left, Link right, int N)
  21. {
  22. Link x = (Link)malloc(sizeof(*x));
  23. x->item = item;
  24. x->left = left;
  25. x->right = right;
  26. x->N = N;
  27. return x;
  28. }
  29. // ====初始化=======
  30. Link BSTreeInit()
  31. {
  32. head = (z = NewItem(NULLItem, NULL, NULL, 0));
  33. if(head == NULL)
  34. {
  35. printf("内存不足,分配失败\n");
  36. exit(1);
  37. }
  38. return head;
  39. }
  40. // =============插入新项===========
  41. Link InsertR(Item item, Link h)
  42. {
  43. if(h == z)
  44. {
  45. return NewItem(item, z, z, 1);
  46. }
  47. Key v = key(item);
  48. Key t = key(h->item);
  49. if(less(v, t))
  50. h->left = InsertR(item, h->left);
  51. else
  52. h->right = InsertR(item, h->right);
  53. (h->N)++;
  54. return h;
  55. }
  56. void BSTreeInsert(Item item)
  57. {
  58. head = InsertR(item, head);
  59. }
  60. //===========搜索====================
  61. Item SearchR(Key v, Link h)
  62. {
  63. if(h == z)
  64. return NULLItem;
  65. Key t = key(h->item);
  66. if(eq(v, t))
  67. return h->item;
  68. else if(less(v, t))
  69. return SearchR(v, h->left);
  70. else
  71. return SearchR(v, h->right);
  72. }
  73. Item BSTreeSearch(Key v)
  74. {
  75. return SearchR(v, head);
  76. }
  77. //=============排序===================
  78. void visit(Link h)
  79. {
  80. if(h != NULL)
  81. printf("%c\t", h->item);
  82. }
  83. void BSTreeSortR(Link h)
  84. {
  85. if(h == z)
  86. return;
  87. BSTreeSortR(h->left);
  88. visit(h);
  89. BSTreeSortR(h->right);
  90. }
  91. void BSTreeSort()
  92. {
  93. BSTreeSortR(head);
  94. }
  95. //=====BST中的旋转============
  96. Link rotR(Link h)
  97. {
  98. Link x = h->left;
  99. h->left = x->right;
  100. x->right = h;
  101. h->N -= (h->left->N + 1);
  102. x->N += (h->right->N + 1);
  103. return x;
  104. }
  105. Link rotL(Link h)
  106. {
  107. Link x = h->right;
  108. h->right = x->left;
  109. x->left = h;
  110. h->N -= (h->right->N + 1);
  111. x->N += (h->left->N + 1);
  112. return x;
  113. }
  114. // ===========BST中的根的插入============
  115. Link InsertRoot(Item item, Link h)
  116. {
  117. if(h == z)
  118. return NewItem(item, z, z, 1);
  119. Key v = key(item);
  120. Key t = key(h->item);
  121. if(less(v, t))
  122. {
  123. h->left = InsertRoot(item, h->left);
  124. h = rotR(h);
  125. }
  126. else
  127. {
  128. h->right = InsertRoot(item, h->right);
  129. h = rotL(h);
  130. }
  131. return h;
  132. }
  133. Link BSTreeInsertRoot(Item item)
  134. {
  135. head = InsertRoot(item, head);
  136. }
  137. // ========select-选择第k小的数据项,第0小是最小=========
  138. Item SelectR(int k, Link h)
  139. {
  140. if(h == z)
  141. return NULLItem;
  142. int t = ( (h->left == z) ? 0 : h->left->N );
  143. if(k < t)
  144. return SelectR(k, h->left);
  145. else if(k > t)
  146. return SelectR(k-t-1, h->right); //-1,减的是根节点
  147. else
  148. return h->item;
  149. }
  150. Item BSTreeSelect(int k)
  151. {
  152. return SelectR(k, head);
  153. }
  154. // === 划分操作(select)=======
  155. Link partR(Link h, int k)
  156. {
  157. if(h == z)
  158. return z;
  159. int t = (h->left == z)?0:h->left->N;
  160. if(k < t)
  161. {
  162. partR(h->left, k);
  163. h = rotR(h);
  164. }
  165. else if(k > t)
  166. {
  167. partR(h->right, k-t-1);
  168. h = rotL(h);
  169. }
  170. return h;
  171. }
  172. // ==============删除给定关键字的节点=========
  173. Link joinR(Link leftChild, Link rightChild)
  174. {
  175. if(rightChild == z)
  176. return leftChild;
  177. rightChild = partR(rightChild, 0);//旋转成左子树为空
  178. rightChild->left = leftChild; //原右子树全部大于左子树
  179. return rightChild;
  180. }
  181. Link deleteR(Link h, Key v)
  182. {
  183. if(h == z)
  184. return z;
  185. Key t = key(h->item);
  186. if(less(v, t))
  187. h->left = deleteR(h->left, v);
  188. else if(less(t, v))
  189. h->right = deleteR(h->right, v);
  190. else
  191. {
  192. Link tmp = h;
  193. h = joinR(h->left, h->right);
  194. free(tmp);
  195. }
  196. return h;
  197. }
  198. void BSTreeDelete(Key v)
  199. {
  200. head = deleteR(head, v);
  201. }
  202. //==============BST的join操作===================
  203. Link BSTreeJoin(Link a, Link b)
  204. {
  205. if(a == z)
  206. return b;
  207. if(b == z)
  208. return a;
  209. //每个节点至多成为根一次,时间线性
  210. // BSTreeInsertRoot(b, a->item);
  211. b->left = BSTreeJoin(b->left, a->left);
  212. b->right = BSTreeJoin(b->right, a->right);
  213. free(a);
  214. return b;
  215. }
  216. //============= 驱动函数 =============
  217. int main()
  218. {
  219. BSTreeInit();
  220. for(int i = 0; i < 20; i++)
  221. {
  222. char c = 'a' + (rand()%26);
  223. Key v = key(c);
  224. printf("%c, %d\n", c, v);
  225. BSTreeInsert(c);
  226. }
  227. printf("Root = %c\n", head->item);
  228. BSTreeInsertRoot('z');
  229. BSTreeInsertRoot('b');
  230. BSTreeInsert('b');
  231. printf("Root = %c\n", head->item);
  232. int k = 4;
  233. printf("第%d小的项是%c\n", k, BSTreeSelect(k));
  234. printf("\n");
  235. printf("\n搜索:\n");
  236. printf("%c\n", BSTreeSearch(4));
  237. printf("%c\n", BSTreeSearch(-1));
  238. printf("%c\n", BSTreeSearch(0));
  239. printf("%c\n", BSTreeSearch(100));
  240. printf("\n排序:\n");
  241. BSTreeSort();
  242. Key v = 3;
  243. printf("\n删除关键字为%d的节点:%c\n", v, BSTreeSearch(v));
  244. BSTreeDelete(v);
  245. printf("\n排序:\n");
  246. BSTreeSort();
  247. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注