6.1.Redblacktree

This section explains the concept, its importance, and when to use it.

6.1.Redblacktree

RED-BLACK TREES

The running time of BST operations depends on the height of the binary search tree: we should keep the tree balanced in order to get the best performance

Each node is either red or black

Rotations

Every new node is red by default

Case 1:

Case 2:

Case 3:

Case 4:

Worked examples and test cases to understand the algorithm.

Example: