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

Binary search tree, A binary search tree (BST), which may sometimes also be...

A binary search tree (BST), which may sometimes also be named a sorted or ordered binary tree, is an edge based binary tree data structure which has the following functionalities:

Graph, multilist representation of graph

multilist representation of graph

Estimate best first search nodes , Given the following search tree, state t...

Given the following search tree, state the order in which the nodes will be searched for breadth first, depth first, hill climbing and best first search, until a solution is reache

All pairs shortest paths, N = number of rows of the graph D[i[j] = C[i][...

N = number of rows of the graph D[i[j] = C[i][j] For k from 1 to n Do for i = 1 to n Do for j = 1 to n D[i[j]= minimum( d ij (k-1) ,d ik (k-1) +d kj (k-1)

Infix expression to postfix form using the stack function, Q. Convert the f...

Q. Convert the following given Infix expression to Postfix form using the stack function: x + y * z + ( p * q + r ) * s , Follow general precedence rule and suppose tha

Darw a flowchart to input 3 numbers, This algorithm inputs 3 numbers, every...

This algorithm inputs 3 numbers, every number goes through successive division by 10 until its value is less than 1. An output is produced which comprise the number input and a val

Sort list of distinct numbers in ascending order - quicksort, (1) Sort a li...

(1) Sort a list of distinct numbers in ascending order, using the following divide- and-conquer strategy (Quicksort): divide the list of numbers into two lists: one that contains a

Which sorting methods sorting a list which is almost sorted, Which sorting ...

Which sorting methods would be most suitable for sorting a list which is almost sorted  Bubble Sorting method.

How do collisions happen during hashing, How do collisions happen during ha...

How do collisions happen during hashing? Usually the key space is much larger than the address space, thus, many keys are mapped to the same address. Assume that two keys K1 an

Complexity of an algorithm, What do you mean by complexity of an algorithm?...

What do you mean by complexity of an algorithm? The complexity of an algorithm M is the function f(n) which gives the running time and/or storage space need of the algorithm i

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