deleteFixup()

template<typename T, typename Compare = less<T>, typename Allocator = allocator_slab<char>>

void fl::RedBlackTree< T, Compare, Allocator >::deleteFixup ( Node * x, Node * xParent )

inlineprivate

Definition at line 163 of file rbtree.h.

                                             {
        while ((x != root_) && (x == nullptr || x->color == BLACK)) {
            if (x == (xParent ? xParent->left : nullptr)) {
                Node* w = xParent ? xParent->right : nullptr;
                if (w && w->color == RED) {
                    w->color = BLACK;
                    if (xParent) { xParent->color = RED; rotateLeft(xParent); }
                    w = xParent ? xParent->right : nullptr;
                }
                bool wLeftBlack = (!w || !w->left || w->left->color == BLACK);
                bool wRightBlack = (!w || !w->right || w->right->color == BLACK);
                if (wLeftBlack && wRightBlack) {
                    if (w) w->color = RED;
                    x = xParent;
                    xParent = xParent ? xParent->parent : nullptr;
                } else {
                    if (!w || (w->right == nullptr || w->right->color == BLACK)) {
                        if (w && w->left) w->left->color = BLACK;
                        if (w) { w->color = RED; rotateRight(w); }
                        w = xParent ? xParent->right : nullptr;
                    }
                    if (w) w->color = xParent ? xParent->color : BLACK;
                    if (xParent) xParent->color = BLACK;
                    if (w && w->right) w->right->color = BLACK;
                    if (xParent) rotateLeft(xParent);
                    x = root_;
                }
            } else {
                Node* w = xParent ? xParent->left : nullptr;
                if (w && w->color == RED) {
                    w->color = BLACK;
                    if (xParent) { xParent->color = RED; rotateRight(xParent); }
                    w = xParent ? xParent->left : nullptr;
                }
                bool wRightBlack = (!w || !w->right || w->right->color == BLACK);
                bool wLeftBlack = (!w || !w->left || w->left->color == BLACK);
                if (wRightBlack && wLeftBlack) {
                    if (w) w->color = RED;
                    x = xParent;
                    xParent = xParent ? xParent->parent : nullptr;
                } else {
                    if (!w || (w->left == nullptr || w->left->color == BLACK)) {
                        if (w && w->right) w->right->color = BLACK;
                        if (w) { w->color = RED; rotateLeft(w); }
                        w = xParent ? xParent->left : nullptr;
                    }
                    if (w) w->color = xParent ? xParent->color : BLACK;
                    if (xParent) xParent->color = BLACK;
                    if (w && w->left) w->left->color = BLACK;
                    if (xParent) rotateRight(xParent);
                    x = root_;
                }
            }
        }
        if (x) x->color = BLACK;
    }

Referenced by fl::RedBlackTree< value_type, PairCompare, Allocator >::erase().

Here is the caller graph for this function: