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

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

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

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

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

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

TreeNode<T>* insertNode(TreeNode<T>* subroot,TreeNode<T>* 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<classT>
2. classSelfTree:publicBinaryTree<T>
3. {
4. private:
5. //returnthesubtreeroot
6. //ab
7. ///->/
8. //ba
9. TreeNode<T>*sLeftRotate(TreeNode<T>*a,TreeNode<T>*b)
10. {
11. a->setLeft(b->getRight());
12. b->setRight(a);
13. returnb;
14. }
17. //returnthesubtreeroot
18. //ab
19. ///->/
20. //ba
21. TreeNode<T>*sRightRotate(TreeNode<T>*a,TreeNode<T>*b)
22. {
23. a->setRight(b->getLeft());
24. b->setLeft(a);
25. returnb;
26. }
30. TreeNode<T>*insertNode(TreeNode<T>*subroot,TreeNode<T>*prev,T&data)
31. {
32. if(subroot==NULL)
33. {
34. subroot=newTreeNode<T>(data);
35. returnsubroot;
36. }
37. else
38. {
39. TreeNode<T>*tempNode=NULL;
40. TreeNode<T>*tempRoot=NULL;
41. if(subroot->getData()>data)
42. {
44. tempNode=insertNode(subroot->getLeft(),subroot,data);
45. tempRoot=sLeftRotate(subroot,tempNode);
47. }
48. elseif(subroot->getData()<data)
49. {
50. tempNode=insertNode(subroot->getRight(),subroot,data);
51. tempRoot=sRightRotate(subroot,tempNode);
52. }
53. else
54. {
55. throw"thesamekey";
56. }
58. if(prev==NULL)
59. {
60. this->head=tempRoot;
61. }
62. else
63. {
64. if(prev->getData()>tempRoot->getData())
65. {
66. prev->setLeft(tempRoot);
67. }
68. else
69. {
70. prev->setRight(tempRoot);
71. }
72. }
73. returntempRoot;
74. }
75. }
76. public:
77. SelfTree(T&data):BinaryTree(data)
78. {
80. }
82. ~SelfTree()
83. {
85. }
87. voidinsertNode(T&data)
88. {
89. insertNode(this->head,NULL,data);
90. }
92. };