Skip to main content

Red-Black Tree

Learn Red-Black Tree (Advanced Data Structures, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Red-Black Tree A red-black tree is a balanced BST where every node is colored red or black and these rules hold: (1) the root is black ; (2) a red node never has a red child ; (3) every path from a node down to a null link has the same number of black nodes . These rules keep the longest path at most twice the shortest, so the height is O(log n) . The version below is the left-leaning red-black tree , which is equivalent to a 2-3 tree and needs just three operations: rotate left, rotate right and flip colors . Java's TreeMap and TreeSet use a red-black tree.

More lessons in Advanced Data Structures