Red-Black Tree

overview

Summary

red_black_tree is a binary_search_tree that stays roughly balanced using node colors. Facts to remember: every node is red or black. The root is black. All nil_leaves are black. No red_red parent child. Every path from a node to a leaf has the same black_height. Insert and delete fix violations with rotations and recoloring. Typical performance is O_log_n for search, insert, and delete.