Splay trees, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Splay trees

What do you understand by structured programming, What do you understand by...

What do you understand by structured programming Structured Programming  This term is used for programming design that emphasizes:- (1) Hierarchical design of programmi

Applications of avl trees, AVL trees are applied into the given situations:...

AVL trees are applied into the given situations: There are few insertion & deletion operations Short search time is required Input data is sorted or nearly sorted

The searching technique that takes o (1) time to find a data, The searching...

The searching technique that takes O (1) time to find a data is    Hashing is used to find a data

Python programming, how to write a function of area of a circle using pytho...

how to write a function of area of a circle using python

Flow chart, What is tha flow chart of algorithm

What is tha flow chart of algorithm

Threaded Binary Tree, If a node in a binary tree is not containing left or ...

If a node in a binary tree is not containing left or right child or it is a leaf node then that absence of child node can be represented by the null pointers. The space engaged by

Exact analysis of insertion sort, Exact analysis of insertion sort: Let...

Exact analysis of insertion sort: Let us assume the following pseudocode to analyse the exact runtime complexity of insertion sort. T j   is the time taken to execute the s

Tradeoff between space and time complexity, We might sometimes seek a trade...

We might sometimes seek a tradeoff among space & time complexity. For instance, we may have to select a data structure which requires a lot of storage to reduce the computation tim

Explain divide and conquer algorithms, Explain divide and conquer algorithm...

Explain divide and conquer algorithms  Divide  and  conquer  is  probably  the  best  known  general  algorithm  design  method.  It   work according to the following general p

Describe data structure?, Typical programming languages such as Pascal, C o...

Typical programming languages such as Pascal, C or Java give primitive data kinds such as integers, boolean, reals values and strings. They give these to be organised into arrays,

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