Spread the post

Splay tree search element

Before read this article we are recommend view.

Animation of splay tree and insertion process.

Search (find) on splay tree node element. this process are similar to BST. if element are found then make this node as a root node of tree. this process are required of a arrangement and rotations of splay 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,3,11,13,5,4,10] are inserted on splay tree.

69311135410

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) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 3left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 11left (pointer)= NULLright (pointer) parent (pointer) struct Nodedata (int)= 13left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 5left (pointer) right (pointer) parent (pointer) struct Nodedata (int)= 4left (pointer) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 10left (pointer) right (pointer) parent (pointer)= NULL

Search element

Suppose search element [6].

69311135410

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

After rotate.

69311135410 Stack Areamainroot(pointer)find_noderoot(pointer)status (int) =1temp(pointer)value (int) =6 Heap Areastruct Nodedata (int)= 6left (pointer) right (pointer) parent (pointer)= NULLstruct Nodedata (int)= 9left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 3left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 11left (pointer)= NULLright (pointer) parent (pointer) struct Nodedata (int)= 13left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 5left (pointer) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 4left (pointer) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 10left (pointer) right (pointer) parent (pointer)

Program for search element in splay tree.


Output

Stack Areamainroot(pointer)find_noderoot(pointer)status (int) =1temp(pointer)value (int) =6checkrotationnode(pointer)root(pointer)checkrotationnode(pointer)root(pointer)checkrotationnode(pointer)root(pointer)zigmakeRoot(pointer)temp (pointer) ? Heap Areastruct Nodedata (int)= 6left (pointer) right (pointer) parent (pointer) struct Nodedata (int)= 9left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 3left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 11left (pointer)= NULLright (pointer) parent (pointer) struct Nodedata (int)= 13left (pointer)= NULLright (pointer)= NULLparent (pointer) struct Nodedata (int)= 5left (pointer) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 4left (pointer) right (pointer)= NULLparent (pointer) struct Nodedata (int)= 10left (pointer) right (pointer) parent (pointer)= NULL

Visualize process Try it Yourself

Spread the post

Recommended Posts: