STL中红黑树的实现

以下代码来自：xtree

左旋：

void _Lrotate(_Nodeptr _Wherenode) noexcept { // promote right node to root of subtree
        _Nodeptr _Pnode    = _Wherenode->_Right;
        _Wherenode->_Right = _Pnode->_Left;

        if (!_Pnode->_Left->_Isnil) {
            _Pnode->_Left->_Parent = _Wherenode;
        }

        _Pnode->_Parent = _Wherenode->_Parent;

        if (_Wherenode == _Myhead->_Parent) {
            _Myhead->_Parent = _Pnode;
        } else if (_Wherenode == _Wherenode->_Parent->_Left) {
            _Wherenode->_Parent->_Left = _Pnode;
        } else {
            _Wherenode->_Parent->_Right = _Pnode;
        }

        _Pnode->_Left       = _Wherenode;
        _Wherenode->_Parent = _Pnode;
    }

 

右旋：

void _Rrotate(_Nodeptr _Wherenode) noexcept { // promote left node to root of subtree
        _Nodeptr _Pnode   = _Wherenode->_Left;
        _Wherenode->_Left = _Pnode->_Right;

        if (!_Pnode->_Right->_Isnil) {
            _Pnode->_Right->_Parent = _Wherenode;
        }

        _Pnode->_Parent = _Wherenode->_Parent;

        if (_Wherenode == _Myhead->_Parent) {
            _Myhead->_Parent = _Pnode;
        } else if (_Wherenode == _Wherenode->_Parent->_Right) {
            _Wherenode->_Parent->_Right = _Pnode;
        } else {
            _Wherenode->_Parent->_Left = _Pnode;
        }

        _Pnode->_Right      = _Wherenode;
        _Wherenode->_Parent = _Pnode;
    }

 

 

