Fundamentals of Red-Black Trees
Explore the fundamentals of red-black trees, including their structural properties, relationship to 2-4 trees, and how to maintain balance through add and remove operations. Learn key subroutines like pushBlack, pullBlack, and rotations to efficiently manage tree color and structure.
Red-Black trees and 2-4 trees
At first it might seem surprising that a red-black tree can be efficiently updated to maintain the black-height and no-red-edge properties, and it seems unusual to even consider these as useful properties. However, red-black trees were designed to be an efficient simulation of – trees as binary trees.
Refer to the below figure.
Consider any red-black tree, , having ...