Sunday, April 6, 2014

CS131: Splay Tree

Splay tree is a balanced binary search tree. On average all operations take O(log n) time.
Any sequence of k operations starting from an empty tree and never exceeding n items in tree will have O(k log n) worst case time.
The data structure ensures fast access to recently accessed data and much easier to program that other balanced trees like 2-3-4 tree.
Splay tree is not kept perfectly balanced all the time.

Splay operation

We do splay operation whenever an item is accessed to move an item up through root. Repeatedly doing the operation moves the item up to the root of the tree.
We continuously rotate the tree so that it takes the position of the item above (parent, grand parent, great grand parent etc.) until it becomes the root.
Given an item X to splay up there are three possible situations:

a. X is a left child of a right child or right child of a left child
For left child of a right child we rotate right first and then rotate left to move the item two level up. For right child of a left child we rotate left first and then rotate right to move the item two level up.
b. X is a left child of a left child or right child of a right child
For left child of a left child we rotate right twice to move the item two level up. For right child of a right child we rotate left twice to move the item two level up.
c. X is child of root
We rotate once as appropriate (left or right) to move the item to root.
In all cases one rotation moves the item one level in upper direction.

Splay tree operations

Find operation

find(k)
Search for the key k as like a binary search tree or reached a leaf node
Let X be the last node during the search whether it contains k or not
Splay the node X up so that it becomes root through a sequence of tree rotation

Splay X up to root using a sequence of rotation.


Insert Operation

insert(k)
Insert k like binary search tree
Splay the new node up to root through tree rotation


Remove operation

remove(k)
Remove the node as ordinary binary search tree
Splay the nodes parent up to root using tree rotation


1. Very useful information on Data Structures, definitely it helps us to protect our site from copied content, if you are Looking for software courses?

DOT NET Training in Chennai
Android Training in Chennai
Selenium Training in Chennai
JAVA Training in Chennai
German Classes in chennai

1. Great Article Cloud Computing Projects

Networking Projects

Final Year Projects for CSE

JavaScript Training in Chennai

JavaScript Training in Chennai

The Angular Training covers a wide range of topics including Components, Angular Directives, Angular Services, Pipes, security fundamentals, Routing, and Angular programmability. The new Angular TRaining will lay the foundation you need to specialise in Single Page Application developer. Angular Training

2. A significant thing consider, when choosing your tree, is to guarantee that it has a decent root spread and equalization.click over here

3. Thanks a lot for sharing such a good source with all, i appreciate your efforts taken for the same. I found this worth sharing and must share this with all.

Dot Net Training in Chennai | Dot Net Training in anna nagar | Dot Net Training in omr | Dot Net Training in porur | Dot Net Training in tambaram | Dot Net Training in velachery