AVL Tree vs Red-Black Tree

AVL Tree

The best benefit of the BST data structure is the time complexity of all the tree operations is O(logn), where n is the number of total nodes. If the BST is a left-skewed or right-skewed tree, time complexity becomes O(n). The solution to this is the AVL tree data structure.

Named after the inventors Adelson-Velsky and Landis. AVL Tree is a self-balancing binary search tree. In an AVL tree, heights of the two child subtrees of any node differ by maximum one. 

AVL Tree is a self – balanced or height-balanced binary search tree where the difference between heights of its left sub-tree and right sub-tree (Balance Factor) can't be more than one for all nodes covered by a tree.

We can say a tree is balanced if the balance factor of each node of a tree is  -1,0 or 1; otherwise, a tree is considered as unbalanced and needs to balance.

           Balance factor (node) = height (left node) – height (right node)

We can balance an AVL tree by performing the operations like left or right rotation. The tree operations on the AVL tree work  in the same way as the BST. After performing any operations on trees, we need to check the balance factor for each node. Therefore, if the tree is  not balanced, we perform rotations in order to make it balanced.

 Operations on AVL Trees

1. Searching

Every AVL tree is a Binary Search Tree, the searching operation in the AVL tree is the same as the BST. We start the searching by comparing the element we want to find with the root node. Also, based on the required element’s key value, we go either left or right subtree from the root node and repeat the process. We terminate the searching process when locating the required element or after fully visiting the tree.

The time complexity for searching an element in the AVL is O(logn), where the total number of nodes in an AVL tree is n.

2. Insertion

 The AVL tree has insertion operation similar to the BST insertion. In the AVL tree, there is an additional step i.e. we need to calculate the balance factor for each node after the insertion operation to ensure that the tree is always balanced. 

We insert the element at the root, when  the tree is empty. If the tree is not empty, then we compare the value of the node that we want to insert with the parent or root node. Based on the comparison, we either go to the right or left subtree and get the correct position for inserting the new node.

To ensure that the given tree remains AVL after every insertion, we need to perform some re-balancing.

Two operations that can be performed to re-balance a BST without violating the BST property (keys(left) < key(root) < keys(right)) are as follows:

1) Left Rotation

2) Right Rotation

Let’s insert the node with a key-value 4:

3. Deletion

In the AVL tree, the deletion operation is similar to the BST deletion. Then, we need to calculate the balance factor for each node after performing a deletion operation. When we want to delete a node, firstly we need to  traverse the tree to find the location of the node. This process is similar to searching nodes or elements in the AVL tree or BST.

When we find our required node in the given tree, we simply delete that node. After the deletion of the node, we have to calculate the balance factor for each node. If the AVL tree is unbalanced, we perform the left or right rotations as per the need. The time complexity for deleting any element from the AVL tree is O(logn).

After deleting the node with a value of 12, we can see that the AVL is not balanced anymore. Therefore, we need to perform a right rotation here to balance the AVL tree:

 

 

Red-Black Trees

A red-black tree is a kind of self-balancing BST where each node has an extra bit, and that bit is often interpreted as the color (red or black).

These colors are used to ensure that the tree remains balanced after the operations like insertions and deletions.

Even if, the balance of the tree is not appropriate, it is good enough to reduce the searching time and maintain it around O(log n) time.

RB tree was invented in 1972 by Rudolf Bayer. 

Need of RB Tree

Most of the BST operations like search, max, min, insert, delete. etc take O(h) time where h is the height of the Binary Search Tree. The time complexity of these operations may become O(n) for a skewed Binary tree.  If we make sure that the height of the RB tree remains O(log n) after every insertion and deletion, then we can consider an upper bound of O(log n) for all these operations. The height of a Red-Black tree is always log n where n is the number of nodes in the tree.

Rules for Every Red-Black Tree  to follow: 

1. Every node of the tree has a color either red or black.

2. The RB tree's root node is always black.

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

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

5. The number of black nodes from the root to that node i.e. the number of black ancestors is the black depth of a node.

