创造练习——自适应树(Self-Adjusting Tree)

Posted on Edited on Word count in article: 1.8k Reading time ≈ 2 mins.

这个树的定义的确很有问题。其实AVLTree和SplayTree以及RedBlackTree都是self-adjusting Tree

因为如果是树做索引那么大部分的时间将用来查找。这个树在查找上可以将查找的节点提升到树根，插入时也是一样。这样提高了查找的效率。并且操作系统有一种说法是近来用
到的，将来用到的几率也会很大（LRU原理）。删除，既然删除对于此树来说再也没有什么，那就直接删除算了。

根据这几点想法。自己做一个self-adjusting Tree。但是还没有验证是否能达到实际水平的O（nlogn）。虽然理论上这个树并不能达到这样一个时间
复杂度。但是对于实际数据来说，还是有可能达到的。不知道有没有这么lucky。

因为对于这个树来说插入和查找操作其实差不多。

所以下面只介绍插入操作。找到要插入的地方，反遍历单旋转（这里和SplayTree不同一点是只使用单旋转）

TreeNode* insertNode(TreeNode* subroot,TreeNode* prev,T& data)

返回值为当前子树根节点

1.subroot是否为空,创建新的节点，并返回subroot

2.如果不为空

A.subroot中的值 < data中的值,对subroot右子树调用insertNode()，subroot
与当前右子树根节点采用旋转操作。将两个节点位置对换。

B.subroot中的值 > data中的值，对subroot左子树调用insertNode()，subroot
与当前左子树根节点采用旋转操作。将两个节点位置对换。

C.subroot中的值 == data中的值，do nothing

3.查看该节点是否已成为根节点。如果是的话，调整根节点的值。

下面给出代码。

  1. template < class T>
  2. class SelfTree: public BinaryTree
  3. {
  4. private :
  5. // return the sub tree root
  6. //        a               b
  7. //       /       ->        /
  8. //      b                   a
  9. TreeNode* sLeftRotate(TreeNode* a,TreeNode* b)
  10. {
  11. a->setLeft(b->getRight());
  12. b->setRight(a);
  13. return b;
  14. }
      1. // return the sub tree root
  16. //        a               b
  17. //         /     ->      /
  18. //          b           a
  19. TreeNode* sRightRotate(TreeNode* a, TreeNode* b)
  20. {
  21. a->setRight(b->getLeft());
  22. b->setLeft(a);
  23. return b;
  24. }
        1. TreeNode* insertNode(TreeNode* subroot,TreeNode* prev,T& data)
  26. {
  27. if (subroot == NULL)
  28. {
  29. subroot = new TreeNode(data);
  30. return subroot;
  31. }
  32. else
  33. {
  34. TreeNode* tempNode = NULL;
  35. TreeNode* tempRoot = NULL;
  36. if (subroot->getData() > data)
  37. {
    1. tempNode = insertNode(subroot->getLeft(),subroot,data);
  39. tempRoot = sLeftRotate(subroot,tempNode);
    1. }
  41. else if (subroot->getData() < data)
  42. {
  43. tempNode = insertNode(subroot->getRight(),subroot,data);
  44. tempRoot = sRightRotate(subroot,tempNode);
  45. }
  46. else
  47. {
  48. throw “the same key” ;
  49. }
    1. if (prev == NULL)
  51. {
  52. this ->head = tempRoot;
  53. }
  54. else
  55. {
  56. if (prev->getData() > tempRoot->getData())
  57. {
  58. prev->setLeft(tempRoot);
  59. }
  60. else
  61. {
  62. prev->setRight(tempRoot);
  63. }
  64. }
  65. return tempRoot;
  66. }
  67. }
  68. public :
  69. SelfTree(T& data):BinaryTree(data)
  70. {
    1. }
    1. ~SelfTree()
  73. {
    1. }
    1. void insertNode(T& data)
  76. {
  77. insertNode( this ->head,NULL,data);
  78. }
    1. };