Splay trees, Data Structure & Algorithms

Addition of new records in a Binary tree structure always occurs as leaf nodes, which are further away from the root node making their access slower. If this new record is to be accessed frequently, then we cannot afford to spend much time in attainment of it but would require it to be positioned close to the root node. It would call for rebuilding or readjustment of the tree to attain the desired shape. But, this process of rebuilding the tree every time as the preferences for the records change is tedious and time consuming. There has to be some measure so that the tree adjusts itself automatically as the frequency of accessing the records changes. Such a self-adjusting tree is the Splay tree.

Splay trees are self-adjusting binary search trees in which every access for insertion or retrieval of any node, lifts that node all the way up to become the root, pushing the other nodes out of the way to make room for this new root of the modified tree. Hence, the frequently accessed nodes will frequently be lifted up and remain around the root position; whereas the most infrequently accessed nodes would move farther and farther away from the root.

This process of readjusting may at times create a highly imbalanced splay tree, wherein a single access may be extremely expensive. But over a long sequence of accesses, these expensive cases may be averaged out by the less expensive ones to produce excellent results over a long sequence of operations. The analytical tool utilized for this purpose is the Amortized algorithm analysis. This will be discussed fully in the following sections.

Posted Date: 4/11/2013 5:56:50 AM | Location : United States







Related Discussions:- Splay trees, Assignment Help, Ask Question on Splay trees, Get Answer, Expert's Help, Splay trees Discussions

Write discussion on Splay trees
Your posts are moderated
Related Questions
explain collision resloving techniques in hasing

Q. What do you understand by the tree traversal? Write down the procedure for traversing a binary tree in preorder and execute it on the following tree.    Ans: Th

Define neotaxonomy. Discuss how electron microscopy can help in solving a zoological problem faced by taxonomist.

Problem 1. You are asked to store Names of all 100 students of class A in your Learning Centre. Which data type will you use? What is its syntax? Explaining the data typ


state difference between linear and non linear data structure. give one example scenario of each

discuss the operating system under the following: MONOLITHIC SYSTEM,LAYER SYSTEM AND VIRTUAL MACHINES

Explain about the Structured types - Built-In Types Values of the carrier set are not atomic, consisting rather than several atomic values arranged in some way. Common illu

Records are mapped onto a computer store by simply juxtaposing their elements. The address of a component (field) r relative to the origin address of the record r is named the fiel

So far, we now have been concerned only with the representation of single stack. What happens while a data representation is required for several stacks? Let us consider an array X