Menu
I am studying about various trees, and came across AVL trees and splay trees. I want to know
954
Splay Trees. Another type of self-balancing BST is called the splay tree. Like an AVL tree, a splay tree uses rotations to keep itself balanced. However, for a splay tree, the notion of what it means to be balanced is different.
Splay trees are a lot like other binary search trees. They have nodes, and each node has two children, one left and one right. There is a root node that serves at the begining of the tree. The main difference, though, is that the root node is always the last element that was accessed.
An AVL tree is a self-balancing binary search tree, balanced to maintain O(log n) height. A B-tree is a balanced tree, but it is not a binary tree. Nodes have more children, which increases per-node search time but decreases the number of nodes the search needs to visit.
A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access again. Like self-balancing binary search trees, a splay tree performs basic operations such as insertion, look-up and removal in O(log n) amortized time.
To answer your questions:
What is the difference between AVL trees and splay trees? Both splay trees and AVL trees are binary search trees with excellent performance guarantees, but they differ in how they achieve those guarantee that performance. In an AVL tree, the shape of the tree is constrained at all times such that the tree shape is balanced, meaning that the height of the tree never exceeds O(log n). This shape is maintained on insertions and deletions, and does not change during lookups. Splay trees, on the other hand, maintain efficient by reshaping the tree in response to lookups on it. That way, frequently-accessed elements move up toward the top of the tree and have better lookup times. The shape of splay trees is not constrained, and varies based on what lookups are performed.
On what basis do we select these trees? There is no hard-and-fast rule about this. However, one key difference between the structures is that AVL trees guarantee fast lookup (O(log n)) on each operation, while splay trees can only guarantee that any sequence of n operations takes at most O(n log n) time. This means that if you need real-time lookups, the AVL tree is likely to be better. However, splay trees tend to be much faster on average, so if you want to minimize the total runtime of tree lookups, the splay tree is likely to be better. Additionally, splay trees support some operations such as splitting and merging very efficiently, while the corresponding AVL tree operations are more involved and less efficient. Splay trees are more memory-efficient than AVL trees, because they do not need to store balance information in the nodes. However, AVL trees are more useful in multithreaded environments with lots of lookups, because lookups in an AVL tree can be done in parallel while they can't in splay trees. Because splay trees reshape themselves based on lookups, if you only need to access a small subset of the elements of the tree, or if you access some elements much more than others, the splay tree will outperform the AVL tree. Finally, splay trees tend to be easier to implement than AVL trees, since the rotation logic is much easier.
What are the positives and negatives of these trees? See my answer to (2) above.
What are the performances of these trees in terms of big-O notation? AVL tree insertion, deletion, and lookups take O(log n) time each. Splay trees have these same guarantees, but the guarantee is only in an amortized sense. Any long sequence of operations will take at most O(n log n) time, but individual operations might take as much as O(n) time.
Hope this helps!
166
They are similar in structure and the operations we call on them. The difference is that in splay trees, after each operation, we try to keep the tree almost perfectly balanced so that future operations take less time.
Splay trees are always better than binary search trees when, your application deals with a lot of data in the tree but, will need access to a subset of the data very frequently than others. In this case the data you access frequently will come near the root as a result of the splay. Also, any node can then be accessed with less time than before.
As a general rule for selecting these trees, if you need "Average" log(n) time over a period of tree operations then use splay tree. Binary tree cannot guarantee this.
Positives for both is that you get around log(n) in both these data structures theoretically.
As mentioned splay trees have average log(n) over a number of operations. This means that, maybe you got n time complexity for an operation atleast once in that set. But this will be compensated when accessing the frequent items.
The negative of the binary search tree is that, you need to be lucky to have log(n) always. If the keys are not random, then the tree will reduce to a list like form with only one side.
Splay tree Log(n) on Average for a group of tree operations Binary tree Log(n) only if your keys are going in random.
The results on the runtime are obvious here. You can see the runtime difference in searching with and without splaying.
31
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
