8
/ \
/ \
/ \
/ \
/ \
/ \
4 12
/ \ / \
/ \ / \
/ \ / \
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 15
Following the search for 15, 15
becomes the splay node
q, and
p = 14 and gp = 12. An RR
rotation is done to get the following tree:
8
/ \
/ \
/ \
/ \
/ \
/ \
4 15
/ \ /
/ \ /
/ \ /
2 6 14
/ \ / \ /
1 3 5 7 12
/ \
10 13
/ \
9 11
The splay node is now at level 2, and a type R
rotation is done to bring the splay node to level 1.
The result is
15
/
8
/ \
/ \
/ \
/ \
/ \
/ \
4 14
/ \ /
/ \ /
/ \ /
2 6 12
/ \ / \ / \
1 3 5 7 10 13
/ \
9 11
Following the search for 14 the splay node is
14. An LR rotation is done to make the splay node
the root. The new tree is
14
/ \
8 15
/ \
/ \
/ \
/ \
/ \
/ \
4 12
/ \ / \
/ \ / \
/ \ / \
2 6 10 13
/ \ / \ / \
1 3 5 7 9 11
Following the search for 13 the splay node is
13. An RR rotation is first done to get the following tree.
14
/ \
13 15
/
12
/
8
/ \
/ \
/ \
/ \
4 10
/ \ / \
/ \ / \
/ \ / \
2 6 9 11
/ \ / \
1 3 5 7
Next a type R rotation is done to make the splay node the root.
The resulting tree is
13
/ \
12 14
/ \
8 15
/ \
/ \
/ \
/ \
4 10
/ \ / \
/ \ / \
/ \ / \
2 6 9 11
/ \ / \
1 3 5 7
Following the search for 12 a type L rotation
is done to make the splay node the root. The resulting tree is
12
/ \
/ \
/ \
8 13
/ \ \
/ \ \
/ \ \
/ \ \
4 10 14
/ \ / \ \
/ \ / \ \
/ \ / \ \
2 6 9 11 15
/ \ / \
1 3 5 7
After the search for 11 an RR rotation
is first done to get the tree
12
/ \
11 13
/ \
10 14
/ \
8 15
/ \
4 9
/ \
/ \
/ \
/ \
2 6
/ \ / \
1 3 5 7
Next a type L rotation is done and the splay node becomes the root.
The new tree is
11
/ \
10 12
/ \
8 13
/ \ \
4 9 14
/ \ \
/ \ \
/ \ \
/ \ \
2 6 15
/ \ / \
1 3 5 7
After the search for 10 a type L rotation
is done to make the splay node the root. The resulting tree is
10
/ \
8 11
/ \ \
4 9 12
/ \ \
/ \ \
/ \ \
/ \ \
2 6 13
/ \ / \ \
1 3 5 7 14
\
15
After the search for 9 a type LR rotation
is done to make the splay node the root. The resulting tree is
9
/ \
8 10
/ \
4 11
/ \ \
/ \ \
/ \ \
/ \ \
2 6 12
/ \ / \ \
1 3 5 7 13
\
14
\
15
The search for 8 is followed by a type L rotation
to make the splay node the root. The resulting tree is
8
/ \
4 9
/ \ \
/ \ \
/ \ \
/ \ \
2 6 10
/ \ / \ \
1 3 5 7 11
\
12
\
13
\
14
\
15
After the search for 7 an RR rotation
is first done to get the tree
8
/ \
7 9
/ \
6 10
/ \
4 11
/ \ \
2 5 12
/ \ \
1 3 13
\
14
\
15
Next a type L rotation is done and the splay node becomes the root.
The new tree is
7
/ \
6 8
/ \
4 9
/ \ \
2 5 10
/ \ \
1 3 11
\
12
\
13
\
14
\
15
The search for 6 is followed by a type L rotation
to make the splay node the root. The resulting tree is
6
/ \
4 7
/ \ \
2 5 8
/ \ \
1 3 9
\
10
\
11
\
12
\
13
\
14
\
15
After the search for 5 an LR rotation
is done to make the splay node the root. The resulting tree is
5
/ \
4 6
/ \
2 7
/ \ \
1 3 8
\
9
\
10
\
11
\
12
\
13
\
14
\
15
The search for 4 is followed by a type L rotation
to make the splay node the root. The resulting tree is
4
/ \
2 5
/ \ \
1 3 6
\
7
\
8
\
9
\
10
\
11
\
12
\
13
\
14
\
15
The search for 3 is followed by a type LR rotation
to make the splay node the root. The resulting tree is
3
/ \
2 4
/ \
1 5
\
6
\
7
\
8
\
9
\
10
\
11
\
12
\
13
\
14
\
15
The search for 2 is followed by a type L rotation
to make the splay node the root. The resulting tree is
2
/ \
1 3
\
4
\
5
\
6
\
7
\
8
\
9
\
10
\
11
\
12
\
13
\
14
\
15
The search for 1 is followed by a type L rotation
to make the splay node the root. The resulting tree is
1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
\
9
\
10
\
11
\
12
\
13
\
14
\
15