Algorithms Summary Points – Part 8: Intro To Red Black Trees

This note has some summary points from my study of algorithms and algorithmic analysis. If you have little or no idea of the concepts I will talk about, this note may not be so helpful to you. I only post these here to serve as a quick note or as a refresher about these concepts should the need arise. In that case, I suggest you take an advanced course on algorithms and data structures first.  Nevertheless, if you are interested in discussing any of the concepts here I will be glad to be of help.

Red Black Trees

Red black Trees 

  • Guarantees the height of the tree is always O (log n), where n is the number of nodes in the tree. 
  • Properties are: 
  • All nodes are either red or black 
  • The root node is red 
  • When a node is red, its children are black. 
  • For every black node, every path from the node to a null reference has the same number of black nodes. 
  • Facts to know when inserting 
  • If we have an outer grandchild violation, 
  • Change color G and P 
  • Rotate the G and P to lift X 
  • If we have an inner violation, 
  • Change the color of G and X 
  • Rotate P and X, lifting X 
  • Rotate G and X lifting X 
  • Nodes are always inserted as red 

Leave a Reply

Your email address will not be published. Required fields are marked *