What is the problem
You’ll either:
- be given an existing RB tree and asked to insert a set of nodes into it.
- be given a set of nodes and asked to insert them into an empty RB tree.
Before you begin
In both cases, going through each given node, u should:
-
place it in its correct position in the current tree, and color it red.
-
mark it as Z, its parent as P, its uncle as U, and its grandparent as G.
-
follow the strategy below.
The keys
Symbols Key
Arrows/lines Key
The Strategy
NOTE
I let P and U be the right and left children of G respectively while showing the strategy. However, this strategy will work just as well if they were reversed.
