编程练习——伸展树(SplayTree)

Posted on Edited on Word count in article: 4.2k Reading time ≈ 4 mins.

伸展树用于查询结果的概率非平均情况，即起初假设某些要查询的信息偏多，有些信息几乎无人问津。对于平均访问概率来说，使用SplayTree实现并不是一个明智的选
择。

可能会用到此数据结构的程序：词典或者多维搜索树，还有连接/切除树（link/cut tree）（这个树是用于网络优化问题包括最大流和最小代价）

  1. /*
  2. * create by chico chen
  3. * date: 2008/10/02
  4. */
  5. template < class T>
  6. class SplayTree: public BinaryTree
  7. {
    1. public :
  9. explicit SplayTree(T& data):BinaryTree(data)
  10. {
    1. }
    1. explicit SplayTree(TreeNode* root):BinaryTree(root)
  13. {
    1. }
  15. ~SplayTree()
  16. {
    1. }
  18. public :
    1. void insertNode(T& data)
  20. {
    1. if (NULL == this ->head)
  22. {
  23. this ->head = new TreeNode(data);
  24. return ;
  25. }
    1. splay( this ->head,data);
  27. if ( this ->head->data > data)
  28. {
  29. //     A     B                 A
  30. //            / /     ->         / /
  31. //         C   D             C   B
  32. //                                /
  33. //                                 D
  34. TreeNode* node = new TreeNode(data);
  35. node->left = this ->head->left ;
  36. node->right = this ->head;
  37. this ->head->left = NULL;
  38. this ->head = node;
  39. }
  40. else if ( this ->head->data < data)
  41. {
  42. //     A     B                 A
  43. //            / /     ->         / /
  44. //         C   D             B   D
  45. //                              /
  46. //                            C
  47. TreeNode* node = new TreeNode(data);
  48. node->right = this ->head->right;
  49. node->left = this ->head;
  50. this ->head->right = NULL;
  51. this ->head = node;
    1. }
  53. else
  54. {
  55. // insert the same key
  56. // throw exception
  57. throw “the same key” ;
  58. }
  59. }
    1. // use the data as key to splay the tree
  61. // then we can get the structures of the tree like the following:
  62. //     (1)  A             (2)   A
  63. //              /                    / /
  64. //               B               C   B
  65. // the difference between the two structures is whether the root has left child
  66. // In case (1), we can simpliy make the root right child instead the root.
  67. // In case (2), we should splay the root left subtree and then it will be
  68. // changed like case (1), and we make the splayed left subtree root instead
  69. // the root.
  70. void deleteNode(T& data)
  71. {
    1. if (NULL == this ->head)
  73. {
  74. return ;
  75. }
  76. splay( this ->head, data);
  77. if ( this ->head->data != data)
  78. {
  79. // not found the key to delete
  80. return ;
  81. }
  82. TreeNode* newRoot;
  83. if (NULL == this ->head->left)
  84. {
  85. newRoot = this ->head->right;
  86. }
  87. else
  88. {
  89. newRoot = this ->head->left;
  90. splay(newRoot,data);
  91. newRoot->right = this ->head->right;
  92. }
  93. delete this ->head;
  94. this ->head = newRoot;
    1. }
      1. TreeNode* searchNode(T& data)
  97. {
  98. if (NULL == this ->head)
  99. {
  100. return NULL;
  101. }
  102. splay( this ->head, data);
  103. if ( this ->head->data == data)
  104. {
  105. return this ->head;
  106. }
  107. return NULL;
  108. }
    1. private :
  110. // use top-down splay method,
    1. // you should make the suitable final step
  112. // according to the situation, such as “insert”, “delete”, “search”.
  113. // And what’s the top-down method?
  114. // now we should add LeftMaxRoot as L and RightMinRoot as R
  115. // 1. L  A  R         2. L  A  R        3. L   A   R
  116. //         /                        /                      /
  117. //        B                     B                     B
  118. //                               /                          /
  119. //                              C                          C
  120. //
  121. // 1.->L  B  R      2.->L  C   R        3.L   C    R
  122. //        /                     /                          /      /
  123. //     A                    B                         B    A
  124. //                             /
  125. //                              A
  126. // but in case 3. we can simplified case 3 rotate as
  127. // 3. L   B      R
  128. //            /      /
  129. //            C  A
  130. // and we must integrate the LeftMaxRoot and RightMinRoot together,
  131. // then we have final step to do this. And L is left tree, and R is right tree.
  132. // L     A     R               A
  133. //         / /         ->         /   /
  134. //       B   C                L     R
  135. //                                 /   /
  136. //                                B C
  137. void splay(TreeNode* &subRoot,T& data)
  138. {
  139. if (NULL == subRoot)
  140. {
  141. return ;
  142. }
  143. TreeNode* leftRoot;
  144. TreeNode* rightRoot;
  145. // here some code use static member, if you promise you have sync-control
  146. // or you don’t use this code in thread or process, you could choose static
  147. // member to accelerate your program.
  148. // It means the following code is thread-safe.
  149. TreeNode head(data);
  150. leftRoot = rightRoot = &head;
  151. while ( true )
  152. {
    1. if (data < subRoot->data)
  154. {
  155. if (NULL == subRoot->left)
  156. {
  157. break ;
  158. }
  159. else if (data < subRoot->left->data)
  160. {
  161. // Left rotate
  162. TreeNode* tempLeft = subRoot->left;
  163. subRoot->left = tempLeft->right;
  164. tempLeft->right = subRoot;
  165. subRoot = tempLeft;
    1. }
  167. else
  168. {
  169. // do nothing
  170. }
  171. // split the tree with right root
  172. if (NULL == subRoot->left)
  173. break ;
  174. rightRoot->left = subRoot;
  175. rightRoot = subRoot;
  176. subRoot = subRoot->left ;
    1. }
  178. else if (data > subRoot->data)
  179. {
  180. if (NULL == subRoot->right)
  181. {
  182. // need not to rotate
  183. break ;
  184. }
  185. else if (data > subRoot->right->data)
  186. {
  187. // right rotate
  188. TreeNode* tempRight = subRoot->right;
  189. subRoot->right = tempRight->left;
  190. tempRight->left = subRoot;
  191. subRoot = tempRight;
  192. }
  193. else
  194. {
  195. // do nothing
  196. }
  197. // split the tree by left root
  198. if (NULL == subRoot->right)
  199. break ;
  200. leftRoot->right = subRoot;
  201. leftRoot = subRoot;
    1. subRoot = subRoot->right;
  203. }
  204. else
  205. {
  206. // the same key
  207. break ;
  208. }
    1. }
    1. // the final step
  211. // we have find the last node, ant then we should
  212. // integrate the left root, the right root and the root into One tree.
  213. // head.right is left root
  214. // head.left is right root
  215. leftRoot->right = subRoot->left;
  216. rightRoot->left = subRoot->right;
  217. subRoot->left = head.right;
  218. subRoot->right = head.left;
      1. }
          1. };

发现CSDN的代码编辑器还是有些问题，空格处理不好，导致我注释中的树形错乱了…

不过没有大关系，应该抓起旁边的纸边看边画就能明白。

在网上找splayTree的源码学习，发现凭自己的实力还真的看不懂…

幸好在家里翻到了古老的数据结构教材。这才明白。

至于不使用添加父节点或者采用递归栈等方式的原因在于：空间消耗太大。

另外递归栈也不好调试

这个top-down splay的方法消耗空间为O(1)，带来的效果却和添加父节点类似，没有使用递归的方法。

至于具体的方法，在代码的注释里。

这里为了编代码方便就没有将treeNode 类中的成员变量私有化。

另外的BinaryTree的代码在 _ 以前的blog中 _
 。

这个splayTree还是较为完整的，至少比Apache中的splayTree完整些。现在我依旧不明白为什么Apache中的内存管理使用的是splayTre
e,而且splayTree还没有delete函数。难道内存管理的东西没有必要删除吗？

思考中…