Properties of Red-Black Trees

1.Black height of the red-black tree is the number of black nodes on a path from the root node to a leaf node of a tree. Leaf nodes are also considered as black nodes. So, the red-black tree of height h has black height >= h/2.

2. The height of a red-black tree with n nodes is h<= 2 log2(n + 1).

Operations on Red-Black Trees

Insertion operation in the RB Trees follows some rules of insertion in the BST. If the tree is empty, then we need to insert the element and make it black because it would be the root node. But, when the tree is not empty, we create a new node and color it red.

Whenever we want to insert an element in the tree, the default color of the new node will always be red. It means the color of the child node and parent node should not be red. We only have to make sure there are no adjacent red nodes.

After inserting an element, if the parent node of the inserted element is black, we don’t have to perform any extra operation. It’ll be a balanced RBT. But if the parent of the inserted element is red, then we need to check the color of the parent’s sibling node. Therefore, we need to check the color of the node, which is at the same level as the parent node.

Deletion operation in RBT is the same as deletion in the BST. First, we need to traverse the tree until the desired node is found. As soon as we locate the node, we remove that node from the RBT.

If we delete any red noded, it won’t violate any condition of RB Trees. Hence, we just need to remove the node like in BST.  In the case of deleting a black node, it may violate the condition of RBT. Therefore, after the deletion of any black node, we have to perform some operations like rotations and recoloring in order to rebalance the RBT.

 Two tools are used for balancing the tree in a Red-Black tree, If the tree is not balanced:

1. Recoloring

2.Rotation

Comparison with AVL Tree:

The AVL trees are more balanced as compared to Red-Black Trees, but they may cause more rotations during insertion and deletion of a node.

If your application involves frequent insertions and deletions, then Red-Black trees should be preferred.

Let’s now look at the core differences between the AVL tree and Red-Black tree data structures:

 

Parameter	Red Black Tree	AVL Tree
Used for	When application involves more insertion and deletion	When searching is on the higher priority.
Insertion and Deletion	Insertion and deletion operations are easy because only few rotations are required to balance the tree in insertion or deletion.	Insertion and deletion are complex in AVL trees because it requires multiple rotations to balance the tree.
Searching	Red black is not used for efficient searching because it is a roughly balanced tree instead of strictly balanced.	Efficient searching is done by AVL tree because it is strictly balanced.
Color of the node	We color the nodes of the red black tree either red or black.	No color is required in case of AVL trees.
Balance factor	It does not contain any balance factor. It stores only one bit of information that denotes either Red or Black color of the node.	Each node has a balance factor in the AVL tree whose value can be 1, 0, or -1. It requires extra memory to store the balance factor per node.
Lookups	Red Black Trees have less lookups as they are not strictly balanced.	AVL trees provide faster lookups than Red Black Trees as they are more strictly balanced.
Information	Red Black Tree needs only 1 bit of information per node.	AVL trees store balance factors or heights with each node, thus requiring storage for an integer per node.
Applications	Red Black Trees are used in most of the language libraries like map, multimap, multiset in C++ etc.	AVL trees are used in the databases where faster retrievals are required.

APPLICATIONS

• Red–black trees are specifically valuable in functional programming, used to construct associative arrays and sets which are able to retain previous versions after mutations.

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

• In the version 8 of Java, the HashMap has been modified such that instead of using a LinkedList to store different elements with colliding hash codes, a red-black tree is used. This results in the improvement of time complexity of searching an element from O(n) to O(log n).

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

• Red-Black trees are common in the Linux kernel. Such as in a process scheduler or for keeping track of the virtual memory segments for a process. They are also used in map, multimap, multiset from C++ STL and java.util.TreeMap , java.util.TreeSet from Java.

• Red-Black trees are benificial in K-mean clustering algorithm for reducing time complexity

• Red Black tree is also used to implement CPU scheduling Linux. 

Conclusion:

In this article, we discussed AVL and red-black tree data structures. We presented the properties and operations along with examples.

Finally, we explored core differences between them.