创造练习——自适应树(self-adjusting Tree)

这个树的定义的确很有问题。其实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
  15. // a b
  16. // / -> /
  17. // b a
  18. TreeNode sRightRotate(TreeNode a, TreeNode* b)
  19. {
  20. a->setRight(b->getLeft());
  21. b->setLeft(a);
  22. return b;
  23. }
        1. TreeNode insertNode(TreeNode subroot,TreeNode* prev,T& data)
  24. {
  25. if (subroot == NULL)
  26. {
  27. subroot = new TreeNode(data);
  28. return subroot;
  29. }
  30. else
  31. {
  32. TreeNode* tempNode = NULL;
  33. TreeNode* tempRoot = NULL;
  34. if (subroot->getData() > data)
  35. {
    1. tempNode = insertNode(subroot->getLeft(),subroot,data);
  36. tempRoot = sLeftRotate(subroot,tempNode);
    1. }
  37. else if (subroot->getData() < data)
  38. {
  39. tempNode = insertNode(subroot->getRight(),subroot,data);
  40. tempRoot = sRightRotate(subroot,tempNode);
  41. }
  42. else
  43. {
  44. throw “the same key” ;
  45. }
    1. if (prev == NULL)
  46. {
  47. this ->head = tempRoot;
  48. }
  49. else
  50. {
  51. if (prev->getData() > tempRoot->getData())
  52. {
  53. prev->setLeft(tempRoot);
  54. }
  55. else
  56. {
  57. prev->setRight(tempRoot);
  58. }
  59. }
  60. return tempRoot;
  61. }
  62. }
  63. public :
  64. SelfTree(T& data):BinaryTree(data)
  65. {
    1. }
    1. ~SelfTree()
  66. {
    1. }
    1. void insertNode(T& data)
  67. {
  68. insertNode( this ->head,NULL,data);
  69. }
    1. };
  • 本文作者: 帐前卒
  • 本文链接: http://chillyc.info/2008/2797586/
  • 版权声明: 本博客所有文章除特别声明外,只能复制超链接地址,且必须注明出处!