Java Implementations
Last updated
Was this helpful?
Last updated
Was this helpful?
Observation. Search is the same as for elementary BST ( ignore color ).
Invariants: Maintains symmetric order and perfect black balance.
Basic Strategy: Maintain 1-1 correspondence with 2-3 trees by applying elementary red-black BST operations.
Do standard BST insert; color new link red
If new red link is a right link, rotate left.
Example: Insert ' C '
Do standard BST insert; color new link red.
Rotate to balance the 4-node ( if needed ).
Flip colors to pass red link up one level.
Rotate to make lean left (if needed).
Example: Inserting ' H '
Do standard BST insert; color new link red.
Rotate to balance the 4-node ( if needed ).
Flip colors to pass red link up one level.
Rotate to make lean left (if needed).
Repeat case 1, case 2 ( if needed ).
Example:
Delete operations are bit complicated.