_Nodeptr _Extract(_Unchecked_const_iterator _Where) noexcept {
    _Nodeptr _Erasednode = _Where._Ptr; // node to erase
    ++_Where; // save successor iterator for return

    _Nodeptr _Fixnode; // the node to recolor as needed
    _Nodeptr _Fixnodeparent; // parent of _Fixnode (which may be nil)
    _Nodeptr _Pnode = _Erasednode;

    if (_Pnode->_Left->_Isnil) {
        _Fixnode = _Pnode->_Right; // stitch up right subtree
    } else if (_Pnode->_Right->_Isnil) {
        _Fixnode = _Pnode->_Left; // stitch up left subtree
    } else { // two subtrees, must lift successor node to replace erased
        _Pnode   = _Where._Ptr; // _Pnode is successor node
        _Fixnode = _Pnode->_Right; // _Fixnode is only subtree
    }

    if (_Pnode == _Erasednode) { // at most one subtree, relink it
        _Fixnodeparent = _Erasednode->_Parent;
        if (!_Fixnode->_Isnil) {
            _Fixnode->_Parent = _Fixnodeparent; // link up
        }

        if (_Myhead->_Parent == _Erasednode) {
            _Myhead->_Parent = _Fixnode; // link down from root
        } else if (_Fixnodeparent->_Left == _Erasednode) {
            _Fixnodeparent->_Left = _Fixnode; // link down to left
        } else {
            _Fixnodeparent->_Right = _Fixnode; // link down to right
        }

        if (_Myhead->_Left == _Erasednode) {
            _Myhead->_Left = _Fixnode->_Isnil ? _Fixnodeparent // smallest is parent of erased node
                                              : _Min(_Fixnode); // smallest in relinked subtree
        }

        if (_Myhead->_Right == _Erasednode) {
            _Myhead->_Right = _Fixnode->_Isnil ? _Fixnodeparent // largest is parent of erased node
                                               : _Max(_Fixnode); // largest in relinked subtree
        }
    } else { // erased has two subtrees, _Pnode is successor to erased
        _Erasednode->_Left->_Parent = _Pnode; // link left up
        _Pnode->_Left               = _Erasednode->_Left; // link successor down

        if (_Pnode == _Erasednode->_Right) {
            _Fixnodeparent = _Pnode; // successor is next to erased
        } else { // successor further down, link in place of erased
            _Fixnodeparent = _Pnode->_Parent; // parent is successor's
            if (!_Fixnode->_Isnil) {
                _Fixnode->_Parent = _Fixnodeparent; // link fix up
            }

            _Fixnodeparent->_Left        = _Fixnode; // link fix down
            _Pnode->_Right               = _Erasednode->_Right; // link next down
            _Erasednode->_Right->_Parent = _Pnode; // right up
        }

        if (_Myhead->_Parent == _Erasednode) {
            _Myhead->_Parent = _Pnode; // link down from root
        } else if (_Erasednode->_Parent->_Left == _Erasednode) {
            _Erasednode->_Parent->_Left = _Pnode; // link down to left
        } else {
            _Erasednode->_Parent->_Right = _Pnode; // link down to right
        }

        _Pnode->_Parent = _Erasednode->_Parent; // link successor up
        _STD swap(_Pnode->_Color, _Erasednode->_Color); // recolor it
    }

    if (_Erasednode->_Color == _Black) { // erasing black link, must recolor/rebalance tree
        for (; _Fixnode != _Myhead->_Parent && _Fixnode->_Color == _Black; _Fixnodeparent = _Fixnode->_Parent) {
            if (_Fixnode == _Fixnodeparent->_Left) { // fixup left subtree
                _Pnode = _Fixnodeparent->_Right;
                if (_Pnode->_Color == _Red) { // rotate red up from right subtree
                    _Pnode->_Color         = _Black;
                    _Fixnodeparent->_Color = _Red;
                    _Lrotate(_Fixnodeparent);
                    _Pnode = _Fixnodeparent->_Right;
                }

                if (_Pnode->_Isnil) {
                    _Fixnode = _Fixnodeparent; // shouldn't happen
                } else if (_Pnode->_Left->_Color == _Black
                           && _Pnode->_Right->_Color == _Black) { // redden right subtree with black children
                    _Pnode->_Color = _Red;
                    _Fixnode       = _Fixnodeparent;
                } else { // must rearrange right subtree
                    if (_Pnode->_Right->_Color == _Black) { // rotate red up from left sub-subtree
                        _Pnode->_Left->_Color = _Black;
                        _Pnode->_Color        = _Red;
                        _Rrotate(_Pnode);
                        _Pnode = _Fixnodeparent->_Right;
                    }

                    _Pnode->_Color         = _Fixnodeparent->_Color;
                    _Fixnodeparent->_Color = _Black;
                    _Pnode->_Right->_Color = _Black;
                    _Lrotate(_Fixnodeparent);
                    break; // tree now recolored/rebalanced
                }
            } else { // fixup right subtree
                _Pnode = _Fixnodeparent->_Left;
                if (_Pnode->_Color == _Red) { // rotate red up from left subtree
                    _Pnode->_Color         = _Black;
                    _Fixnodeparent->_Color = _Red;
                    _Rrotate(_Fixnodeparent);
                    _Pnode = _Fixnodeparent->_Left;
                }

                if (_Pnode->_Isnil) {
                    _Fixnode = _Fixnodeparent; // shouldn't happen
                } else if (_Pnode->_Right->_Color == _Black
                           && _Pnode->_Left->_Color == _Black) { // redden left subtree with black children
                    _Pnode->_Color = _Red;
                    _Fixnode       = _Fixnodeparent;
                } else { // must rearrange left subtree
                    if (_Pnode->_Left->_Color == _Black) { // rotate red up from right sub-subtree
                        _Pnode->_Right->_Color = _Black;
                        _Pnode->_Color         = _Red;
                        _Lrotate(_Pnode);
                        _Pnode = _Fixnodeparent->_Left;
                    }

                    _Pnode->_Color         = _Fixnodeparent->_Color;
                    _Fixnodeparent->_Color = _Black;
                    _Pnode->_Left->_Color  = _Black;
                    _Rrotate(_Fixnodeparent);
                    break; // tree now recolored/rebalanced
                }
            }
        }

        _Fixnode->_Color = _Black; // stopping node is black
    }

    if (0 < _Mysize) {
        --_Mysize;
    }

    return _Erasednode;
}

 

