Splaying procedure, Data Structure & Algorithms

Assignment Help:

For splaying, three trees are maintained, the central, left & right sub trees. At first, the central subtree is the complete tree and left and right subtrees are empty. The target key is compared to the root of the central subtree where the following two conditions are possible:

a) Target > Root: If target is greater than the root, then the search will be more to the right and in the procedure, the root and its left subtree are shifted to the left tree.

b) Target < Root: If the target is less than the root, then the search is shifted to the left, moving the root and its right subtree to right tree.

We repeat the comparison procedure till either of the following conditions is satisfied:

a) Target is found: In this, insertion would create a duplicate node. Therefore, original node is maintained. Deletion would lead to elimination the root node.

b) Target is not found and we reach a null node: In this case, target is inserted in the null node position.

Now, the tree is reassembled. For the target node, which is the new root of our tree, the largest node is the left subtree & is linked to its left child and the smallest node in the right subtree is connected as its right child.


Related Discussions:- Splaying procedure

Draw trace table and determine output of number, Draw trace table and deter...

Draw trace table and determine output from the following flowchart using following data: Number = 45, -2, 20.5

Convert graph into tree, How can we convert a graph into a tree ? Do we hav...

How can we convert a graph into a tree ? Do we have any standardized algorithm for doing this?

Implementation of queue by using a single linked list, Q. Perform implement...

Q. Perform implementation of a queue using a singly linked list L. The operations INSER and DELETE should take O (1) time.

Tree, tree is graph or not

tree is graph or not

Data type, Q. Define the terms data type and abstract data type. Comment up...

Q. Define the terms data type and abstract data type. Comment upon the significance of both these.   Ans: We determine the total amount of memory to reserve by determining

What is called the basic operation of an algorithm, What is called the basi...

What is called the basic operation of an algorithm? The most significant operation of the algorithm is the operation contributing the most to the total running time is known as

Importance of object-oriented over java, Importance of Object-Oriented over...

Importance of Object-Oriented over java Java is basically based on OOP notions of classes and objects. Java uses a formal OOP type system that should be obeyed at compile-t

Tree, application of threaded binary treee

application of threaded binary treee

Data Structure, Ask consider the file name cars.text each line in the file ...

Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

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