20
No rotation is done because the inserted element is already the root.
The next insert yields the following tree.
20
/
10
A type L rotation is done with 10 as the
splay node. The result is the following tree.
10
\
20
When 5 is inserted, the following tree results.
10
/ \
5 20
The splay node is
5 and a type L rotation is done to get
the following tree.
5
\
10
\
20
When 30 is inserted the tree becomes
5
\
10
\
20
\
30
An RR rotation is done to get the following tree.
5
\
30
/
20
/
10
Next a type R rotation is done to get the following tree.
30
/
5
\
20
/
10
When 40 is inserted we get the following tree.
30
/ \
5 40
\
20
/
10
A type R rotation
is done to make the splay node (40) the root.
The resulting tree is
40
/
30
/
5
\
20
/
10
When 25 is inserted we get the
following tree.
40
/
30
/
5
\
20
/ \
10 25
An RR rotation is done to get the following tree.
40
/
30
/
25
/
20
/
5
\
10
Now an LL rotation is done to get the tree
25
/ \
20 30
/ \
5 40
\
10
When 8 is inserted we get the
following tree.
25
/ \
20 30
/ \
5 40
\
10
/
8
First an RL rotation is done. The new tree is
25
/ \
20 30
/ \
8 40
/ \
5 10
Then an LL rotation
is done to make the splay node the root. The resulting tree is
8
/ \
5 20
/ \
10 25
\
30
\
40
Inserting 35 results in the following tree.
8
/ \
5 20
/ \
10 25
\
30
\
40
/
35
An RL rotation is done to get the following tree.
8
/ \
5 20
/ \
10 25
\
35
/ \
30 40
Now an RR rotation is done. The resulting tree is
8
/ \
5 35
/ \
25 40
/ \
20 30
/
10
Finally a type R rotation is done
to make the splay node the root. The resulting tree is
35
/ \
8 40
/ \
5 25
/ \
20 30
/
10
When 7 is inserted the following tree results.
35
/ \
8 40
/ \
5 25
\ / \
7 20 30
/
10
First an LR rotation is done to get the following tree.
35
/ \
7 40
/ \
5 8
\
25
/ \
20 30
/
10
Next a type L rotation is done to move the splay node to the
root level. The resulting tree is
7
/ \
5 35
/ \
8 40
\
25
/ \
20 30
/
10
The tree following the insertion of 23 is shown
below.
7
/ \
5 35
/ \
8 40
\
25
/ \
20 30
/ \
10 23
An LR rotation is done to get the following tree.
7
/ \
5 35
/ \
8 40
\
23
/ \
20 25
/ \
10 30
Another LR rotation is done. The new tree is
7
/ \
5 23
/ \
/ \
/ \
8 35
\ / \
20 25 40
/ \
10 30
Now a type R rotation is done and the splay node becomes the root.
The new tree is shown below.
23
/ \
/ \
/ \
7 35
/ \ / \
5 8 25 40
\ \
20 30
/
10