Splay伸展树

伸展树，感觉对我这种菜鸟还是有些吃力，主要也是旋转的时候吧，把要查询的节点旋转到根节点，看网上是有两种方法，一是从上到下，一是从下到上。从上到下，是把树拆分成中树，左树和右树，始终保证目标节点在中树，不断向下把中树的节点添到右树或者左树，直到目标节点为中树的根，再将三树合并起来。另外一种从下到上，旋转操作类似AVL树中的旋转，但是判断好像不是很好写，我写的是从上到下的，另外删除也很巧妙，先把目标节点旋转到根，若此时左子树为空直接删除，否则找到左子树最右的节点当头，利用伸展树的特殊旋转就可以一步删除，太牛叉了，还有就是一个元素和指向它的指针的巧妙运用，真是涨了不少知识啊，，，，

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 
  5 typedef struct _spaly
  6 {
  7     int key;
  8     struct _spaly* left;
  9     struct _spaly* right;
 10 }*Pspaly;
 11 
 12 Pspaly splay(Pspaly tree,int k);
 13 void Destory(Pspaly tree);
 14 void Printf(Pspaly tree);
 15 Pspaly Insert(Pspaly tree,int k);
 16 Pspaly Node(int k);
 17 Pspaly Delete(Pspaly tree,int k);
 18 Pspaly Search(Pspaly tree,int k);
 19 
 20 int main()
 21 {
 22     Pspaly tree=NULL;
 23     tree = Insert(tree,3);
 24     tree = Insert(tree,6);
 25     tree = Insert(tree,1);
 26     tree = Insert(tree,5);
 27     tree = Insert(tree,7);
 28     tree = Insert(tree,0);
 29     tree = Insert(tree,11);
 30     Printf(tree);
 31     printf("
");
 32     tree=splay(tree,2);
 33      Printf(tree);
 34      printf("
");
 35     // tree = splay(tree,6);
 36      tree = Delete(tree,3);
 37      Printf(tree);
 38       printf("
");
 39      tree = splay(tree,11);
 40       Printf(tree);
 41     return 0;
 42 }
 43 
 44 Pspaly Node(int k)
 45 {
 46     Pspaly node = (Pspaly)malloc(sizeof(_spaly));
 47     node->key = k;
 48     node->left = NULL;
 49     node->right = NULL;
 50     return node;
 51 }
 52 
 53 Pspaly Insert(Pspaly tree,int k)
 54 {
 55     Pspaly node = Node(k);
 56     if(tree==NULL)
 57     {
 58         tree = node;
 59         return tree;
 60     }
 61     if(k<tree->key)
 62     {
 63         tree->left = Insert(tree->left,k);
 64     }
 65     else if(k>tree->key)
 66     {
 67         tree->right = Insert(tree->right,k);
 68     }
 69     return tree;
 70 }
 71 
 72 //销毁伸展树
 73 void Destory(Pspaly tree)
 74 {
 75     if(tree==NULL)return;
 76     Destory(tree->left);
 77     Destory(tree->right);
 78     free(tree);
 79 }
 80 
 81 //核心，旋转操作
 82 Pspaly splay(Pspaly tree,int k)
 83 {
 84     Pspaly l,r;
 85     _spaly N;
 86     l = r = &N; //  
 87     while(true)
 88     {
 89         if(k<tree->key)
 90         {
 91             if(tree->left==NULL)
 92                 break;//当目标节点不在树上时，在删除时有大用
 93             if(k<tree->left->key)
 94             {
 95                 Pspaly tem = tree->left;
 96                 tree->left = tem->right;
 97                 tem->right = tree;
 98                 tree = tem;
 99             }
100             //将节点加到右树
101             r->left = tree; 
102             r = tree;
103             tree = tree->left;
104         }
105         else if(k>tree->key)
106         {
107             if(tree->right==NULL)break;
108             if(k>tree->right->key)
109             {
110                 Pspaly tem = tree->right;
111                 tree->right = tem->left;
112                 tem->left = tree;
113                 tree = tem;
114             }
115             l->right = tree;
116             l = tree;
117             tree = tree->right;
118         }
119         else
120         {
121             break;
122         }
123 
124     }
125     
126     //合并三课树
127         l->right = tree->left;
128         r->left = tree->right;
129         tree->left = N.right;
130         tree->right = N.left;
131         return tree;
132 }
133 
134 //打印函数
135 void Printf(Pspaly tree)
136 {
137     if(tree==NULL)return;
138     printf("父亲结点是:%d",tree->key);
139     printf(" 左儿子是:");
140     if(tree->left==NULL)printf("NULL");
141     else printf("%d",tree->left->key);
142     printf(" 右儿子是:");
143     if(tree->right==NULL)printf("NULL
");
144     else printf("%d
",tree->right->key);
145     Printf(tree->left);
146     Printf(tree->right);
147 }
148 
149 Pspaly Delete(Pspaly tree,int k)
150 {
151     Pspaly tem;
152     if(Search(tree,k)==NULL)
153     {
154         printf("无
");
155         return NULL;
156     }
157     tree = splay(tree,k);
158     if(tree->left==NULL)
159         return tree->right;
160     else
161     {
162         //将tree->left的最右子树当做根
163       tem = splay(tree->left,k);
164       tem->right = tree->right;
165     }
166     free(tree);
167     return tem;
168 }
169 
170 Pspaly Search(Pspaly tree,int k)
171 {
172     if(tree==NULL)return NULL;
173     if(k<tree->key)Search(tree->left,k);
174     else if(k>tree->key)Search(tree->right,k);
175     else
176         return tree;
177 }

View Code

再贴个C++的

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <cstring>
  4 
  5 using namespace std;
  6 
  7 template<class T>
  8 class SplayNode
  9 {
 10 public:
 11     T key;
 12     SplayNode* left;
 13     SplayNode* right;
 14 
 15     SplayNode():left(NULL),right(NULL){}
 16     SplayNode(T value,SplayNode* l,SplayNode* r):key(value),left(l),right(r){}
 17 
 18     /*SplayNode()
 19     {
 20         left  = NULL;
 21         right = NULL;
 22     }
 23     SplayNode(T value,SplayNode* l,SplayNode* r)
 24     {
 25         key = value;
 26         left = l;
 27         right = r;
 28     }*/
 29 };
 30 
 31 template <class T>
 32 class SplayTree
 33 {
 34 private:
 35     SplayNode<T>* mroot;
 36 public:
 37     SplayTree();
 38     ~SplayTree();
 39     SplayNode<T>* splay(SplayNode<T>* tree,T k);
 40     void Destory(SplayNode<T>* tree);
 41     void Printf(SplayNode<T>* tree);
 42     void Insert(T k);
 43     SplayNode<T>* Node(T k);
 44     SplayNode<T>* Delete(SplayNode<T>* tree,T k);
 45     SplayNode<T>* Insert_into(SplayNode<T>* Tree,T k);
 46     SplayNode<T>* Search(T k);
 47     void Printf(SplayTree<T>* tree);
 48     void _printf();
 49 };
 50 
 51 template <class T>
 52 SplayTree<T>::SplayTree()
 53 {
 54     mroot = NULL;
 55 }
 56 
 57 template <class T>
 58 SplayTree<T>::~SplayTree()
 59 {
 60     Destory(mroot);
 61 }
 62 
 63 template <class T>
 64 void SplayTree<T>::Destory(SplayNode<T>* tree)
 65 {
 66     if(tree==NULL)return;
 67     Destory(tree->left);
 68     Destory(tree->right);
 69     delete tree;
 70 }
 71 
 72 template <class T>
 73 SplayNode<T>* SplayTree<T>::Node(T k)
 74 {
 75     SplayNode<T>* node = new SplayNode<T>(k,NULL,NULL);
 76    /* node->key = k;
 77     node->left = NULL;
 78     node->right = NULL;*/
 79     return node;
 80 }
 81 
 82 template <class T>
 83 void SplayTree<T>::Insert(T k)
 84 {
 85     mroot = Insert_into(mroot,k);
 86 }
 87 
 88 template <class T>
 89 void SplayTree<T>::_printf()
 90 {
 91     SplayTree::Printf(mroot);
 92 }
 93 
 94 template <class T>
 95 void SplayTree<T>::Printf(SplayNode<T>* tree)
 96 {
 97     if(tree==NULL)return;
 98     printf("父亲节点是:%d",tree->key);
 99     printf(" 左儿子是:");
100     if(tree->left==NULL)printf("NULL");
101     else printf("%d",tree->left->key);
102     printf(" 右儿子是:");
103     if(tree->right==NULL)printf("NULL
");
104     else printf("%d
",tree->right->key);
105     Printf(tree->left);
106     Printf(tree->right);
107 }
108 template <class T>
109 SplayNode<T>* SplayTree<T>::Insert_into(SplayNode<T>* tree,T k)
110 {
111     SplayNode<T>* node = SplayTree<T>::Node(k);
112     if(tree==NULL)
113     {
114         tree = node;
115         return tree;
116     }
117     if(k<tree->key)
118     {
119         tree->left = Insert_into(tree->left,k);
120     }
121     else if(k>tree->key)
122     {
123         tree->right = Insert_into(tree->right,k);
124     }
125     return tree;
126 }
127 
128 template <class T>
129 SplayNode<T>* SplayTree<T>::splay(SplayNode<T>* tree,T k)
130 {
131     SplayNode<T>  N,*r,*l;
132     N.left = N.right = NULL;
133     l = r = &N;
134     while(true)
135     {
136         if(k<tree->key)
137         {
138             if(tree->left==NULL)break;
139             if(k<tree->left->key)
140             {
141                 SplayNode<T>* tem = tree->left;
142                 tree->left = tem->right;
143                 tem->right = tree;
144                 tree = tem;
145             }
146             r->left = tree;
147             r = tree;
148             tree = tree->left;
149         }
150         if(k>tree->key)
151         {
152             if(tree->right==NULL)break;
153             if(k>tree->right->key)
154             {
155                 SplayNode<T>* tem = tree->right;
156                 tree->right = tem->left;
157                 tem->left = tree;
158                 tree = tem;
159             }
160             l->right = tree;
161             l = tree;
162             tree = tree->right;
163         }
164         else
165         {
166             break;
167         }
168     }
169     l->right = tree->left;
170     r->left = tree->right;
171     tree->left = N.right;
172     tree->right = N.left;
173     return tree;
174 }
175 
176 template <class T>
177 SplayNode<T>* SplayTree<T>::Search(T k)
178 {
179     mroot = SplayTree<T>::splay(mroot,k);
180 }
181 int main()
182 {
183     SplayTree<int>* tree = new SplayTree<int>();
184     tree->Insert(3);
185     tree->Insert(6);
186     tree->Insert(1);
187     tree->Insert(5);
188     tree->Insert(7);
189     tree->Insert(0);
190     tree->Insert(11);
191     tree->_printf();
192     printf("
");
193     tree->Search(11);
194     tree->_printf();
195     return 0;
196 }

View Code