\u4ee5\u4e0b\u4ee3\u7801\u6765\u81ea\uff1axtree<\/p>\n
\u5de6\u65cb\uff1a<\/p>\n
void _Lrotate(_Nodeptr _Wherenode) noexcept { \/\/ promote right node to root of subtree\r\n _Nodeptr _Pnode = _Wherenode->_Right;\r\n _Wherenode->_Right = _Pnode->_Left;\r\n\r\n if (!_Pnode->_Left->_Isnil) {\r\n _Pnode->_Left->_Parent = _Wherenode;\r\n }\r\n\r\n _Pnode->_Parent = _Wherenode->_Parent;\r\n\r\n if (_Wherenode == _Myhead->_Parent) {\r\n _Myhead->_Parent = _Pnode;\r\n } else if (_Wherenode == _Wherenode->_Parent->_Left) {\r\n _Wherenode->_Parent->_Left = _Pnode;\r\n } else {\r\n _Wherenode->_Parent->_Right = _Pnode;\r\n }\r\n\r\n _Pnode->_Left = _Wherenode;\r\n _Wherenode->_Parent = _Pnode;\r\n }<\/pre>\n <\/p>\n
\u53f3\u65cb\uff1a<\/p>\n
void _Rrotate(_Nodeptr _Wherenode) noexcept { \/\/ promote left node to root of subtree\r\n _Nodeptr _Pnode = _Wherenode->_Left;\r\n _Wherenode->_Left = _Pnode->_Right;\r\n\r\n if (!_Pnode->_Right->_Isnil) {\r\n _Pnode->_Right->_Parent = _Wherenode;\r\n }\r\n\r\n _Pnode->_Parent = _Wherenode->_Parent;\r\n\r\n if (_Wherenode == _Myhead->_Parent) {\r\n _Myhead->_Parent = _Pnode;\r\n } else if (_Wherenode == _Wherenode->_Parent->_Right) {\r\n _Wherenode->_Parent->_Right = _Pnode;\r\n } else {\r\n _Wherenode->_Parent->_Left = _Pnode;\r\n }\r\n\r\n _Pnode->_Right = _Wherenode;\r\n _Wherenode->_Parent = _Pnode;\r\n }<\/pre>\n <\/p>\n
<\/p>\n
_Nodeptr _Extract(_Unchecked_const_iterator _Where) noexcept {\r\n _Nodeptr _Erasednode = _Where._Ptr; \/\/ node to erase\r\n ++_Where; \/\/ save successor iterator for return\r\n\r\n _Nodeptr _Fixnode; \/\/ the node to recolor as needed\r\n _Nodeptr _Fixnodeparent; \/\/ parent of _Fixnode (which may be nil)\r\n _Nodeptr _Pnode = _Erasednode;\r\n\r\n if (_Pnode->_Left->_Isnil) {\r\n _Fixnode = _Pnode->_Right; \/\/ stitch up right subtree\r\n } else if (_Pnode->_Right->_Isnil) {\r\n _Fixnode = _Pnode->_Left; \/\/ stitch up left subtree\r\n } else { \/\/ two subtrees, must lift successor node to replace erased\r\n _Pnode = _Where._Ptr; \/\/ _Pnode is successor node\r\n _Fixnode = _Pnode->_Right; \/\/ _Fixnode is only subtree\r\n }\r\n\r\n if (_Pnode == _Erasednode) { \/\/ at most one subtree, relink it\r\n _Fixnodeparent = _Erasednode->_Parent;\r\n if (!_Fixnode->_Isnil) {\r\n _Fixnode->_Parent = _Fixnodeparent; \/\/ link up\r\n }\r\n\r\n if (_Myhead->_Parent == _Erasednode) {\r\n _Myhead->_Parent = _Fixnode; \/\/ link down from root\r\n } else if (_Fixnodeparent->_Left == _Erasednode) {\r\n _Fixnodeparent->_Left = _Fixnode; \/\/ link down to left\r\n } else {\r\n _Fixnodeparent->_Right = _Fixnode; \/\/ link down to right\r\n }\r\n\r\n if (_Myhead->_Left == _Erasednode) {\r\n _Myhead->_Left = _Fixnode->_Isnil ? _Fixnodeparent \/\/ smallest is parent of erased node\r\n : _Min(_Fixnode); \/\/ smallest in relinked subtree\r\n }\r\n\r\n if (_Myhead->_Right == _Erasednode) {\r\n _Myhead->_Right = _Fixnode->_Isnil ? _Fixnodeparent \/\/ largest is parent of erased node\r\n : _Max(_Fixnode); \/\/ largest in relinked subtree\r\n }\r\n } else { \/\/ erased has two subtrees, _Pnode is successor to erased\r\n _Erasednode->_Left->_Parent = _Pnode; \/\/ link left up\r\n _Pnode->_Left = _Erasednode->_Left; \/\/ link successor down\r\n\r\n if (_Pnode == _Erasednode->_Right) {\r\n _Fixnodeparent = _Pnode; \/\/ successor is next to erased\r\n } else { \/\/ successor further down, link in place of erased\r\n _Fixnodeparent = _Pnode->_Parent; \/\/ parent is successor's\r\n if (!_Fixnode->_Isnil) {\r\n _Fixnode->_Parent = _Fixnodeparent; \/\/ link fix up\r\n }\r\n\r\n _Fixnodeparent->_Left = _Fixnode; \/\/ link fix down\r\n _Pnode->_Right = _Erasednode->_Right; \/\/ link next down\r\n _Erasednode->_Right->_Parent = _Pnode; \/\/ right up\r\n }\r\n\r\n if (_Myhead->_Parent == _Erasednode) {\r\n _Myhead->_Parent = _Pnode; \/\/ link down from root\r\n } else if (_Erasednode->_Parent->_Left == _Erasednode) {\r\n _Erasednode->_Parent->_Left = _Pnode; \/\/ link down to left\r\n } else {\r\n _Erasednode->_Parent->_Right = _Pnode; \/\/ link down to right\r\n }\r\n\r\n _Pnode->_Parent = _Erasednode->_Parent; \/\/ link successor up\r\n _STD swap(_Pnode->_Color, _Erasednode->_Color); \/\/ recolor it\r\n }\r\n\r\n if (_Erasednode->_Color == _Black) { \/\/ erasing black link, must recolor\/rebalance tree\r\n for (; _Fixnode != _Myhead->_Parent && _Fixnode->_Color == _Black; _Fixnodeparent = _Fixnode->_Parent) {\r\n if (_Fixnode == _Fixnodeparent->_Left) { \/\/ fixup left subtree\r\n _Pnode = _Fixnodeparent->_Right;\r\n if (_Pnode->_Color == _Red) { \/\/ rotate red up from right subtree\r\n _Pnode->_Color = _Black;\r\n _Fixnodeparent->_Color = _Red;\r\n _Lrotate(_Fixnodeparent);\r\n _Pnode = _Fixnodeparent->_Right;\r\n }\r\n\r\n if (_Pnode->_Isnil) {\r\n _Fixnode = _Fixnodeparent; \/\/ shouldn't happen\r\n } else if (_Pnode->_Left->_Color == _Black\r\n && _Pnode->_Right->_Color == _Black) { \/\/ redden right subtree with black children\r\n _Pnode->_Color = _Red;\r\n _Fixnode = _Fixnodeparent;\r\n } else { \/\/ must rearrange right subtree\r\n if (_Pnode->_Right->_Color == _Black) { \/\/ rotate red up from left sub-subtree\r\n _Pnode->_Left->_Color = _Black;\r\n _Pnode->_Color = _Red;\r\n _Rrotate(_Pnode);\r\n _Pnode = _Fixnodeparent->_Right;\r\n }\r\n\r\n _Pnode->_Color = _Fixnodeparent->_Color;\r\n _Fixnodeparent->_Color = _Black;\r\n _Pnode->_Right->_Color = _Black;\r\n _Lrotate(_Fixnodeparent);\r\n break; \/\/ tree now recolored\/rebalanced\r\n }\r\n } else { \/\/ fixup right subtree\r\n _Pnode = _Fixnodeparent->_Left;\r\n if (_Pnode->_Color == _Red) { \/\/ rotate red up from left subtree\r\n _Pnode->_Color = _Black;\r\n _Fixnodeparent->_Color = _Red;\r\n _Rrotate(_Fixnodeparent);\r\n _Pnode = _Fixnodeparent->_Left;\r\n }\r\n\r\n if (_Pnode->_Isnil) {\r\n _Fixnode = _Fixnodeparent; \/\/ shouldn't happen\r\n } else if (_Pnode->_Right->_Color == _Black\r\n && _Pnode->_Left->_Color == _Black) { \/\/ redden left subtree with black children\r\n _Pnode->_Color = _Red;\r\n _Fixnode = _Fixnodeparent;\r\n } else { \/\/ must rearrange left subtree\r\n if (_Pnode->_Left->_Color == _Black) { \/\/ rotate red up from right sub-subtree\r\n _Pnode->_Right->_Color = _Black;\r\n _Pnode->_Color = _Red;\r\n _Lrotate(_Pnode);\r\n _Pnode = _Fixnodeparent->_Left;\r\n }\r\n\r\n _Pnode->_Color = _Fixnodeparent->_Color;\r\n _Fixnodeparent->_Color = _Black;\r\n _Pnode->_Left->_Color = _Black;\r\n _Rrotate(_Fixnodeparent);\r\n break; \/\/ tree now recolored\/rebalanced\r\n }\r\n }\r\n }\r\n\r\n _Fixnode->_Color = _Black; \/\/ stopping node is black\r\n }\r\n\r\n if (0 < _Mysize) {\r\n --_Mysize;\r\n }\r\n\r\n return _Erasednode;\r\n}\r\n<\/pre>\n <\/p>\n
\u63d2\u5165\u5143\u7d20<\/p>\n
_Nodeptr _Insert_node(const _Tree_id<_Nodeptr> _Loc, const _Nodeptr _Newnode) noexcept {\r\n ++_Mysize;\r\n const auto _Head = _Myhead;\r\n _Newnode->_Parent = _Loc._Parent;\r\n if (_Loc._Parent == _Head) { \/\/ first node in tree, just set head values\r\n _Head->_Left = _Newnode;\r\n _Head->_Parent = _Newnode;\r\n _Head->_Right = _Newnode;\r\n _Newnode->_Color = _Black; \/\/ the root is black\r\n return _Newnode;\r\n }\r\n\r\n _STL_INTERNAL_CHECK(_Loc._Child != _Tree_child::_Unused);\r\n if (_Loc._Child == _Tree_child::_Right) { \/\/ add to right of _Loc._Parent\r\n _STL_INTERNAL_CHECK(_Loc._Parent->_Right->_Isnil);\r\n _Loc._Parent->_Right = _Newnode;\r\n if (_Loc._Parent == _Head->_Right) { \/\/ remember rightmost node\r\n _Head->_Right = _Newnode;\r\n }\r\n } else { \/\/ add to left of _Loc._Parent\r\n _STL_INTERNAL_CHECK(_Loc._Parent->_Left->_Isnil);\r\n _Loc._Parent->_Left = _Newnode;\r\n if (_Loc._Parent == _Head->_Left) { \/\/ remember leftmost node\r\n _Head->_Left = _Newnode;\r\n }\r\n }\r\n\r\n for (_Nodeptr _Pnode = _Newnode; _Pnode->_Parent->_Color == _Red;) {\r\n if (_Pnode->_Parent == _Pnode->_Parent->_Parent->_Left) { \/\/ fixup red-red in left subtree\r\n const auto _Parent_sibling = _Pnode->_Parent->_Parent->_Right;\r\n if (_Parent_sibling->_Color == _Red) { \/\/ parent's sibling has two red children, blacken both\r\n _Pnode->_Parent->_Color = _Black;\r\n _Parent_sibling->_Color = _Black;\r\n _Pnode->_Parent->_Parent->_Color = _Red;\r\n _Pnode = _Pnode->_Parent->_Parent;\r\n } else { \/\/ parent's sibling has red and black children\r\n if (_Pnode == _Pnode->_Parent->_Right) { \/\/ rotate right child to left\r\n _Pnode = _Pnode->_Parent;\r\n _Lrotate(_Pnode);\r\n }\r\n\r\n _Pnode->_Parent->_Color = _Black; \/\/ propagate red up\r\n _Pnode->_Parent->_Parent->_Color = _Red;\r\n _Rrotate(_Pnode->_Parent->_Parent);\r\n }\r\n } else { \/\/ fixup red-red in right subtree\r\n const auto _Parent_sibling = _Pnode->_Parent->_Parent->_Left;\r\n if (_Parent_sibling->_Color == _Red) { \/\/ parent's sibling has two red children, blacken both\r\n _Pnode->_Parent->_Color = _Black;\r\n _Parent_sibling->_Color = _Black;\r\n _Pnode->_Parent->_Parent->_Color = _Red;\r\n _Pnode = _Pnode->_Parent->_Parent;\r\n } else { \/\/ parent's sibling has red and black children\r\n if (_Pnode == _Pnode->_Parent->_Left) { \/\/ rotate left child to right\r\n _Pnode = _Pnode->_Parent;\r\n _Rrotate(_Pnode);\r\n }\r\n\r\n _Pnode->_Parent->_Color = _Black; \/\/ propagate red up\r\n _Pnode->_Parent->_Parent->_Color = _Red;\r\n _Lrotate(_Pnode->_Parent->_Parent);\r\n }\r\n }\r\n }\r\n\r\n _Head->_Parent->_Color = _Black; \/\/ root is always black\r\n return _Newnode;\r\n}\r\n<\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
\u4ee5\u4e0b\u4ee3\u7801\u6765\u81ea\uff1axtree \u5de6\u65cb\uff1a voi<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[],"tags":[119],"class_list":["post-4575","post","type-post","status-publish","format-standard","hentry","tag-03-"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/4575","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=4575"}],"version-history":[{"count":0,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/4575\/revisions"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=4575"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=4575"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=4575"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}