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.
Tree rotation

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
Very useful information on Data Structures, definitely it helps us to protect our site from copied content, if you are Looking for software courses?
ReplyDeleteDOT NET Training in Chennai
Hadoop Training in Chennai
Android Training in Chennai
Selenium Training in Chennai
JAVA Training in Chennai
German Classes in chennai
Loadrunner Training in Chennai
Loadrunner Training in T Nagar
Great Article Cloud Computing Projects
DeleteNetworking 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
A significant thing consider, when choosing your tree, is to guarantee that it has a decent root spread and equalization.click over here
ReplyDeleteThanks 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.
ReplyDeleteDot 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