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

Assignment, How do I submit a three page assignment

How do I submit a three page assignment

Find the complexity of an algorithm, Q.1 What is an algorithm? What are the...

Q.1 What is an algorithm? What are the characteristics of a good algorithm? Q.2 How do you find the complexity of an algorithm? What is the relation between the time and space c

Designed to manage the booking, Beauty Salon is a system to be designed to...

Beauty Salon is a system to be designed to manage the booking and the payment of a single beauty parlour. Beauty Therapists: A beauty parlour has a number of staff members mo

Conversion of general trees to binary trees, Taking a suitable example expl...

Taking a suitable example explains how a general tree can be shown as a Binary Tree. Conversion of general trees to binary trees: A general tree can be changed into an equiv

What is assertions and abstract data types, Assertions and Abstract Data Ty...

Assertions and Abstract Data Types Even though we have defined assertions in terms of programs, notion can be extended to abstract data types (which are mathematical entities).

Perform inorder, QUESTION (a) Construct a binary tree for the following...

QUESTION (a) Construct a binary tree for the following numbers assuming that a number greater than the node (starting from the root) goes to the left else it goes to the right.

Determine the warnock algorithm, Warnock's Algorithm A divide and conqu...

Warnock's Algorithm A divide and conquer algorithm Warnock (PolyList PL, ViewPort VP) If (PL simple in VP) then Draw PL in VP, else Split VP vertically and horiz

Perform breadth -first search, You are given two jugs, a 4-gallon one and a...

You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring marker on it. There is a tap that can be used to fill the jugs with water. How can you get exac

Implementation of a binary tree, Like general tree, binary trees are implem...

Like general tree, binary trees are implemented through linked lists. A typical node in a Binary tree has a structure as follows struct NODE { struct NODE *leftchild; 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