AVL TREE vs RB TREE

This blog refers to tree which is a data structure, made up of nodes. Where each node stores a value and there is also some type of hierarchical relationship between the nodes such that one node is the parent of its children. The trees are typically drawn with circles and lines also. The circles represent the nodes of the tree. The lines represent the relationships between a parent node and its child node.

Both AVL and RB trees fall under Self-Balancing Binary Search Trees. These are height-balanced binary search trees that automatically keep the height as small as possible when insertion and deletion operations are performed on trees.

A Binary Search Tree (BST) is a Binary Tree that conforms to the following conditions:

⦁ All nodes stored in the left subtree of a node must have values that are less than that node.

⦁ All nodes stored in the right subtree of a node must have values that are greater than that node.

AVL Tree :

AVL tree (Adelson-Velsky and Landis) is a self-balancing binary search tree invented in 1962. In an AVL tree, heights of the two subtrees (child subtrees) of any node differ by at most one, if at any time they differ by more than one, to restore this property re-balancing is done. This difference is called as the Balance Factor.

We can calculate the Balance Factor from below formula :

BalanceFactor = height(left-subtree) − height(right-subtree)

i.e |B.F| = |hl - hr|     {-1,0,1}

There are 4 types of rotations performed by the AVL tree to balance itself.

⦁ Left rotation

⦁ Right rotation

⦁ Left-Right rotation (LR)

⦁ Right-Left rotation (RL)

The first two rotations are single rotations and the next two rotations are double rotations. To have an unbalanced tree, we need a minimum of a tree of height 2.

Left Rotation : 

If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we perform a single left rotation −

      

                                                                          fig.1                      fig.2                      fig.3

We can see in the above picture, node A has become unbalanced as a node is inserted in the right subtree of A's right subtree. We perform the left rotation by making A the left-sub tree of B.

Right Rotation : 

An AVL tree can become unbalanced if a node is inserted in the left subtree of the left subtree. So we have to perform right rotation.

                                                                          fig.1                      fig.2                       fig.3

As shown in the above picture, the unbalanced node C becomes the right child of its left child by performing a right rotation. And we get a balanced tree.

Left-Right Rotation :

The First type of double rotation is LR rotation. As compared to the above rotations this rotation is slightly complex. This LR (left-right) rotation is a combination of left rotation followed by a right rotation.

STEP -1

Node B has been inserted into the right subtree of the left subtree. So it makes node C an unbalanced node. This causes the AVL tree to perform left-right rotation.

STEP -2 

We have to first perform the left rotation on the left subtree of C. And it will make A, the left subtree of B.

STEP -3

Because of the left-sub tree (node C) of the left-sub (node B) tree, node C is still unbalanced.

STEP -4

Now we, right-rotate the tree, by making B the new root node of this subtree. And now C becomes the right subtree of its own left subtree.

STEP -5

The tree is now balanced.

Right-Left Rotation :

This is the second type of double rotation. It is a combination of right rotation followed by a left rotation.

STEP -1

Node B has been inserted into the left subtree of the right subtree. This makes A, an unbalanced node with a balance factor of 2.

STEP -2

First, we have to perform the right rotation along with the C node, making C the right subtree of its own left subtree B. And now, B becomes the right subtree of A.

STEP -3

Node A is still unbalanced because of the right subtree of its right subtree and requires a left rotation.

STEP -4

A left rotation is performed by making B the new root node of the subtree. And finally A (node) becomes the left subtree of its right subtree B.

STEP -5

The tree is now balanced.

RB Tree :

An RB tree (Red-Black) invented in 1972 is a kind of self-balancing binary search tree where each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits used to ensure that the tree remains approximately balanced during operations like insertio and deletion. The new tree is subsequently rearranged and repainted to restore the coloring properties when the tree modification is done. 

Rules followed by the RB tree are :

⦁  Every node has a color either red or black.

⦁  The root of the tree is always black.

⦁  There are no two adjacent red nodes (A red node cannot have a red parent or red child).

⦁ Every path from a node (including root) to any of its descendant NULL nodes must have the same number of black nodes.

Black Height of a Red-Black Tree:

The amount of black nodes on a path from the root to the leaf is known as black height. Black nodes are also counted when it comes to leaf nodes. From above 3 and 4 rules we can derive, a Red-Black Tree of height h has black-height >= h/2. The number of nodes between a node and its farthest descendant leaf is no more than twice that of the closest descendant leaf. 

Every Red Black Tree with n nodes has height <= 2Log2(n+1)

Time Complexities :

AVL TREE -

Algorithm               Average                        Worst case

Space                         O(n)                                 O(n)

Search                       O(log n)                           O(log n)

Insert                         O(log n)                           O(log n)

Delete                        O(log n)                           O(log n)

RED BLACK TREE -

Algorithm             Average                        Worst case

Space                       O(n)                                 O(n)

Search                     O(log n)                           O(log n)

Insert                       O(log n)                           O(log n)

Delete                      O(log n)                           O(log n)

• Because only a few points are altered, the rotation operations (left and right rotate) take a fixed amount of time. It takes time to update the height and calculate the balance factor. As a result, the time complexity of an AVL insert is the same as that of a BST insert, which is O(h), where his the tree's height is. The height of the AVL tree is O since it is balanced (Log n). As a result, the temporal complexity of the AVL insert is O. (Logn).

SOME MAJOR DIFFERENCES :

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

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

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

APPLICATIONS :

• AVL trees are beneficial in the cases where you are designing some database where insertions and deletions are not that frequent but you have to frequently look up the items present in there.

• RB and AVL binary search trees can be used in a natural way to construct and maintain ordered lists, such as priority queues.

• A red-Black tree is used to implement CPU scheduling Linux. Completely Fair scheduler uses it.

Blog Written By -

- Rugved Rajandekar
- Rahul Ekambaram
- Dhiraj Rathod
- Ritika Sisodiya

                                                     " We Hope That This Will Be Really Helpful To You "