手植这棵自顶向下伸展树，何时亭亭如盖呢？

前言

伸展树，解释起来真的很晕。先看一下我写的关于伸展树的理论部分吧：伸展树，据说比AVL树要简单一些。简单个球啊，写完了我还是晕晕的，所以又看了很久。

但是，总有那么一瞬，总有那么一句话，会让你茅塞顿开。
所以，我再简单讲一遍自顶向下伸展树原理，自底向上是真的，好理解，但是实现成本太高。

自顶向下原理图

说在前头

为了叙述的方便，上图的右旋叫做X绕Y右旋，左旋叫做Y绕X左旋。

当我们沿着树向下搜索某个节点X的时候，我们将搜索路径上的节点及其子树移走。我们构建两棵临时的树──左树和右树。没有被移走的节点构成的树称作中树。在伸展操作的过程中：
1、当前节点X是中树的根。
2、左树L保存小于X的节点。
3、右树R保存大于X的节点。
开始时候，X是树T的根，左右树L和R都是空的。

和自底向上一样，自顶向下也分了三种情况。

zig(单旋转)

如上图，在搜索到X的时候，所查找的节点比X小，将Y旋转到中树的树根。旋转之后，X及其右子树被移动到右树上。很显然，右树上的节点都大于所要查找的节点。注意X被放置在右树的最小的位置，也就是X及其子树比原先的右树中所有的节点都要小。这是由于越是在路径前面被移动到右树的节点，其值越大。读者可以分析一下树的结构，原因很简单。（就这句，给我点醒了）

通了一点之后，后面就好办了。

zig-zig(一字型旋转)

在这种情况下，所查找的节点在Z的子树中，也就是，所查找的节点比X和Y都小。所以要将X，Y及其右子树都移动到右树中。首先是Y绕X右旋，然后Z绕Y右旋，最后将Z的右子树（此时Z的右子节点为Y）移动到右树中。注意右树中挂载点的位置。

zig-zag(之字型旋转)

在这种情况中，首先将Y右旋到根。这和Zig的情况是一样的。然后变成上图右边所示的形状。接着，对Z进行左旋，将Y及其左子树移动到左树上。这样，这种情况就被分成了两个Zig情况。这样，在编程的时候就会简化，但是操作的数目增加（相当于两次Zig情况）。

合并树

将中树的左右子树分别连接到左树的右子树和右树的左子树上。将左右树作为X的左右子树。重新最成了一所查找的节点为根的树。

我一直没看懂的示例

下面是一个查找节点19的例子：
在例子中，树中并没有节点19,最后，距离节点最近的节点18被旋转到了根作为新的根。节点20也是距离节点19最近的节点，但是节点20没有成为新根，这和节点20在原来树中的位置有关系。

而一直困扰我的，就是第二步到第三步的转化，为什么要把20提上去，现在明白了。

自顶向下伸展树代码实现

#include <stdlib.h>
#include <stdio.h>
	int size;  /* number of nodes in the tree */ /* Not actually needed for any of the operations */
typedef struct tree_node Tree;
struct tree_node
{ Tree * left, * right; int item;
};

Tree * splay (int i, Tree * t)
{
 /* Simple top down splay, not requiring i to be in the tree t.  */
 /* What it does is described above. */ Tree N, *l, *r, *y; if (t == NULL) return t; N.left = N.right = NULL; l = r = &N; for (;;) { if (i < t->item) { if (t->left == NULL) break; if (i < t->left->item) { y = t->left; /* rotate right */ t->left = y->right; y->right = t; t = y; if (t->left == NULL) break; } r->left = t; /* link right */ r = t; t = t->left; } else if (i > t->item) { if (t->right == NULL) break; if (i > t->right->item) { y = t->right; /* rotate left */ t->right = y->left; y->left = t; t = y; if (t->right == NULL) break; } l->right = t; /* link left */ l = t; t = t->right; } else break; } l->right = t->left; /* assemble */ r->left = t->right; t->left = N.right; t->right = N.left; return t;
}
/* Here is how sedgewick would have written this. */
/* It does the same thing. */
Tree * sedgewickized_splay (int i, Tree * t)
{ Tree N, *l, *r, *y; if (t == NULL) return t; N.left = N.right = NULL; l = r = &N; for (;;) { if (i < t->item) { if (t->left != NULL && i < t->left->item) { y = t->left; t->left = y->right; y->right = t; t = y; } if (t->left == NULL) break; r->left = t; r = t; t = t->left; } else if (i > t->item) { if (t->right != NULL && i > t->right->item) { y = t->right; t->right = y->left; y->left = t; t = y; } if (t->right == NULL) break; l->right = t; l = t; t = t->right; } else break; } } l->right=t->left; r->left=t->right; t->left=N.right; t->right=N.left; return t;
}

Tree * insert(int i, Tree * t)
{
/* Insert i into the tree t, unless it's already there. */
/* Return a pointer to the resulting tree. */ Tree * new_node; new_node = (Tree *) malloc (sizeof (Tree)); if (new_node == NULL) { printf("Ran out of space\n"); exit(1); } new_node ->item = i; if (t == NULL) { new_node->left = new_node->right = NULL; size = 1; return new_node; } t = splay(i,t); if (i < t->item) { new_node->left = t->left; new_node->right = t; t->left = NULL; size ++; return new_node; } else if (i > t->item) { new_node->right = t->right; new_node->left = t; t->right = NULL; size++; return new_node; } else { /* We get here if it's already in the tree */ /* Don't add it again */ free(new_node); return t; }
}

Tree * delete(int i, Tree * t)
{
/* Deletes i from the tree if it's there. */
/* Return a pointer to the resulting tree. */ Tree * x; if (t==NULL) return NULL; t = splay(i,t); if (i == t->item) { /* found it */ if (t->left == NULL) x = t->right; else { x = splay(i, t->left); x->right = t->right; } size--; free(t); return x; } return t; /* It wasn't there */
}

int main(int argv, char *argc[])
{
/* A sample use of these functions.  Start with the empty tree, */
/* insert some stuff into it, and then delete it */ Tree * root; int i; root = NULL; /* the empty tree */ size = 0; for (i = 0; i < 1024; i++) { root = insert((541*i) & (1023), root); } printf("size = %d\n", size); for (i = 0; i < 1024; i++) { root = delete((541*i) & (1023), root); } printf("size = %d\n", size);
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
  
118
  
119
  
120
  
121
  
122
  
123
  
124
  
125
  
126
  
127
  
128
  
129
  
130
  
131
  
132
  
133
  
134
  
135
  
136
  
137
  
138
  
139
  
140
  
141
  
142
  
143
  
144
  
145
  
146
  
147
  
148
  
149
  
150
  
151
  
152
  
153
  
154
  
155
  
156
  
157
  
158
  
159
  
160
  
161
  
162
  
163
  
164
  
165
  
166
  
167
  
168
  
169
  
170
  
171
  
172
  
173
  
174
  
175
  
176
  
177
  
178
  
179
  
180
  
181
  
182
  
183
  
184
  
185
  
186
  
187
  
188
  
189
  
190
  
191
  
192
  
193
  
194
  
195
  
196
  
197
  
198
  
199
  
200
  
201
  
202
  
203
  
204
  
205
 

文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。

原文链接：lion-wu.blog.csdn.net/article/details/107376602