Red Black Tree Insertion

For more information, you can view this material: Reading(Optional)

Introduction of RBT

Valid Red-Black Trees are regular BSTs with following properties:

• Each node is either red or black
• The root node is black
• No red nodes have red children
• All paths from the root to a null child have the same number of black nodes (black height of the tree)

RBT Insertion

Procedure

1. Insert new value using BST insertion algorithm
2. Color the new node red
3. Check Red-Black tree properties and restore if necessary

Properties could be violated after insert

• Each node is either red or black
• The root node is black
• No red nodes have red children
• All paths from the root to a null child have the same number of black nodes (black height of the tree)

Repair Operation

Case 1: If aunt is black (or null), rotate and color swap

Case 2: If aunt is red, recolor

Let's practice!

Insert numbers in the following order: 7, 14, 18, 23, 1, 11, 20, 29, 25, 27

Following the level-order traversal, fill in the following box with your answer, and hit submit button

Here is the answer key: Answer key