deleteFixup()

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

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

inlineprivate

Definition at line 170 of file rbtree.h.

                                                 {
        while ((x != mRoot) && (x == nullptr || x->color == Color::kBlack)) {
            if (x == (xParent ? xParent->left : nullptr)) {
                RBNode* w = xParent ? xParent->right : nullptr;
                if (w && w->color == Color::kRed) {
                    w->color = Color::kBlack;
                    if (xParent) { xParent->color = Color::kRed; rotateLeft(xParent); }
                    w = xParent ? xParent->right : nullptr;
                }
                bool wLeftBlack = (!w || !w->left || w->left->color == Color::kBlack);
                bool wRightBlack = (!w || !w->right || w->right->color == Color::kBlack);
                if (wLeftBlack && wRightBlack) {
                    if (w) w->color = Color::kRed;
                    x = xParent;
                    xParent = xParent ? xParent->parent : nullptr;
                } else {
                    if (!w || (w->right == nullptr || w->right->color == Color::kBlack)) {
                        if (w && w->left) w->left->color = Color::kBlack;
                        if (w) { w->color = Color::kRed; rotateRight(w); }
                        w = xParent ? xParent->right : nullptr;
                    }
                    if (w) w->color = xParent ? xParent->color : Color::kBlack;
                    if (xParent) xParent->color = Color::kBlack;
                    if (w && w->right) w->right->color = Color::kBlack;
                    if (xParent) rotateLeft(xParent);
                    x = mRoot;
                }
            } else {
                RBNode* w = xParent ? xParent->left : nullptr;
                if (w && w->color == Color::kRed) {
                    w->color = Color::kBlack;
                    if (xParent) { xParent->color = Color::kRed; rotateRight(xParent); }
                    w = xParent ? xParent->left : nullptr;
                }
                bool wRightBlack = (!w || !w->right || w->right->color == Color::kBlack);
                bool wLeftBlack = (!w || !w->left || w->left->color == Color::kBlack);
                if (wRightBlack && wLeftBlack) {
                    if (w) w->color = Color::kRed;
                    x = xParent;
                    xParent = xParent ? xParent->parent : nullptr;
                } else {
                    if (!w || (w->left == nullptr || w->left->color == Color::kBlack)) {
                        if (w && w->right) w->right->color = Color::kBlack;
                        if (w) { w->color = Color::kRed; rotateLeft(w); }
                        w = xParent ? xParent->left : nullptr;
                    }
                    if (w) w->color = xParent ? xParent->color : Color::kBlack;
                    if (xParent) xParent->color = Color::kBlack;
                    if (w && w->left) w->left->color = Color::kBlack;
                    if (xParent) rotateRight(xParent);
                    x = mRoot;
                }
            }
        }
        if (x) x->color = Color::kBlack;
    }

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

Here is the caller graph for this function: