AVL Trees vs RB Trees with Application

AVL vs RB Trees ,which is Good ? With Applications 

               To understand this comparison let's understand the BST , because both AVL and the RB trees are the type of  BST which is Binary Search tree which also a type of Tree data structure which further used for storing a particular data more sorted.

Binary Search Trees (BST) :

      

So it is a BST where each circle containing value in it represents or called as node where first blue circle is called as Root node or starting point of tree .After the root node below structures are known as sub-trees.

       The rule of BST is ;

 All the values less than the root node value are placed on left side of  root and all the value greater than the root are placed on the right as shown in the figure 

ex. if you want to find a particular element ex. 3 first from root you have to go to left because 3<4 and after that you have to go right because 3>2 to find 3.

           But the problem with BST are they are can be imbalanced as shown in the figure because of that it make difficult to find particular element which increase time complexity which is required time to complete task.

          To overcome this problem AVL trees and RB trees which are the type of BST means both follow the rules of BST .These two are invented which are more balanced and which is best among them for that we will see the comparison.

AVL trees :

                 AVL are the BST which is named after Adelson-Velsky and Landis.

               This is self balancing BST in which difference between height of  two child subtree (balance factor)  is not other than the values -1,0,1 which is the only rule of AVL . 

   

              

 RB Trees :

           RB trees are also known as Red Black tree which are also self balancing trees and the rules for BST to be RB trees are as follows:

1) Every node is either black or red but the root node is always black.

2)  Every leaf which is nil is in black.

3) If node is red then the children are black or their can't be adjacent red nodes.

4) Every path from a node to any of it's adjacent NIL node has same number of black nodes.

Which is best ?

                 In case of  AVL trees it is more height restricted so searching happens more easily in case of  AVL trees ,

                Where in RB trees it is less height restricted than AVL but insertion and deletion

of elements are much more faster than AVL trees because ,

                In AVL trees insertion and deletion of elements are done by the technique of

" 1)   rotation of nodes  " 

               while in RB trees insertion an deletion process is done by rotation technique and also" 2) recoloring technique " after rotation provide faster insertion and deletion  

           "  If your need is fast searching in database you can go for AVL trees and if you want to add and delete more data in your data base go for the RB trees. "

APPLICATIONS :

a) AVL trees

1) In AVL trees it is used for storing the information in most efficient manner.

 2)It is also used in many search application where the data is continuously entering or leaving.

3)AVL trees are also useful in security concerns and to parallel code

4)It is also useful in creating new type of data structures. 

 b) RB trees 

5) RB trees are fair scheduler in Linux kernel.

6) It is also used to keep track the virtual memory segment for a process the start address of range server as the key.

7) RB trees are also valuable in "functional programming".

8) It is also used in computational geometrical data structures.

                

             Share your feedbacks in comment section and tell us which is better according to you .

     THANK YOU !