Learn basic concept of c , c++ and python programming in regularcodes.com

Spread the post

Insertion in splay tree

Before read this article we are recommend view.

Animation of splay tree .

Insertion of splay tree are similar to Binary search tree. but here small difference. inserted newly node are maked as root node of tree. this process are required some arrangement and rotation in splay tree nodes.

Splay tree rotation

Basic 6 type of rotation are possible in splay tree.

1) Zig

2) Zag

3) ZigZig

4) ZagZig

5) ZigZig

6) ZagZag

View rotations example of splay tree.

Note that there are possible to minimize this 6 rotations.

Insertion in empty splay tree

Step by step inserting following [6, 2, 9, 11, 1] nodes in splay tree.

Insert node : 6

In this case tree are empty then insert node 6 and assign this node to root of splay tree.

6

Visualize Try it Yourself

In this post use one extra pointer which is pointed to parent of child node. root are point to this first node of splay tree.

Stack Areamainroot(pointer) Heap Areastruct Nodedata (int)= 6left (pointer)= NULLright (pointer)= NULLparent (pointer)= NULL

Insert node : 2

insert node to its proper position.

62

visualize this inserted position.

Stack Areamainroot(pointer)insertNodenew_node(pointer)root(pointer)temp(pointer)value (int) =2 Heap Areastruct Nodedata (int)= 6left (pointer) right (pointer)= NULLparent (pointer)= NULLstruct Nodedata (int)= 2left (pointer)= NULLright (pointer)= NULLparent (pointer)

Insert node 2 required Zig rotation.

62

Make new node as root node of tree.

Stack Areamainroot(pointer)insertNodenew_node(pointer)root(pointer)temp(pointer)value (int) =2 Heap Areastruct Nodedata (int)= 6left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 2left (pointer)= NULLright (pointer) parent (pointer)= NULL

Visualize Zig Rotation Try it Yourself

Insert node 9

insert node to its proper position.

629

View node position.

Stack Areamainroot(pointer)insertNodenew_node(pointer)root(pointer)temp(pointer)value (int) =9 Heap Areastruct Nodedata (int)= 6left (pointer)= NULLright (pointer) parent (pointer) struct Nodedata (int)= 2left (pointer)= NULLright (pointer) parent (pointer)= NULLstruct Nodedata (int)= 9left (pointer)= NULLright (pointer)= NULLparent (pointer)

After Zag zag rotation.

629 Stack Areamainroot(pointer) Heap Areastruct Nodedata (int)= 6left (pointer) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 2left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 9left (pointer) right (pointer)= NULLparent (pointer)= NULL

Visualize Zagzag Try it Yourself

Insert node 11

insert node to its proper position.

62911 Stack Areamainroot(pointer)insertNodenew_node(pointer)root(pointer)temp(pointer)value (int) =11checkrotationnode(pointer)root(pointer)zagmakeRoot (pointer) ? temp (pointer) ? Heap Areastruct Nodedata (int)= 6left (pointer) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 2left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 9left (pointer) right (pointer) parent (pointer)= NULLstruct Nodedata (int)= 11left (pointer)= NULLright (pointer)= NULLparent (pointer)

After Zag rotation

62911

Visualize Zagzag Try it Yourself

Stack Areamainroot(pointer) Heap Areastruct Nodedata (int)= 6left (pointer) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 2left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 9left (pointer) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 11left (pointer) right (pointer)= NULLparent (pointer)= NULL

Insert node 1

629111 Stack Areamainroot(pointer)insertNodenew_node(pointer)root(pointer)temp(pointer)value (int) =1checkrotationnode(pointer)root(pointer)zigziggrandpa(pointer)makeRoot(pointer)t_parent(pointer) Heap Areastruct Nodedata (int)= 6left (pointer) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 2left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 9left (pointer) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 11left (pointer) right (pointer)= NULLparent (pointer)= NULLstruct Nodedata (int)= 1left (pointer)= NULLright (pointer) parent (pointer)

Program for insertion in splay tree.


Output

Stack Areamainroot(pointer)insertNodenew_node(pointer)root(pointer)temp(pointer)value (int) =1checkrotationnode(pointer)root(pointer)checkrotationnode(pointer)root(pointer)checkrotationnode(pointer)root(pointer) Heap Areastruct Nodedata (int)= 6left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 2left (pointer)= NULLright (pointer) parent (pointer) struct Nodedata (int)= 9left (pointer) right (pointer) parent (pointer) struct Nodedata (int)= 11left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 1left (pointer)= NULLright (pointer) parent (pointer)= NULL

Visualize process Try it Yourself

Spread the post

Recommended Posts: