8
/ \
/ \
/ \
/ \
/ \
/ \
4 12
/ \ / \
/ \ / \
/ \ / \
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 15
The tree following the
the deletion of 6 is shown below.
8
/ \
/ \
/ \
/ \
/ \
/ \
4 12
/ \ / \
/ \ / \
/ \ / \
2 5 10 14
/ \ \ / \ / \
1 3 7 9 11 13 15
5
becomes the splay node
q, and
p = 4 and gp = 8. An LR
rotation is done and the splay node becomes the root.
We get the following tree:
5
/ \
/ \
/ \
/ \
/ \
/ \
4 8
/ / \
/ / \
/ / \
2 7 12
/ \ / \
1 3 10 14
/ \ / \
9 11 13 15
The deletion of 7 results in the following tree.
5
/ \
/ \
/ \
/ \
/ \
/ \
4 8
/ \
/ \
/ \
2 12
/ \ / \
1 3 10 14
/ \ / \
9 11 13 15
The splay node is 8, and a type R rotation is done
to get the following tree.
8
/ \
/ \
/ \
/ \
/ \
/ \
5 12
/ / \
/ / \
/ / \
4 10 14
/ / \ / \
2 9 11 13 15
/ \
1 3
5 is deleted we get the following tree.
8
/ \
/ \
/ \
/ \
/ \
/ \
4 12
/ / \
/ / \
/ / \
2 10 14
/ \ / \ / \
1 3 9 11 13 15
8 is the splay node. Since the splay node is already
the root, no rotation is done. The deletion of 10
results in the following tree.
8
/ \
/ \
/ \
/ \
/ \
/ \
4 12
/ / \
/ / \
/ / \
2 9 14
/ \ \ / \
1 3 11 13 15
The splay node is 9, and an RL
rotation is done to get the following tree.
9
/ \
/ \
/ \
/ \
/ \
/ \
8 12
/ / \
/ / \
/ / \
4 11 14
/ / \
2 13 15
/ \
1 3
The deletion of 9 gives us the following tree.
8
/ \
/ \
/ \
/ \
/ \
/ \
4 12
/ / \
/ / \
/ / \
2 11 14
/ \ / \
1 3 13 15
No rotation is done because the splay node, 8,
is already the root.
11 is deleted we get the following tree.
8
/ \
/ \
/ \
/ \
/ \
/ \
4 12
/ \
/ \
/ \
2 14
/ \ / \
1 3 13 15
The splay node is 12, and
a type R rotation is done to get the following tree.
12
/ \
/ \
/ \
8 14
/ / \
4 13 15
/
2
/ \
1 3
The tree following the deletion of 15 is shown below.
12
/ \
/ \
/ \
8 14
/ /
4 13
/
2
/ \
1 3
14 is the splay node, and a type R rotation
is done to get the following tree.
14
/
12
/ \
/ \
/ \
8 13
/
4
/
2
/ \
1 3
When 12 is deleted, the following tree results.
14
/
8
/ \
/ \
/ \
4 13
/
2
/ \
1 3
8 is the splay node and a tye L rotation
is done to get the tree that is shown
below.
8
/ \
/ \
/ \
4 14
/ /
2 13
/ \
1 3
The tree following the deletion of 13 is shown
below.
8
/ \
/ \
/ \
4 14
/
2
/ \
1 3
14 is the splay node and a type R rotation
is done to get the following tree.
14
/
8
/
4
/
2
/ \
1 3
When 14 is deleted we get the following tree.
14
/
8
/
4
/
2
/ \
1 3
This time, there is no rotation.