- {
- gl_oset_node_t sibling = parent->right;
- /* sibling's black-height is >= 1. In particular,
- sibling != NULL.
-
- parent
- / \
- child sibling
- bh bh+1
- */
-
- if (sibling->color == RED)
- {
- /* sibling is RED, hence parent is BLACK and sibling's children
- are non-NULL and BLACK.
-
- parent sibling
- bh+2 bh+2
- / \ / \
- child sibling --> parent SR
- bh bh+1 bh+1 bh+1
- / \ / \
- SL SR child SL
- bh+1 bh+1 bh bh+1
- */
- *parentp = rotate_left (parent, sibling);
- parent->color = RED;
- sibling->color = BLACK;
-
- /* Concentrate on the subtree of parent. The new sibling is
- one of the old sibling's children, and known to be BLACK. */
- parentp = &sibling->left;
- sibling = parent->right;
- }
- /* Now we know that sibling is BLACK.
-
- parent
- / \
- child sibling
- bh bh+1
- */
- if (sibling->right != NULL && sibling->right->color == RED)
- {
- /*
- parent sibling
- bh+1|bh+2 bh+1|bh+2
- / \ / \
- child sibling --> parent SR
- bh bh+1 bh+1 bh+1
- / \ / \
- SL SR child SL
- bh bh bh bh
- */
- *parentp = rotate_left (parent, sibling);
- sibling->color = parent->color;
- parent->color = BLACK;
- sibling->right->color = BLACK;
- return;
- }
- else if (sibling->left != NULL && sibling->left->color == RED)
- {
- /*
- parent parent
- bh+1|bh+2 bh+1|bh+2
- / \ / \
- child sibling --> child SL
- bh bh+1 bh bh+1
- / \ / \
- SL SR SLL sibling
- bh bh bh bh
- / \ / \
- SLL SLR SLR SR
- bh bh bh bh
-
- where SLL, SLR, SR are all black.
- */
- parent->right = rotate_right (sibling->left, sibling);
- /* Change sibling from BLACK to RED and SL from RED to BLACK. */
- sibling->color = RED;
- sibling = parent->right;
- sibling->color = BLACK;
-
- /* Now do as in the previous case. */
- *parentp = rotate_left (parent, sibling);
- sibling->color = parent->color;
- parent->color = BLACK;
- sibling->right->color = BLACK;
- return;
- }
- else
- {
- if (parent->color == BLACK)
- {
- /* Change sibling from BLACK to RED. Then the entire
- subtree at parent has decreased its black-height.
- parent parent
- bh+2 bh+1
- / \ / \
- child sibling --> child sibling
- bh bh+1 bh bh
- */
- sibling->color = RED;
-
- child = parent;
- }
- else
- {
- /* Change parent from RED to BLACK, but compensate by
- changing sibling from BLACK to RED.
- parent parent
- bh+1 bh+1
- / \ / \
- child sibling --> child sibling
- bh bh+1 bh bh
- */
- parent->color = BLACK;
- sibling->color = RED;
- return;
- }
- }
- }
+ {
+ gl_oset_node_t sibling = parent->right;
+ /* sibling's black-height is >= 1. In particular,
+ sibling != NULL.
+
+ parent
+ / \
+ child sibling
+ bh bh+1
+ */
+
+ if (sibling->color == RED)
+ {
+ /* sibling is RED, hence parent is BLACK and sibling's children
+ are non-NULL and BLACK.
+
+ parent sibling
+ bh+2 bh+2
+ / \ / \
+ child sibling --> parent SR
+ bh bh+1 bh+1 bh+1
+ / \ / \
+ SL SR child SL
+ bh+1 bh+1 bh bh+1
+ */
+ *parentp = rotate_left (parent, sibling);
+ parent->color = RED;
+ sibling->color = BLACK;
+
+ /* Concentrate on the subtree of parent. The new sibling is
+ one of the old sibling's children, and known to be BLACK. */
+ parentp = &sibling->left;
+ sibling = parent->right;
+ }
+ /* Now we know that sibling is BLACK.
+
+ parent
+ / \
+ child sibling
+ bh bh+1
+ */
+ if (sibling->right != NULL && sibling->right->color == RED)
+ {
+ /*
+ parent sibling
+ bh+1|bh+2 bh+1|bh+2
+ / \ / \
+ child sibling --> parent SR
+ bh bh+1 bh+1 bh+1
+ / \ / \
+ SL SR child SL
+ bh bh bh bh
+ */
+ *parentp = rotate_left (parent, sibling);
+ sibling->color = parent->color;
+ parent->color = BLACK;
+ sibling->right->color = BLACK;
+ return;
+ }
+ else if (sibling->left != NULL && sibling->left->color == RED)
+ {
+ /*
+ parent parent
+ bh+1|bh+2 bh+1|bh+2
+ / \ / \
+ child sibling --> child SL
+ bh bh+1 bh bh+1
+ / \ / \
+ SL SR SLL sibling
+ bh bh bh bh
+ / \ / \
+ SLL SLR SLR SR
+ bh bh bh bh
+
+ where SLL, SLR, SR are all black.
+ */
+ parent->right = rotate_right (sibling->left, sibling);
+ /* Change sibling from BLACK to RED and SL from RED to BLACK. */
+ sibling->color = RED;
+ sibling = parent->right;
+ sibling->color = BLACK;
+
+ /* Now do as in the previous case. */
+ *parentp = rotate_left (parent, sibling);
+ sibling->color = parent->color;
+ parent->color = BLACK;
+ sibling->right->color = BLACK;
+ return;
+ }
+ else
+ {
+ if (parent->color == BLACK)
+ {
+ /* Change sibling from BLACK to RED. Then the entire
+ subtree at parent has decreased its black-height.
+ parent parent
+ bh+2 bh+1
+ / \ / \
+ child sibling --> child sibling
+ bh bh+1 bh bh
+ */
+ sibling->color = RED;
+
+ child = parent;
+ }
+ else
+ {
+ /* Change parent from RED to BLACK, but compensate by
+ changing sibling from BLACK to RED.
+ parent parent
+ bh+1 bh+1
+ / \ / \
+ child sibling --> child sibling
+ bh bh+1 bh bh
+ */
+ parent->color = BLACK;
+ sibling->color = RED;
+ return;
+ }
+ }
+ }