empty }; // Get the child direction (∈ { LEFT, RIGHT }) // of the non-root non-NIL RBnode* N: #define childDir(N) ( N == (N->parent)->right ? RIGHT : LEFT ) RBnode* RotateDirRoot( RBtree* T, // red–black tree RBnode* P, // root of subtree (may be the root of T) int dir) { // dir ∈ { LEFT, RIGHT } RBnode* G = P->parent; RBnode* S = P->child[1-dir]; RBnode* C; assert(S != NIL); // pointer to true node required C = S->child[dir]; P->child[1-dir] = C; if (C != NIL) C->parent = P; S->child[ dir] = P; P->parent = S; S->parent = G; if (G != NULL) G->child[ P == G->right ? RIGHT : LEFT ] = S; else T->root = S; return S; // new root of subtree } #define RotateDir(N,dir) RotateDirRoot(T,N,dir) #define RotateLeft(N) RotateDirRoot(T,N,LEFT) #define RotateRight(N) RotateDirRoot(T,N,RIGHT) Notes to the sample code and diagrams of insertion and removal The proposal breaks down both, insertion and removal (not mentioning some very simple cases), into six constellations of nodes, edges and colors, which are called cases. The proposal contains for both, insertion and removal, exactly one case that advances one black level closer to the root and loops, the other five cases rebalance the tree of their own. The more complicated cases are pictured in a diagram. The variable N denotes the current node, which is labeled N in the diagrams. symbolises a red node and a (non-NIL) black node (of black height ≥ 1), symbolises the color red or black of a non-NIL node, but the same color throughout the same diagram. NIL nodes are not represented in the diagrams. A diagram contains three columns and two to four actions. The left column shows the first iteration, the right column the higher iterations, the middle column shows the segmentation of a case into its different actions. The action "entry" shows the constellation of nodes with their colors which defines a case and mostly violates some of the requirements.A blue border rings the current node N and the other nodes are labeled according to their relation to N. If a rotation is considered useful, this is pictured in the next action, which is labeled "rotation". If some recoloring is considered useful, this is pictured in the next action, which is labeled "color". If there is still some need to repair, the cases make use of code of other cases and this after