logo头像

待到风起时,扬帆济沧海

伸展树(SplayTree)

伸展树介绍

伸展树(Splay Tree)是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。
(01) 伸展树属于二叉查找树,即它具有和二叉查找树一样的性质:假设x为树中的任意一个结点,x节点包含关键字key,节点x的key值记为key[x]。如果y是x的左子树中的一个结点,则key[y] <= key[x];如果y是x的右子树的一个结点,则key[y] >= key[x]。
(02) 除了拥有二叉查找树的性质之外,伸展树还具有的一个特点是:当某个节点被访问时,伸展树会通过旋转使该节点成为树根。这样做的好处是,下次要访问该节点时,能够迅速的访问到该节点。

假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小,被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法,在每次查找之后对树进行重构,把被查找的条目搬移到离树根近一些的地方。伸展树应运而生,它是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。

相比于”二叉查找树”和”AVL树”,学习伸展树时需要重点关注是”伸展树的旋转算法”。

旋转算法讲解

将”键值为key的节点”旋转为根节点,并返回根节点。它的处理情况共包括:

  • (a)伸展树中存在”键值为key的节点”。
    • 将”键值为key的节点”旋转为根节点。
  • (b)伸展树中不存在”键值为key的节点”,并且key < tree.key。
    • b-1)”键值为key的节点”的前驱节点存在的话,将”键值为key的节点”的前驱节点旋转为根节点。
    • b-2)”键值为key的节点”的前驱节点存在的话,则意味着,key比树中任何键值都小,那么此时,将最小节点旋转为根节点。
  • (c) 伸展树中不存在”键值为key的节点”,并且key > tree.key
    • c-1)”键值为key的节点”的后继节点存在的话,将”键值为key的节点”的后继节点旋转为根节点。
    • c-2)”键值为key的节点”的后继节点不存在的话,则意味着,key比树中任何键值都大,那么此时,将最大节点旋转为根节点。

举个例子分别对a进行说明。
在下面的伸展树中查找10,共包括”右旋” –> “右链接” –> “组合”这3步。
1.jpg
第一步: 右旋
对应代码中的”rotate right”部分
2.jpg
第二步: 右链接
对应代码中的”link right”部分
3.jpg
第三步: 组合
对应代码中的”assemble”部分
4.jpg

完整源码

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
package tree

import "fmt"

type SplayTreeNode struct {
Value int
Left, Right *SplayTreeNode
}

type SplayTree struct {
Root *SplayTreeNode
}

/**
前序遍历
*/
func (this *SplayTree) PreOrder(node *SplayTreeNode) {
if this.Root != nil {
fmt.Print(node.Value, " ")
this.PreOrder(node.Left)
this.PreOrder(node.Right)
}
}

/**
中序遍历
*/
func (this *SplayTree) InOrder(node *SplayTreeNode) {
if this.Root != nil {
this.PreOrder(node.Left)
fmt.Print(node.Value, " ")
this.PreOrder(node.Right)
}
}

/**
后续遍历
*/
func (this *SplayTree) PostOrder(node *SplayTreeNode) {
if this.Root != nil {
this.PreOrder(node.Left)
this.PreOrder(node.Right)
fmt.Print(node.Value, " ")
}
}

