In computer science, a red–black tree is a kind of self-balancing binary search tree. Each node stores an extra bit representing "color" ("red" or "black"), used to ensure that the tree remains balanced during insertions and deletions.
Binary search trees:Can balance using rotation,but we have no algorithm for doing so(yet).
2·3 trees. Balanced by construction, i.e.no rotations required.
What is the maximum height of the corresponding LLRB?
o TotaI height is H (black) + H + 1 (red)
= 2H + 1
Red black tree is actually a 2-3 tree, .
． Right red link —> rotate left.
． two consecutive left links -> rotate right.
． Red left and red right -> flip.