插入元素

_Nodeptr _Insert_node(const _Tree_id<_Nodeptr> _Loc, const _Nodeptr _Newnode) noexcept {
    ++_Mysize;
    const auto _Head  = _Myhead;
    _Newnode->_Parent = _Loc._Parent;
    if (_Loc._Parent == _Head) { // first node in tree, just set head values
        _Head->_Left     = _Newnode;
        _Head->_Parent   = _Newnode;
        _Head->_Right    = _Newnode;
        _Newnode->_Color = _Black; // the root is black
        return _Newnode;
    }

    _STL_INTERNAL_CHECK(_Loc._Child != _Tree_child::_Unused);
    if (_Loc._Child == _Tree_child::_Right) { // add to right of _Loc._Parent
        _STL_INTERNAL_CHECK(_Loc._Parent->_Right->_Isnil);
        _Loc._Parent->_Right = _Newnode;
        if (_Loc._Parent == _Head->_Right) { // remember rightmost node
            _Head->_Right = _Newnode;
        }
    } else { // add to left of _Loc._Parent
        _STL_INTERNAL_CHECK(_Loc._Parent->_Left->_Isnil);
        _Loc._Parent->_Left = _Newnode;
        if (_Loc._Parent == _Head->_Left) { // remember leftmost node
            _Head->_Left = _Newnode;
        }
    }

    for (_Nodeptr _Pnode = _Newnode; _Pnode->_Parent->_Color == _Red;) {
        if (_Pnode->_Parent == _Pnode->_Parent->_Parent->_Left) { // fixup red-red in left subtree
            const auto _Parent_sibling = _Pnode->_Parent->_Parent->_Right;
            if (_Parent_sibling->_Color == _Red) { // parent's sibling has two red children, blacken both
                _Pnode->_Parent->_Color          = _Black;
                _Parent_sibling->_Color          = _Black;
                _Pnode->_Parent->_Parent->_Color = _Red;
                _Pnode                           = _Pnode->_Parent->_Parent;
            } else { // parent's sibling has red and black children
                if (_Pnode == _Pnode->_Parent->_Right) { // rotate right child to left
                    _Pnode = _Pnode->_Parent;
                    _Lrotate(_Pnode);
                }

                _Pnode->_Parent->_Color          = _Black; // propagate red up
                _Pnode->_Parent->_Parent->_Color = _Red;
                _Rrotate(_Pnode->_Parent->_Parent);
            }
        } else { // fixup red-red in right subtree
            const auto _Parent_sibling = _Pnode->_Parent->_Parent->_Left;
            if (_Parent_sibling->_Color == _Red) { // parent's sibling has two red children, blacken both
                _Pnode->_Parent->_Color          = _Black;
                _Parent_sibling->_Color          = _Black;
                _Pnode->_Parent->_Parent->_Color = _Red;
                _Pnode                           = _Pnode->_Parent->_Parent;
            } else { // parent's sibling has red and black children
                if (_Pnode == _Pnode->_Parent->_Left) { // rotate left child to right
                    _Pnode = _Pnode->_Parent;
                    _Rrotate(_Pnode);
                }

                _Pnode->_Parent->_Color          = _Black; // propagate red up
                _Pnode->_Parent->_Parent->_Color = _Red;
                _Lrotate(_Pnode->_Parent->_Parent);
            }
        }
    }

    _Head->_Parent->_Color = _Black; // root is always black
    return _Newnode;
}