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