Java Implementations
Node Implementation
Search Operation
Observation. Search is the same as for elementary BST ( ignore color ).
Elementary operations
Left Rotation
Right Rotation
Invariants: Maintains symmetric order and perfect black balance.
Color Flip
Insertion
Basic Strategy: Maintain 1-1 correspondence with 2-3 trees by applying elementary red-black BST operations.
Case 1: Into Exactly 2-node
Do standard BST insert; color new link red
If new red link is a right link, rotate left.
Example: Insert ' C '
Case 2: Insert into 3-node
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 '
Passing red links up the tree
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:
Java Implementation
Delete
Delete operations are bit complicated.
Last updated