/**
旋转key对应的节点为根节点,并返回根节点。
*
* 注意:
* (a):伸展树中存在"键值为key的节点"。
* 将"键值为key的节点"旋转为根节点。
* (b):伸展树中不存在"键值为key的节点",并且key < tree.key。
* b-1 "键值为key的节点"的前驱节点存在的话,将"键值为key的节点"的前驱节点旋转为根节点。
* b-2 "键值为key的节点"的前驱节点存在的话,则意味着,key比树中任何键值都小,那么此时,将最小节点旋转为根节点。
* (c):伸展树中不存在"键值为key的节点",并且key > tree.key。
* c-1 "键值为key的节点"的后继节点存在的话,将"键值为key的节点"的后继节点旋转为根节点。
* c-2 "键值为key的节点"的后继节点不存在的话,则意味着,key比树中任何键值都大,那么此时,将最大节点旋转为根节点。
*/
func (this *SplayTree) splay(tree *SplayTreeNode, data int) *SplayTreeNode {
if tree == nil {
return tree
}
var n, l, r, c *SplayTreeNode
l, r = n, n
for {
if data < tree.Value {
if tree.Left == nil {
break
}
if data < tree.Left.Value {
c = tree.Left /* rotate right */
tree.Left = c.Right
c.Right = tree
tree = c
if tree.Left == nil {
break
}
}
r.Left = tree /* link right */
r = tree
tree = tree.Left
} else if data > tree.Value {
if tree.Right == nil {
break
}
if data > tree.Right.Value {
c = tree.Right /* rotate left */
tree.Right = c.Left
c.Left = tree
tree = c
if tree.Right == nil {
break
}
}
l.Right = tree /* link left */
l = tree
tree = tree.Right
} else {
break
}
}
l.Right = tree.Left /* assemble */
r.Left = tree.Right
tree.Left = n.Right
tree.Right = n.Left
return tree
}

/**
递归查找
*/
func (this *SplayTree) Search(tree *SplayTreeNode, data int) *SplayTreeNode {
if tree == nil {
return tree
}
if data < tree.Value {
return this.Search(tree.Left, data)
} else if data > tree.Value {
return this.Search(tree.Right, data)
} else {
return tree
}
}
func (this *SplayTree) FindMin(tree *SplayTreeNode) *SplayTreeNode {
if tree == nil {
return nil
}
for tree.Left != nil {
tree = tree.Left
}
return tree
}
func (this *SplayTree) FindMax(tree *SplayTreeNode) *SplayTreeNode {
if tree == nil {
return nil
}
for tree.Right != nil {
tree = tree.Right
}
return tree
}

/*
* 将结点插入到伸展树中,并返回根节点
*
* 参数说明:
* tree 伸展树的
* addNode 插入的结点
*/
func (this *SplayTree) insert(tree *SplayTreeNode, addNode *SplayTreeNode) *SplayTreeNode {

var y *SplayTreeNode
x := tree
for x != nil {
y = x
if addNode.Value < x.Value {
x = x.Left
} else if addNode.Value > x.Value {
x = x.Right
} else {
fmt.Errorf("插入相同的节点(%d)\n", addNode.Value)
addNode = nil
return tree
}
}
if y == nil {
tree = addNode
} else {
if addNode.Value < y.Value {
y.Left = addNode
} else {
y.Right = addNode
}
}
return tree
}
func (this *SplayTree) Add(data int) {
z := &SplayTreeNode{Value: data}
// 插入节点
this.Root = this.insert(this.Root, z)
// 将节点(key)旋转为根节点
this.Root = this.splay(this.Root, data)
}

func (this *SplayTree) Del(data int) {
this.Root = this.remove(this.Root, data)
}

func (this *SplayTree) remove(tree *SplayTreeNode, data int) *SplayTreeNode {
var x *SplayTreeNode
if tree == nil {
return nil
}
// 查找键值为key的节点,找不到的话直接返回。
if this.Search(tree, data) == nil {
return tree
}
// 将key对应的节点旋转为根节点。
tree = this.splay(tree, data)
if tree.Left != nil {
// 将"tree的前驱节点"旋转为根节点
x = this.splay(tree.Left, data)
// 移除tree节点
x.Right = tree.Right
} else {
x = tree.Right
}
tree = nil
return x

}

func (this *SplayTree) Display() {
if this.Root != nil {
this.print(this.Root, this.Root.Value, 0)
}
}

/**
递归打印
key -- 节点的值
direction -- 0,根节点
-1,父节点的坐孩子
1,父节点的右孩子
*/
func (this *SplayTree) print(tree *SplayTreeNode, key int, direction int) {
if tree != nil {
if direction == 0 {
fmt.Printf("%2d is root\n", tree.Value)
} else {
var post string
if direction == 1 {
post = "right"
} else {
post = "left"
}
fmt.Printf("%2d is %2d's %6s child\n", tree.Value, key, post)
}
this.print(tree.Left, tree.Value, -1)
this.print(tree.Right, tree.Value, 1)
}
}

评论系统未开启,无法评论!