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

Determine the effect of ruby in implementation of string, Determine the eff...

Determine the effect of Ruby in implementation of string Ruby has a String class whose instances are mutable sequences of Unicode characters. Symbol class instances are charact

User-specified memory location, You need to implement a function which will...

You need to implement a function which will write out a given user-specified memory location to disk in base 10. That means that you have to convert the large number data structure

Linked list, how to creat atm project by using linked list?

how to creat atm project by using linked list?

Non-recursive implementation of preorder traversal, For preorder traversal,...

For preorder traversal, in the worst case, the stack will rise to size n/2, where n refer to number of nodes in the tree. Another method of traversing binary tree non-recursively t

Sequential files, Data records are stored in some particular sequence e.g.,...

Data records are stored in some particular sequence e.g., order of arrival value of key field etc. Records of sequential file cannot be randomly accessed i.e., to access the n th

The complexity of searching an element, The complexity of searching an elem...

The complexity of searching an element from a set of n elements using Binary search algorithm is   O(log n)

Expression trees, What are the expression trees? Represent the below writte...

What are the expression trees? Represent the below written expression using a tree. Give a relevant comment on the result that you get when this tree is traversed in Preorder,

What is a binary search tree (bst), What is a Binary Search Tree (BST)? ...

What is a Binary Search Tree (BST)? A binary search tree B is a binary tree every node of which satisfies the three conditions: 1.  The value of the left-subtree of 'x' is le

Define ordinary variable, Ordinary variable An ordinary variable of a e...

Ordinary variable An ordinary variable of a easy data type can store a one element only

Explain graph traversal, Graph Traversal In many problems we wish to in...

Graph Traversal In many problems we wish to investigate all the vertices in a graph in some systematic order. In graph we often do not have any single vertex singled out as spe

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