Splaying steps - splay trees, Data Structure & Algorithms

Assignment Help:

Readjusting for tree modification calls for rotations in the binary search tree. Single rotations are possible in the left or right direction for moving a node to the root position. The task would be achieved this way, but the performance of the tree amortized over many accesses may not be good.

Rather, the key idea of splaying is to move the accessed node two levels up the tree at each step. Basic terminologies in this context are:

Zig: Movement of one step down the path to the left to fetch a node up. Zag: Movement of one step down the path to the right to fetch a node up.

With these two fundamental steps, the possible splay rotations are: Zig-Zig: Movement of two steps down to the left.

Zag-Zag: Movement of two steps down to the right. Zig-Zag: Movement of one step left and then right. Zag-Zig: Movement of one step right and then left.

Figure depicts the splay rotations.

Zig:

Zig-Zig:

Zig-Zag:

Splaying may be top-down or bottom-up. In bottom-up splaying, splaying begin at the accessed node, moving up the chain to root. While in top-down splaying, splaying begins from the top while searching for the node to access. In the next section, we would be discussing the top-down splaying procedure:

As top-down splaying proceeds, the tree is split into three parts:

a) Central SubTree: This is initially the complete tree and may contain the target node. Search proceeds by comparison of the target value with the root and ends with the root of the central tree being the node containing the target if present or null node if the target is not present.

b) Left SubTree: This is initially empty and is created as the central subtree is splayed. It consists of nodes with values less than the target being searched.

c) Right SubTree: This is also initially empty and is created similar to left subtree. It contains nodes with values more than the target node.


Related Discussions:- Splaying steps - splay trees

Tower of hanoi problem., Write an algorithm for getting solution to the Tow...

Write an algorithm for getting solution to the Tower's of Hanoi problem. Explain the working of your algorithm (with 4 disks) with appropriate diagrams. Ans: void Hanoi(int

Declaring a two dimensional array, Declaring a two dimensional array   A...

Declaring a two dimensional array   A two dimensional array is declared same to the way we declare a one-dimensional array except that we state the number of elements in both di

The two famous methods for traversing, The two famous methods for traversin...

The two famous methods for traversing are:- a) Depth first traversal b) Breadth first

Frequency count, what is frequency count with examble

what is frequency count with examble

Depth of complete binary tree, What will be depth do , of complete binary t...

What will be depth do , of complete binary tree of n nodes, where nodes are labelled from 1 to n with root as node and last leaf node as node n

Define strictly binary tree, Define Strictly Binary Tree Strictly Bina...

Define Strictly Binary Tree Strictly Binary Tree: - If each non leaf node in binary tree has non empty left and right sub-trees , then the tree is known as a strictly binary t

Direct file organisation, It offers an effective way to organize data while...

It offers an effective way to organize data while there is a requirement to access individual records directly. To access a record directly (or random access) a relationship is

Binry trees, Build a class ?Node?. It should have a ?value? that it stores ...

Build a class ?Node?. It should have a ?value? that it stores and also links to its parent and children (if they exist). Build getters and setters for it (e.g. parent node, child n

For loop, for (i = 0; i sequence of statements } Here, the loop e...

for (i = 0; i sequence of statements } Here, the loop executes n times. Thus, the sequence of statements also executes n times. Since we suppose the time complexity of th

Entity relationship diagram, This question is based on the requirements of ...

This question is based on the requirements of a system to record band bookings at gigs. (A 'gig' is an event at which one or more bands are booked to play). You do not need to know

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd