# 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