Hello everyone when we search related to the data structure we always get the list of main topics. In this list we always see one name 'TREES'.

      A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees. So there are many types of trees are available for Eg. Binary search tree, AVL tree , RB tree , etc. In this blog we will see the details about AVL tree, RB tree and difference between both the trees. 

     AVL tree 

     AVL tree is Named after their inventor Adelson, Velski and Landis, AVL trees are height balancing binary search tree. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor. 

             

AVL TREE

AVL Tree can be defined as height balanced binary search tree in which each node is associated with a balance factor which is calculated by subtracting the height of its right sub-tree from that of its left sub-tree.

Tree is said to be balanced if balance factor of each node is in between -1 to 1, otherwise, the tree will be unbalanced and need to be balanced.

        Balance Factor (k) = height (left(k)) - height (right(k))

If balance factor of any node is 1, it means that the left sub-tree is one level higher than the right sub-tree.

If balance factor of any node is 0, it means that the left sub-tree and right sub-tree contain equal height.

If balance factor of any node is -1, it means that the left sub-tree is one level lower than the right sub-tree.

     Operations on AVL tree

Due to the fact that, AVL tree is also a binary search tree therefore, all the operations are performed in the same way as they are performed in a binary search tree. Searching and traversing do not lead to the violation in property of AVL tree. However, insertion and deletion are the operations which can violate this property and therefore, they need to be revisited. 

   1. INSERTION OPERATION 

Insertion in AVL tree is performed in the same way as it is performed in a binary search tree. However, it may lead to violation in the AVL tree property and therefore the tree may need balancing. The tree can be balanced by applying rotations.

  2 .  DELETION  OPERATION 

Deletion can also be performed in the same way as it is performed in a binary search tree. Deletion may also disturb the balance of the tree therefore, various types of rotations are used to rebalance the tree.

Why AVL Trees? 

Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. 

If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree 

Time Complexity 

The rotation operations (left and right rotate) take constant time as only a few pointers are being changed there. Updating the height and getting the balance factor also takes constant time. 

So the time complexity of AVL insert remains same as BST insert which is O(h) where h is the height of the tree. Since AVL tree is balanced, the height is O(Logn). So time complexity of AVL insert is O(Logn).

 RB TREE

A red-black tree is a kind of self-balancing binary search tree 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 during insertions and deletions. 

Although the balance of the tree is not perfect, it is good enough to reduce the searching time and maintain it around O(log n) time, where n is the total number of elements in the tree. This tree was invented in 1972 by Rudolf Bayer. 

It must be noted that as each node requires only 1 bit of space to store the color information, these types of trees show identical memory footprint to the classic (uncolored) binary search tree. 

Rules That Every Red-Black Tree Follows

1. Every node has a color either red or black.
2. The root of the tree 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 descendants NULL nodes has the same number of black nodes.

operations on RB tree 

 

1. INSERTION OPERATION 

 Insert the new node the way it is done in Binary Search Trees. Color the node red , If an inconsistency arises for the red-black tree, fix the tree according to the type of discrepancy.

A discrepancy can decision from a parent and a child both having a red color. This type of discrepancy is determined by the location of the node concerning grandparent, and the color of the sibling of the parent.

  2 .  DELETION  OPERATION 

If the element to be deleted is in a node with only left child, swap this node with one containing the largest element in the left subtree. (This node has no right child). 

If the element to be deleted is in a node with only right child, swap this node with the one containing the smallest element in the right subtree (This node has no left child). 

If the element to be deleted is in a node with both a left child and a right child, then swap in any of the above two ways. While swapping, swap only the keys but not the colors.

Why Red-Black Trees?

Most of the BST operations (e.g., search, max, min, insert, delete , Etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. 

If we make sure that the height of the tree remains O(log n) after every insertion and deletion, then we can guarantee an upper bound of O(log n) for all these operations. The height of a Red-Black tree is always O(log n) where n is the number of nodes in the tree. 

 Time complexity

Thus, the power of a red-black tree is that the average and worst-case scenario to search, insert, and delete from the tree is always O(log n) time, guaranteed. 

The space complexity of a red-black tree is no different from a BST, and depends on the number of total nodes: O(n).

AVL tree VS  RB tree 

on the basis of :

1.  Binary search tree

The Red-Black tree is a binary search tree, and the AVL tree is also a binary search tree.

2. Rules

The following rules are applied in a Red-Black Tree:

1. The node in a Red-Black tree is either red or black in color.
2. The color of the root node should be black.
3. The adjacent nodes should not be red. In other words, we can say that the red node cannot have red children, but the black node can have black children.
4. There should be the same number of black nodes in every path; then, only a tree can be considered a Red-Black tree.
5. The external nodes are the nil nodes, which are always black in color.

Rule of the AVL tree:

Every node should have the balance factor either as -1, 0 or 1.

3. How can the tree be considered as a balanced tree or not?

In the case of a Red-Black tree, if all the above rules are satisfied, provided that a tree is a binary search tree, then the tree is said to be a Red-black tree.

In the case of the AVL tree, if the balance factor is -1, 0, or 1, then the above tree is said to be an AVL tree.

4. Tools used for balancing

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

1. Recoloring
2. Rotation

If the tree is not balanced, then one tool is used for balancing the tree in the AVL tree:

       1. Rotation          

5. Efficient for which operation

In the case of the Red-Black tree, the insertion and deletion operations are efficient. If the tree gets balanced through the recoloring, then insertion and deletion operations are efficient in the Red-Black tree.

In the case of the AVL tree, the searching operation is efficient as it requires only one tool to balance the tree.

6. Time complexity

In the Red-Black tree case, the time complexity for all the operations, i.e., insertion, deletion, and searching is O(logn).

In the case of AVL tree, the time complexity for all the operations, i.e., insertion, deletion, and searching is O(logn).

Tabular difference between AVL and RB tree 

    Application of AVL tree 

• The height of the AVL tree is always balanced. The height never grows beyond log N, where N is the total number of nodes in the tree.
• It gives better search time complexity when compared to simple Binary Search trees.
• AVL trees have self-balancing capabilities. 
• AVL trees are mostly used for in-memory sorts of sets and dictionaries. 
• AVL trees are also used extensively in database applications in which insertions and deletions are fewer but there are frequent lookups for data required.

Application of RB tree 

• Real-world uses of red-black trees include TreeSet, TreeMap, and Hashmap in the Java Collections Library. Also, the Completely Fair Scheduler in the Linux kernel uses this data structure.
•  Linux also uses red-black trees in the mmap and munmap operations for file/memory mapping.
• A red-black tree is a particular implementation of a self-balancing binary search tree, and today it seems to be the most popular choice of implementation. 
• Binary search trees are used to implement finite maps, where you store a set of keys with associated values.