Spread the post

Delete given node in splay tree

Before read this article we are recommend view Animation of splay tree and insertion process.

Deletion of a splay tree node. first need to find particular delete element (search element). if found deleted node then make this node as a root of tree. This process are required some splay tree rotation. after arrangement delete this root nodes. After remove root node we are get left and right subtree. If left sub tree are not NULL that means element are exist in left subtree. then find big value in this left subtree and make this big node as a root of tree and combine right subtree. If left subtree are NULL then make the Right subtree first node as a root node of tree.

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.

Suppose following nodes [6,9,5,34,80,54,90,3,7] are inserted on splay tree.

6953480549037

Visualize insertion

Try it Yourself

View nodes and pointers.

Stack Areamainroot(pointer) Heap Areastruct Nodedata (int)= 6left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 9left (pointer)= NULLright (pointer) parent (pointer) struct Nodedata (int)= 5left (pointer)= NULLright (pointer) parent (pointer) struct Nodedata (int)= 34left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 80left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 54left (pointer) right (pointer) parent (pointer) struct Nodedata (int)= 90left (pointer) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 3left (pointer)= NULLright (pointer) parent (pointer) struct Nodedata (int)= 7left (pointer) right (pointer) parent (pointer)= NULL

Delete element

Suppose delete element [9].

6953480549037

If splay tree delete node are found then required rotation to make this node at the root. and delete root node.

After delete and rotatation.

653480549037

View pointer after delete.

Stack Areamainroot(pointer)delete_nodeauxilary(pointer)help(pointer)root(pointer)status (int) =1temp(pointer)value (int) =9 Heap Areastruct Nodedata (int)= 6left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 5left (pointer)= NULLright (pointer) parent (pointer) struct Nodedata (int)= 34left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 80left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 54left (pointer) right (pointer) parent (pointer) struct Nodedata (int)= 90left (pointer) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 3left (pointer)= NULLright (pointer) parent (pointer) struct Nodedata (int)= 7left (pointer) right (pointer) parent (pointer)= NULL

Program for Delete given node in splay tree.


Output

Stack Areamainroot(pointer)delete_nodeauxilary(pointer) NULLhelp(pointer) NULLroot(pointer)status (int) =1temp(pointer)value (int) =9checkrotationnode(pointer)root(pointer)zagziggrandpa(pointer)makeRoot(pointer)t_parent(pointer) Heap Areastruct Nodedata (int)= 6left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 9left (pointer)= NULLright (pointer) parent (pointer) struct Nodedata (int)= 5left (pointer)= NULLright (pointer) parent (pointer) struct Nodedata (int)= 34left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 80left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 54left (pointer) right (pointer) parent (pointer) struct Nodedata (int)= 90left (pointer) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 3left (pointer)= NULLright (pointer) parent (pointer) struct Nodedata (int)= 7left (pointer) right (pointer) parent (pointer)= NULL

Visualize process Try it Yourself

Spread the post

Recommended Posts: