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
Q. Establish the usage of linked lists for polynomial manipulation.                                       Ans. Usag e of Linked List for Polynomial Manipulation. Link

Q. Describe what do you understand by the term array? How does an array vary from an ordinary variable? How are the arrays represented in the specific memory?

Define the Internal Path Length The Internal Path Length I of an extended binary tree is explained as the sum of the lengths of the paths taken over all internal nodes- from th

Write an algorithm for searching a key from a sorted list using binary search technique 1.   if (low > high) 2.     return (-1) 3.    mid = (low +high)/2; 4    .if ( X

what is queues? how it work? and why it used? i want an assignment on queue .....

Explain the array and linked list implementation of stack

Illustrates the program for Binary Search. Program: Binary Search /*Header Files*/ #include #include /*Functions*/ void binary_search(int array[ ], int value,

Program: Creation of a Circular linked list ALGORITHM (Insertion of an element into a Circular Linked List) Step 1        Begin Step 2      if the list is empty or new

In assignment, you have already started the process of designing a database for the Beauty Salon mini-case (enclosed again below), mainly in the phase of conceptual database design

State the range of operation of ADT Operations of the Range of T ADT includes following, where a, b ∈ T and r and s are values of Range of T: a...b-returns a range value (an