Skip to main content

What Is Red-Black Tree

                          Red-Black Tree

What is Red-Black Tree ?

  • Red Black Tree : A Red Black Tree is a kind of Self-Balancing binary search Tree in Computer Science . 
  • Properties : 
                           1)  Root node is always Black if Root Node is red then you have to change into black.
                          2) each node either red or black .
                          3) All leaves ( Nil ) are black .
                          4) if a node is red then it's both children is black .
                          5) every path from a given node to any its descendant nil node contains the same number of black nodes .


red black tree,red-black tree,red-black trees,red–black tree,tree,red black tree deletion,binary search tree,trees,red black trees,red-black,red black tree rotate,red black tree türkçe,red-black tree tutorial,red-black tree deletion,red-black trees - 2 - insertion,red-black trees in javascript,data structure,rb tree,data structures,red black tree code,red black tree intro,what is red black tree



  • Time Complexity : worst case = O( log n )
  • Space Complexity : Worst case = O( n )
  • Insertion : Insertion is very similar manner as a binary search tree . Insertion Follows few's property  
                                                       1) N is the root node , i.e , first node of the red black tree
                                                       2) N is parent (p) is black .
                                                       3) P is red and N is uncle (U) is red
                                                       4) p is red and u is black .
  • Application : Red Black tree Worst case time complexity is O( log n ) for insertion , deletion and searching . that is why many data structure are used in Computational geometry can be based on red black trees and completely Fair Scheduler used in current Linux Kernels. now day's it is used in java 8 .
Labels:

Comments

Post a Comment