The Two Rules

• No red-red: a red node cannot have a red child
• Equal black-height on every root-to-leaf path
• Together these bound height at 2·log(n+1)
• Looser than AVL, so writes are cheaper and reads slightly slower

Knowledge Check