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

Determine the greatest common divisor, Determine the greatest common diviso...

Determine the greatest common divisor (GCD) of two integers, m & n. The algorithm for GCD might be defined as follows: While m is greater than zero: If n is greater than m, s

Write down the procedure to reverse a singly linked list. , Ans: A pr...

Ans: A procedure to reverse the singly linked list: reverse(struct node **st) { struct node *p, *q, *r; p = *st; q = NULL; while(p != NULL) { r =q;

Linked lists, representation of links list in memory

representation of links list in memory

Pseudocodes, how to draw a 5 inch square on the screen using * symbol

how to draw a 5 inch square on the screen using * symbol

Binary search trees, In this unit, we discussed Binary Search Trees, AVL tr...

In this unit, we discussed Binary Search Trees, AVL trees and B-trees. The outstanding feature of Binary Search Trees is that all of the elements of the left subtree of the root

Write the algorithm to find input and output value, This algorithm inputs 5...

This algorithm inputs 5 values and outputs how many input numbers were positive and how many were negative. Data to be used: N = 1, -5, 2, -8, -7

Use a random number generator to create 10 numbers, Use a random number gen...

Use a random number generator to create 10 numbers between 1 and 1000 and store them in 2 different arrays.  The first array should contain the numbers as they are generated.  The

Implementation of tree, The most common way to insert nodes to a general tr...

The most common way to insert nodes to a general tree is to first discover the desired parent of the node you desire to insert, and then insert the node to the parent's child list.

Searching techniques, Searching is the procedure of looking for something. ...

Searching is the procedure of looking for something. Searching a list containing 100000 elements is not the similar as searching a list containing 10 elements. We discussed two sea

Definition of algorithm, Definition of Algorithm Algorithm must have th...

Definition of Algorithm Algorithm must have the following five characteristic features: 1.      Input 2.      Output 3.      Definiteness 4.      Effectiveness 5

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