伸展树
伸展树（英语：Splay Tree）是一种能够自我平衡的二叉查找树，它能在均摊 O(log n) 的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。
它是由丹尼尔·斯立特（Daniel Sleator）和罗伯特·塔扬在1985年发明的。
核心思想
考虑到局部性原理（刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问），为了使整个查找时间更小，被查频率高的那些节点应当经常处于靠近树根的位置。
ps: 这个思想实际上非常的简单，也非常的实用。我们以前实现的 LFU 的思想是类似的。
操作方案
每次查找节点之后对树进行重构，把被查找的节点搬移到树根，这种自调整形式的二叉查找树就是伸展树。每次对伸展树进行操作后，它均会通过旋转的方法把被访问节点旋转到树根的位置。
它的优势在于不需要记录用于平衡树的冗余信息。
为了将当前被访问节点旋转到树根，我们通常将节点自底向上旋转，直至该节点成为树根为止。
“旋转”的巧妙之处就是在不打乱数列中数据大小关系（指中序遍历结果是全序的）情况下，所有基本操作的平摊复杂度仍为O（log n）。
优缺点
优点
伸展树的自我平衡使其拥有良好的性能，因为频繁访问的节点会被移动到更靠近根节点，进而获得更快的访问速度。
可靠的性能——它的平均效率不输于其他平衡树。
存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息，相对于其他平衡树，内存占用要小。
编程实现起来，也比红黑树要容易很多。
缺点
伸展树最显著的缺点是它有可能会变成一条链。
例如，在以非递减顺序访问全部n个之后就会出现这种情况。此时树的高度对应于最坏情况的时间效率，操作的实际时间效率可能很低。
然而均摊的最坏情况是对数级的——O(log n)。
即使以“只读”方式（例如通过查找操作）访问伸展树，其结构也可能会发生变化。
这使得伸展树在多线程环境下会变得很复杂。具体而言，如果允许多个线程同时执行查找操作，则需要额外的维护和操作。这也使得它们不适合在纯粹的函数式编程中普遍使用，尽管用于实现优先级队列的方式不多。
操作
伸展(splay)
当一个节点x被访问过后，伸展操作会将x移动到根节点。
为了进行伸展操作，我们会进行一系列的旋转，每次旋转会使x离根节点更近。
通过每次访问节点后的伸展操作，最近访问的节点都会离根节点更近，且伸展树也会大致平衡，这样我们就可以得到期望均摊时间复杂度的下界——均摊 O(log n)。
每次旋转操作由三个因素决定：
-
x 是其父节点p的左儿子还是右儿子；
-
p 是否为根；
-
p 是其父节点g（x的祖父节点）的左儿子还是右儿子。
在每次旋转操作后，设置g的儿子为x是很重要的。
如果g为空，那么x显然就是根节点了。
共有三种旋转操作，每种都有左旋（Zig）和右旋（Zag）两种情况。
为了简单起见，对每种旋转操作只展示一种情况。
这些旋转操作是：
Zig：当p为根节点时进行。Zig通常只在伸展操作的最后一步进行。
Zig-zig和Zag-zag：当p不为根节点且x和p都为左儿子或都为右儿子时进行。
下图为x和p都为左儿子时的情况（即Zig-zig），需先将p右旋到g的位置，再将x右旋到p的位置。
Zig-zag和Zag-zig：当p不为根节点且x为左儿子而p为右儿子时进行，反之亦然。
下图为前述情况（即Zig-zag），需先将x左旋到p到的位置，再将x右旋到g的位置。
连接(join)
给出两棵树S和T，且S的所有元素都比T的元素要小。
下面的步骤可以把它们连接成一棵树：
-
伸展S中最大的节点。现在这个节点变为S的根节点，且没有右儿子。
-
令T的根节点变为其右儿子。
分割(split)
给出一棵树和一个元素x，返回两棵树：一棵中所有的元素均小于等于x，另一棵中所有的元素大于x。下面的步骤可以完成这个操作：
-
伸展x。这样的话x成为了这棵树的根所以它的左子树包含了所有比x小的元素，右子树包含了所有比x大的元素。
-
把 x 的右子树从树中分割出来。
插入(insert)
插入操作是一个比较复杂的过程，具体步骤如下: 我们假定要插入的值为k。
-
如果当前树为空，则直接插入根。
-
如果当前节点的权值等于k则增加当前节点的大小并更新节点和父亲的信息，将当前节点进行splay操作。
-
否则按照二叉查找树的性质向下找，找到空节点就插入即可，当然在最后还要进行一次splay操作。
C 语言实现图解
节点结构定义
[c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15typedef struct SplayNode *Tree;
typedef int ElementType;
struct SplayNode
{
Tree parent; //该结点的父节点，方便操作
ElementType val; //结点值
Tree lchild;
Tree rchild;
SplayNode(int val=0) //默认构造函数
{
parent=NULL;
lchild=rchild=NULL;
this->val=val;
}
};
旋转操作
单 R 型
什么叫单R型呢，在上图中，我们查找的元素是9,其父节点是7，并且7是根结点，查找结点是其父节点的右孩子，而且把9变成根结点只需一次左旋转即可（即将9提升一层），这样的情况我们叫单R型，经过一次左旋转后结点9替代了原来的根结点7，变成新的根结点（注意这里因为图简单，9最终变成了根结点，在树复杂的情况，一般不会一次就变成了根结点，但肯定会变成原子树的根，这也就是程序中说的当前子树中的新根）。
为了后面更加轻松，这里把单左旋代码贴出，可以对比图示和代码分析分析，便于理解
[c++]
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//单左旋操作
//参数:根，旋转结点(旋转中心)
//返回:当前子树中的新根
Tree left_single_rotate(Tree &root,Tree node)
{
if (node==NULL)
return NULL;
Tree parent=node->parent; //其父结点
Tree grandparent=parent->parent; //其祖父结点
parent->rchild=node->lchild; //设置其父节点的右孩子
if (node->lchild) //如果有左孩子则更新node结点左孩子的父节点信息
node->lchild->parent=parent;
node->lchild=parent; //更新node结点的左孩子信息
parent->parent=node; //更新原父节点的信息
node->parent=grandparent;
if (grandparent) //更新祖父孩子结点的信息
{
if (grandparent->lchild==parent)
grandparent->lchild=node;
else
grandparent->rchild=node;
}
else //不存在祖父节点，则原父节点为根，那么旋转后node为根
root=node;
return node;
}
单 L 型
单L型和单R型是对称的，也就是说查找结点3是其父节点的左子树，并且其父节点是根结点，这样一次右旋转后3就是根结点了。
[c++]
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//单右旋操作
//参数:根，旋转结点(旋转中心)
//返回:当前子树中的新根
Tree right_single_rotate(Tree &root,Tree node)
{
if (node==NULL)
return NULL;
Tree parent,grandparent;
parent=node->parent;
grandparent=parent->parent;
parent->lchild=node->rchild;
if (node->rchild)
node->rchild->parent=parent;
node->rchild=parent;
parent->parent=node;
node->parent=grandparent;
if (grandparent)
{
if (grandparent->lchild==parent)
grandparent->lchild=node;
else
grandparent->rchild=node;
}
else
root=node;
return node;
}
RR 型
所谓RR型，简单点说就是两次R型，两次左旋转，这种情况是查找结点有父节点，同时也有祖父结点，并且三则在同右侧，这种就是RR型，针对这种情况，先把查找结点的父节点旋转一次，即提升一层，然后再以查找结点再次旋转，这样查找结点就到了根结点了，都是左旋转，只是旋转对象不一样罢了。
[c++]
1
2
3
4
5
6
7//两次单左旋操作
//参数：根，最后将变成子树根结点的结点
void left_double_rotate(Tree &root,Tree node)
{
left_single_rotate(root,node->parent);
left_single_rotate(root,node);
}
LL 型
[c++]
1
2
3
4
5
6
7//两次单右旋操作
//参数：根，最后将变成子树根结点的结点
void right_double_rotate(Tree &root,Tree node)
{
right_single_rotate(root,node->parent); //先提升其父节点
right_single_rotate(root,node); //最后提升自己
}
LL型和RR型是对称的，经过一次双右旋结果如上图，但是这样就结束了吗？
回想一下，伸展树的旋转操作目的是干什么，不是为了把查找结点推送至树根么，是的，但是现在这种情况结点9还不是树根，但是这种情况不是我们前面讲过的单R型吗？
所以再来次左旋就可以了，也就是下面这个样子：
RL 型
[c++]
1
2
3
4
5
6
7//双旋操作（RL型），于AVL树类似
//参数：根，最后将变成子树根结点的结点
void RL_rotate(Tree&root,Tree node)
{
right_single_rotate(root,node); //先右后左
left_single_rotate(root,node);
}
这个和AVL树中的RL是一样的，旋转完成后，还需要一步左旋：
LR 型
[c++]
1
2
3
4
5
6
7//双旋操作（LR型），于AVL树类似
//参数：根，最后将变成子树根结点的结点
void LR_rotate(Tree &root,Tree node)
{
left_single_rotate(root,node); //先左
right_single_rotate(root,node);//后右
}
OK，到这里伸展树的几种情况就介绍完了，怎么这么多旋转方式，其实大可不必这样，这个只是我学习的时候自己总结的，和网上的也打不相同，主要是自己理解了它的旋转方式后，就好了，至于命名这些都影响不大，我这里把它们分为这几种的方式，主要是为了封装成函数，方便我的调用，这样逻辑更清楚一下，自己懂了以后就可以根据自己理解来组织代码了。
伸展树的操作
伸展树的操作和AVL树一样无非就是查，插，删，下面我们分别来介绍它们。
(1) 先看看查找函数search：
[c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16//查找函数，带调整功能
//参数:根结点，需要查找的val
//返回:true or false
bool search(Tree &root,ElementType val)
{
Tree parent=NULL;
Tree *temp=NULL;
temp=search_val(root,val, parent);
if (*temp && *temp!=root)
{
SplayTree(root,*temp);
return true;
}
return false;
}
查找函数中里面有另一个具体的查找函数，我们先不管它，先梳理逻辑，首先我们通过内部的查找函数，查找值为val的结点，找到后返回结点给temp，如果查找成功，并且当前结点不是根结点，那么我们将进行树的调整，将结点temp推到树根，否则直接退出，这就是search的功能，简单明了。
[c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14//具体的查找函数
//参数:根，需要查找的val,父节点指针
//成功:返回其结点
//失败：返回其引用,方便后面的插入操作
Tree *search_val(Tree &root,ElementType val,Tree &parent)
{
if (root==NULL)
return &root;
if (root->val>val)
return search_val(root->lchild,val,parent=root);
else if(root->val<val)
return search_val(root->rchild,val,parent=root);
return &root;
}
这里我们有必要介绍一下内部的查找函数，因为这是一个通用的接口，后面都会用到它，这个查找函数，如果查找成功则返回结点的引用，否则返回它该插入地方的引用，也就是其最后的parent的某个孩子，parent是查找成功或失败结点的父节点，也是引用类型。
OK，这就是我们的查找函数，这里没有强化它的查找功能，只是方便我们后面的插入和删除工作。
插入
[c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19//插入函数
//参数：根，需要插入的val
//返回:true or false
bool insert(Tree &root,ElementType val)
{
Tree *temp=NULL;
Tree parent=NULL;
//先查找，如果成功则无需插入，否则返回该结点的引用。
temp=search_val(root,val,parent);
if (*temp==NULL) //需要插入数据
{
Tree node=new SplayNode(val);
*temp=node; //因为是引用型，所以这里直接赋值，简化了很多了。
node->parent=parent; //设置父节点。
return true;
}
return false;
}
可以看到这个插入函数也是很短的，注意观察，里面有我们熟悉的东西，没错就是前面所讲的内部查找函数，这里对插入结点，我们先进行查找，如果查找成功就不进行插入，否则返回该插入地址的引用，这样我们直接让 *temp=node，便完成了插入工作，简化了很多工作，然后设置父节点信息，插入成功。
伸展
当我们查找一个val后，我们需要对树进行伸展，下面就是我们的伸展函数
[c++]
1
2
3
4
5
6
7
8
9
10//Splay调整操作
void SplayTree(Tree &root,Tree node)
{
while (root->lchild!=node && root->rchild!=node && root!=node) //当前结点不是根，或者不是其根的左右孩子，则根据情况进行旋转操作
up(root, node);
if (root->lchild==node) //当前结点为根的左孩子，只需进行一次单右旋
root=right_single_rotate(root, node);
else if(root->rchild==node) //当前结点为根的右孩子，只需进行一次单左旋
root=left_single_rotate(root, node);
}
可以看到，里面有个up函数，在这个函数外，还有单独的if判断结构，这两个if就是判断特殊情况的，也就是我们只需进行一个单旋便可以晋级为根结点的情况，这个很简单，结合一下图就可以看出来了。
OK，看看我们的up函数
[c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18//根据情况，选择不同的旋转方式
void up(Tree &root,Tree node)
{
Tree parent,grandparent;
int i,j;
parent=node->parent;
grandparent=parent->parent;
i=grandparent->lchild==parent ? -1:1;
j=parent->lchild==node ?-1:1;
if (i==-1 && j==-1) //AVL树中的LL型
right_double_rotate(root, node);
else if(i==-1 && j==1) //AVL树中的LR型
LR_rotate(root, node);
else if(i==1 && j==-1) //AVL树中的RL型
RL_rotate(root, node);
else //AVL树中的RR型
left_double_rotate(root, node);
}
up顾名思义就是往上，也就是把查找结点往上推送，在这个函数里面我们判断了旋转类型，是LL型，还是RR型，还是LR型，亦或是RL型，然后再调用我们前面展示过的旋转函数。
只需旋转函数最好结合图然后再看代码，这样很容易理解，不要只看代码。
到这里我们的查找和插入，以及伸展过程我们都展示了，这里很重要一个函数就是查找函数，还有就是几种旋转方式。
删除
[c++]
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//删除操作
void remove(Tree &root,ElementType val)
{
Tree parent=NULL;
Tree *temp;
Tree *replace;
Tree replace2;
temp=search_val(root,val, parent); //先进行查找操作
if(*temp) //如果查找到了
{
if (*temp!=root) //判断是否是根结点，不是根结点，则需要调整至根结点
SplayTree(root, *temp);
//调至根结点或者本来就是根结点后进行删除，先查看是否有替代元素
if (root->rchild)
{
//有替代元素
replace=Find_Min(root->rchild); //找到替换元素
root->val=(*replace)->val; //替换
if ((*replace)->lchild==NULL) //左子树为空
{
replace2=*replace;
*replace=(*replace)->rchild; //重接其右孩子
delete replace2;
}
else if((*replace)->rchild==NULL) //右子树为空
{
replace2=*replace;
*replace=(*replace)->lchild; //重接其左孩子
delete replace2;
}
}
else
{
//无替代元素，则根直接移向左子树，不管左子树是否为空都可以处理
replace2=root;
root=root->lchild;
delete replace2;
}
}
}
在删除函数中，我们首先进行了查找，查找失败就退出，查找成功后，我们便把它推送到根结点，然后再用我们BST删除方式，找替代元素，这样化繁为简，只是这里统一采用引用方式，要简单很多。
下面是这是我们的熟悉的找替代元素的函数:
[c++]
1
2
3
4
5
6
7
8//操作当前子树的最小结点
//返回:其最小结点的引用
Tree *Find_Min(Tree &root)
{
if (root->lchild)
return Find_Min(root->lchild);
return &root;
}
OK，到这里我们的伸展树就介绍完了，在这里可以看到我们伸展树里面的函数和AVL树里面的函数差别很大，在AVL树里面，我们即采用了引用(部分),同时又可以通过返回值来设置，再加上手生，写得有点杂乱，这里的伸展树，我就统一采用引用方式，能不返回值就返回值，这样可以简化很多操作，加之伸展树本来就比AVL树简单，不同判断平衡因子，因此写起来就更加简单了。
完整的 C 实现
[c++]
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
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef struct SplayNode *Tree;
typedef int ElementType;
struct SplayNode
{
Tree parent; //该结点的父节点，方便操作
ElementType val; //结点值
Tree lchild;
Tree rchild;
SplayNode(int val=0) //默认构造函数
{
parent=NULL;
lchild=rchild=NULL;
this->val=val;
}
};
bool search(Tree &,ElementType);
Tree *search_val(Tree&,ElementType,Tree&);
bool insert(Tree &,ElementType);
Tree left_single_rotate(Tree&,Tree);
Tree right_single_rotate(Tree &,Tree );
void LR_rotate(Tree&,Tree );
void RL_rotate(Tree&,Tree );
void right_double_rotate(Tree&,Tree );
void left_double_rotate(Tree&,Tree );
void SplayTree(Tree &,Tree);
void up(Tree &,Tree );
Tree *Find_Min(Tree &);
void remove(Tree &,ElementType);
//查找函数，带调整功能
//参数:根结点，需要查找的val
//返回:true or false
bool search(Tree &root,ElementType val)
{
Tree parent=NULL;
Tree *temp=NULL;
temp=search_val(root,val, parent);
if (*temp && *temp!=root)
{
SplayTree(root,*temp);
return true;
}
return false;
}
//具体的查找函数
//参数:根，需要查找的val,父节点指针
//成功:返回其结点
//失败：返回其引用,方便后面的插入操作
Tree *search_val(Tree &root,ElementType val,Tree &parent)
{
if (root==NULL)
return &root;
if (root->val>val)
return search_val(root->lchild,val,parent=root);
else if(root->val<val)
return search_val(root->rchild,val,parent=root);
return &root;
}
//插入函数
//参数：根，需要插入的val
//返回:true or false
bool insert(Tree &root,ElementType val)
{
Tree *temp=NULL;
Tree parent=NULL;
//先查找，如果成功则无需插入，否则返回该结点的引用。
temp=search_val(root,val,parent);
if (*temp==NULL) //需要插入数据
{
Tree node=new SplayNode(val);
*temp=node; //因为是引用型，所以这里直接赋值，简化了很多了。
node->parent=parent; //设置父节点。
return true;
}
return false;
}
//单左旋操作
//参数:根，旋转结点(旋转中心)
//返回:当前子树中的新根
Tree left_single_rotate(Tree &root,Tree node)
{
if (node==NULL)
return NULL;
Tree parent=node->parent; //其父结点
Tree grandparent=parent->parent; //其祖父结点
parent->rchild=node->lchild; //设置其父节点的右孩子
if (node->lchild) //如果有左孩子则更新node结点左孩子的父节点信息
node->lchild->parent=parent;
node->lchild=parent; //更新node结点的左孩子信息
parent->parent=node; //更新原父节点的信息
node->parent=grandparent;
if (grandparent) //更新祖父孩子结点的信息
{
if (grandparent->lchild==parent)
grandparent->lchild=node;
else
grandparent->rchild=node;
}
else //不存在祖父节点，则原父节点为根，那么旋转后node为根
root=node;
return node;
}
//单右旋操作
//参数:根，旋转结点(旋转中心)
//返回:当前子树中的新根
Tree right_single_rotate(Tree &root,Tree node)
{
if (node==NULL)
return NULL;
Tree parent,grandparent;
parent=node->parent;
grandparent=parent->parent;
parent->lchild=node->rchild;
if (node->rchild)
node->rchild->parent=parent;
node->rchild=parent;
parent->parent=node;
node->parent=grandparent;
if (grandparent)
{
if (grandparent->lchild==parent)
grandparent->lchild=node;
else
grandparent->rchild=node;
}
else
root=node;
return node;
}
//双旋操作（LR型），于AVL树类似
//参数：根，最后将变成子树根结点的结点
void LR_rotate(Tree &root,Tree node)
{
left_single_rotate(root,node); //先左
right_single_rotate(root,node);//后右
}
//双旋操作（RL型），于AVL树类似
//参数：根，最后将变成子树根结点的结点
void RL_rotate(Tree&root,Tree node)
{
right_single_rotate(root,node); //先右后左
left_single_rotate(root,node);
}
//两次单右旋操作
//参数：根，最后将变成子树根结点的结点
void right_double_rotate(Tree &root,Tree node)
{
right_single_rotate(root,node->parent); //先提升其父节点
right_single_rotate(root,node); //最后提升自己
}
//两次单左旋操作
//参数：根，最后将变成子树根结点的结点
void left_double_rotate(Tree &root,Tree node)
{
left_single_rotate(root,node->parent);
left_single_rotate(root,node);
}
//Splay调整操作
void SplayTree(Tree &root,Tree node)
{
while (root->lchild!=node && root->rchild!=node && root!=node) //当前结点不是根，或者不是其根的左右孩子，则根据情况进行旋转操作
up(root, node);
if (root->lchild==node) //当前结点为根的左孩子，只需进行一次单右旋
root=right_single_rotate(root, node);
else if(root->rchild==node) //当前结点为根的右孩子，只需进行一次单左旋
root=left_single_rotate(root, node);
}
//根据情况，选择不同的旋转方式
void up(Tree &root,Tree node)
{
Tree parent,grandparent;
int i,j;
parent=node->parent;
grandparent=parent->parent;
i=grandparent->lchild==parent ? -1:1;
j=parent->lchild==node ?-1:1;
if (i==-1 && j==-1) //AVL树中的LL型
right_double_rotate(root, node);
else if(i==-1 && j==1) //AVL树中的LR型
LR_rotate(root, node);
else if(i==1 && j==-1) //AVL树中的RL型
RL_rotate(root, node);
else //AVL树中的RR型
left_double_rotate(root, node);
}
//操作当前子树的最小结点
//返回:其最小结点的引用
Tree *Find_Min(Tree &root)
{
if (root->lchild)
return Find_Min(root->lchild);
return &root;
}
//删除操作
void remove(Tree &root,ElementType val)
{
Tree parent=NULL;
Tree *temp;
Tree *replace;
Tree replace2;
temp=search_val(root,val, parent); //先进行查找操作
if(*temp) //如果查找到了
{
if (*temp!=root) //判断是否是根结点，不是根结点，则需要调整至根结点
SplayTree(root, *temp);
//调制根结点或者本来就是根结点后进行删除，先查看是否有替代元素
if (root->rchild)
{
//有替代元素
replace=Find_Min(root->rchild); //找到替换元素
root->val=(*replace)->val; //替换
if ((*replace)->lchild==NULL) //左子树为空
{
replace2=*replace;
*replace=(*replace)->rchild; //重接其右孩子
delete replace2;
}
else if((*replace)->rchild==NULL) //右子树为空
{
replace2=*replace;
*replace=(*replace)->lchild; //重接其左孩子
delete replace2;
}
}
else
{
//无替代元素，则根直接移向左子树，不管左子树是否为空都可以处理
replace2=root;
root=root->lchild;
delete replace2;
}
}
}
//前序
void PreOrder(Tree root)
{
if (root==NULL)
return;
printf("%d ",root->val);
PreOrder(root->lchild);
PreOrder(root->rchild);
}
//中序
void InOrder(Tree root)
{
if (root==NULL)
return;
InOrder(root->lchild);
printf("%d ",root->val);
InOrder(root->rchild);
}
int main()
{
Tree root=NULL;
insert(root, 11);
insert(root, 7);
insert(root, 18);
insert(root, 3);
insert(root, 9);
insert(root, 16);
insert(root, 26);
insert(root, 14);
insert(root, 15);
search(root,14);
printf("查找14:\n");
printf("前序:");
PreOrder(root);
printf("\n");
printf("中序:");
InOrder(root);
printf("\n");
// remove(root,16);
// remove(root,26);
// remove(root,11);
remove(root,16);
printf("删除16:\n");
printf("前序:");
PreOrder(root);
printf("\n");
printf("中序:");
InOrder(root);
printf("\n");
return 0;
}
java 实现版本
[java]
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
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227public class SplayTree<T extends Comparable<T>> {
class SplayTreeNode<T extends Comparable<T>>{
SplayTreeNode<T> left;
SplayTreeNode<T> right;
T data;
SplayTreeNode(SplayTreeNode<T> left, SplayTreeNode<T> right, T data){
this.left = left;
this.right = right;
this.data = data;
}
SplayTreeNode(){
this(null, null, null);
}
SplayTreeNode(T data){
this(null, null, data);
}
}
private SplayTreeNode<T> root;
private Comparator<T> cmp;
public SplayTree(){
root = null;
}
public SplayTree(Comparator<T> cmp){
this.cmp = cmp;
}
private int mCompare(T a, T b){
if (cmp != null){
return cmp.compare(a,b);
}
return a.compareTo(b);
}
public SplayTreeNode<T> insert(T data){
root = insert(root, data);
//进行伸展
root = splay(root, data);
return root;
}
private SplayTreeNode<T> insert(SplayTreeNode<T> tree, T data){
if (tree == null){
return new SplayTreeNode<T>(data);
}
int result = mCompare(data, tree.data);
if (result < 0){
tree.left = insert(tree.left, data);
} else if (result > 0){
tree.right = insert(tree.right, data);
} else {
System.out.println("已经存在该值");
return null;
}
return tree;
}
private SplayTreeNode<T> insert(SplayTreeNode<T> rootTree, SplayTreeNode<T> tempNode){
if (rootTree == null){
return tempNode;
} else {
int result = mCompare(tempNode.data, rootTree.data);
if (result < 0){
rootTree.left = insert(rootTree.left, tempNode);
} else if (result > 0){
rootTree.right = insert(rootTree.right, tempNode);
}
}
return rootTree;
}
public SplayTreeNode<T> search(T data){
return search(root, data);
}
private SplayTreeNode<T> search(SplayTreeNode<T> tree, T data){
if (tree == null){
return null;
}
int result = mCompare(data, tree.data);
if (result < 0){
return search(tree.left, data);
} else if (result > 0){
return search(tree.right, data);
} else {
//找到目标节点，进行伸展，使其成为根节点
root = splay(root, data);
return tree;
}
}
public T getRoot(){
return root != null ? root.data : null;
}
public T findMax(){
return findMax(root).data;
}
private SplayTreeNode<T> findMax(SplayTreeNode<T> tree){
if (tree == null){
return null;
}
while (tree.right != null){
tree = tree.right;
}
return tree;
}
/**
* 删除时，进行伸展：
* a. 找到删除的节点
* b. 对删除的节点进行旋转，使其成为根节点
* c. 删除该节点后，问题是如何将左右子树进行拼接？
* (1) 若左子树不为空，则找到左子树中的最大值，因为左子树的最大值节点没有右子树
* (1.1) 将选中的最大值节点进行旋转，使其成为根节点
* (1.2) 将原来的右子树拼接过来
* (2) 若左子树为空，则右子树直接成为完整的树
* @param data
* @return
*/
public SplayTreeNode<T> remove(T data){
SplayTreeNode<T> newRoot, removeRoot;
if (root == null){
return null;
}
//找到要删除的节点
removeRoot = search(root, data);
//若没找到，则返回空
if (removeRoot == null){
return null;
}
//对要删除的节点旋转成为根节点
root = splay(root, data);
//左边不为空
if (root.left != null){
//找到左子树的最大节点值作为根节点，因为其没有右孩子存在
newRoot = splay(root.left, findMax(root.left).data);
//右子树直接赋值
newRoot.right = root.right;
}
//否则直接赋值右子树
else {
newRoot = root.right;
}
//更新树
root = newRoot;
//返回删除的节点
return removeRoot;
}
/**
* 使用自底向上的方法实现伸展
* @param tree 节点
* @param data 目标值
* @return 返回目标节点
*/
public SplayTreeNode<T> splay(SplayTreeNode<T> tree, T data){
//若树为空，则返回
if (tree == null){
return null;
}
//进行比较
int result = mCompare(data, tree.data);
//小于0，说明目标节点在左子树
if (result < 0){
//在左子树中进行查找
tree.left = splay(tree.left, data);
//表示找到了目标节点，tree为目标节点的父节点，进行右旋
tree = rotationRight(tree);
}
// 大于0，说明目标节点在右子树
else if (result > 0){
//在右子树树种进行查找
tree.right = splay(tree.right, data);
//表示找到了目标节点，tree为目标节点的父节点，进行左旋
tree = rotationLeft(tree);
} else {
//找到目标节点，返回
return tree;
}
return tree;
}
/**
* 进行左旋转
* @param root 传入目标节点的父节点
* @return 返回以目标节点为根节点的部分树
*/
private SplayTreeNode<T> rotationLeft(SplayTreeNode<T> root) {
SplayTreeNode<T> newRoot = root.right;//A
root.right = newRoot.left;//B
newRoot.left = root;//C
return newRoot;
}
/**
* 进行右旋
* @param tree
* @return
*/
private SplayTreeNode<T> rotationRight(SplayTreeNode<T> tree) {
SplayTreeNode<T> newRoot = tree.left;//A
tree.left = newRoot.right;//B
newRoot.right = tree;//C
return newRoot;
}
public void inOrder(){
inOrder(root);
}
private void inOrder(SplayTreeNode<T> tree){
if (tree != null){
inOrder(tree.left);
System.out.print(tree.data + " ");
inOrder(tree.right);
}
}
}
测试代码
[java]
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
31public class SplayTreeTest {
public static void main(String[] args){
int arr[] = {8,4,30,2,6,9,38,1,3,5,7,33,39,31,34};
SplayTree<Integer> splayTree = new SplayTree<Integer>();
//进行插入
for (int anArr : arr) {
splayTree.insert(anArr);
}
//打印树
System.out.println("root:" + splayTree.getRoot());
printArr(splayTree);
//进行搜索节点33
splayTree.search(33);
System.out.println("root:" + splayTree.getRoot());
printArr(splayTree);
//进行删除节点8
splayTree.remove(8);
System.out.println("root:" + splayTree.getRoot());
printArr(splayTree);
}
private static void printArr(SplayTree<Integer> splayTree){
System.out.println("当前树的中序遍历如下：");
splayTree.inOrder();
System.out.println();
}
}
