Question

6.)Perform an experimental study to compare the speed of our AVL tree,

splay tree, and red-black tree implementations for various sequences of

operations

Answer 1

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.

AVL trees provide faster lookups than Red Black Trees because they are more strictly balanced.

Red Black Trees provide faster insertion and removal operations than AVL trees as fewer rotations are done due to relatively relaxed balancing.

AVL trees store balance factors or heights with each node, thus requires storage for an integer per node whereas Red Black Tree requires only 1 bit of information per node.

Red Black Trees are used in most of the language libraries like map, multimap, multiset in C++ whereas AVL trees are used in databases where faster retrievals are required.

->Splay tree provides performance better than O(log n) by optimizing the placement of nodes. It makes the recently accessed nodes in the top of the tree and hence providing better performance. It’s suitable for cases where there are large number of nodes but only few of them are accessed frequently.

->Red-Black tree is preferred over AVL trees when there is high frequency of insert/delete operations compared to search as AVL tree balancing (rotation) is expensive. Red-black tree balances itself on insert and delete operations satisfying the following conditions.

Each node is either red or black. Usually color information is stored in a bit in the node.

Root and leaf nodes are black.

No two red nodes to be adjacent, meaning, a red node cannot have a parent or children which are red.

Every path from root to leaf nodes have same number of black nodes.

->Binary Search Tree (BST) becomes ineffective, O(n) worst case if not balanced. Any practical usage of BST requires a balanced tree. AVL tree is a self-balancing binary search tree which guarantees O(log n) performance.

• AVL tree balances itself on insertion and deletion.
• Balancing is done by computing the balance factor for every node. A node in a tree is unbalanced if its absolute(balance factor) > 1. That means a node stays balanced if it’s left and right sub-tree are in the same level or in difference of one level.
• Balance factor = (height of left sub-tree ) – (height of right sub-tree)
• Once a node is determined as unbalanced, balancing the node is done using rotations.