STL中map、set的数据结构及底层实现
摘要：本文列出几个基本的
的问题，通过解答这些问题讲解了
联容器内部的数据结构，最后提出了关于
UNIX/LINUX
自带平衡二叉树库函数和
选择问题，并分析了
的优势之处。对于希望深入学习
和希望了解
等关联容器底层数据结构的朋友来说，有一定的参考价值。
中标准而安全的数组。只能在
增加数据。
（双端队列
double-endedqueue
在功能上和
相似，但是可以在前后
两端向其中添加数据。
游标一次只可以移动一步。如果你对链表已经很熟悉，那么
则是一个双向链表（每个节点有指向前驱和指向后继的两个指针）。
包含了经过排序了的数据，这些数据的值
必须是唯一的。
经过排序了的二元组的集合，
中的每个元素都是由两个值组成，其
（键值，一个
中的键值必须是唯一的）是在排序或搜索时使用，它的值可以
在容器中重新获取；而另一个值是该元素关联的数值。比如，除了可以
这样找到一个数据，
还可以通过
ar["banana"]="overripe"
这样的方法找
到一个数据。如果你想获得其中的元素信息，通过输入元素的全名就可以轻松实现。
（多重集）
）相似，然而其中的值不要求必须是唯一的（即可以
有重复）。
（多重映射）
）相似，然而其中的键值不要求必须是唯一的（即
可以有重复）。
的使用虽不复杂，但也有一些不易理解的地方，如：
的插入删除效率比用其他序列容器高？
之后，以前保存的
不会失效？
函数来预分配数据？
当数据元素增多时（
个比较），
的插入和搜索速度变化如
或许有得人能回答出来大概原因，但要彻底明白，还需要了解
的底层数据结构。
之所以得到广泛的赞誉，也被很多人使用，不只是提供了像
vector,string,list
等方便的容器，更重要的是
封装了许多复杂的数据结构算法和大量常用数据结构操作。
封装数组，
封装了链表，
封装了二叉树等，在封装这些数据结构的
按照程序员的使用习惯，以成员函数方式提供的常用操作，如：插入、排序、删
除、查找等。让用户在
使用过程中，并不会感到陌生。
中标准关联容器
set,multiset,map,multimap
内部采用的就是一种非常高效
的平衡检索二叉树：红黑树，也成为
(Red-BlackTree)
树的统计性能要好于一
般的平衡二叉树
有些书籍根据作者姓名，
Adelson-Velskii
，将其称为
选择作为了关联容器的内部结构。本文并不会介绍详细
以及他们的优劣，关于
树的详细实现参看红黑树
理论与实现
。本文针对开始
提出的几个问题的回答，来向大家简单介绍
的底层数据结构。
的插入删除效率比用其他序列容器高？
大部分人说，很简单，因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确
容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，
指向父节点和子节点。结构图可能如下：
因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，
稍做变换后把指向删除节点的指针指向其他节点就
了。这里的一切操作就是指针换来换
去，和内存移动没有关系。
之后，以前保存的
不会失效？
看见了上面答案的解释，你应该已经可以很容易解释这个问题。
这里就相当于指向
节点的指针，内存没有变，指向内存的指针怎么会失效呢
当然被删除的那个元素本身已经
来说，每一次删除和插入，指针都有可能失效，调用
在尾部插入也是如此。因为为了保证内部数据的连续存放，
指向的那块内存在删除
和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时
容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大
的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内
存指针自然就不可用了。特别时在和
等算法在一起使用的时候，牢记这个原则：不要
使用过期的
函数来预分配数据？
我以前也这么问，究其原理来说时，引起它的原因在于在
内部存储的已经不是
元素本身了，而是包含元素的节点。也就是说
内部使用的
Data,Compare,Alloc&
声明的时候从参数中传入的
map&int,int,less&int&,Alloc&int&&
Alloc&int&,
而是通过了转换的
转换的方法时在内部通过
Alloc&int&::rebind
重新定义了新的节点分配器，详细的实现参
看彻底学习
。其实你就记住一点，在
内面的分配器已经发
生了变化，
方法你就不要奢望了。
当数据元素增多时（
个比较），
的插入和搜索速度变化如何？
如果你知道
的关系你应该就彻底了解这个答案。在
中查找是使用二分查
找，也就是说，如果有
个元素，最多需要比较
次就能找到结果，有
个元素，最多
次。那么有
个呢？最多比较的次数为
次，如果是
个元素呢？最多不过
次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了
的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。
最后，对于
还要提的就是它们和一个
语言包装库的效率比较。在许多
平台下，都有一个库叫
，里面就提供类似于以下声明的函数
voidtree_init(void**tree);
相关资料推荐
在STL的set或map容器中使用类作key时的结构
当前资料暂无简介~
微软标准模板库STL，帮助大家更高效实现各类经典算法
C语言数据结构中链表的具体实现, C语言, 数据结构 ,链表, 具体实现 ,初始化, 创建, 查找, 插入 ,删除 ,清空, 销毁
这几个文件包括了C++的介绍以及stl的使用等，其中电脑合订本介绍了（walkdriving）。
编程相关的技巧知识收集
java中list、set和map_的区别
STM32F103的串口通讯例程
STM32F103下音乐演示例程
数据结构C语言实现系列
数据结构C语言实现系列[1]——线性表
在此可输入您对该资料的评论~
资料阅读排行
(window.slotbydup=window.slotbydup || []).push({
id: '2371234',
container: s,
size: '300,250',
display: 'inlay-fix'
该用户的其它资料
请选择举报的类型
赌博犯罪类
资料评价：
所需积分：1&&国之画&&&& &&&&&&
&& &&&&&&&&&&&&&&
鲁ICP备号-4
打开技术之扣，分享程序人生！数据结构（8）
为什么选择红黑树作为底层实现
红黑树是一种类平衡树, 但它不是高度的平衡树, 但平衡的效果已经很好了. 补充说明另一种 AVL 树, 我之前的博文: 《编程珠玑，字字珠玑》读书笔记完结篇——AVL树
用过 STL map 么, 你用过 linux 么(这个说大了), 他们都有红黑树的应用. 当你对搜索的效率要求较高，并且数据经常改动的情景，你可以用红黑树, 也就是 map.
至于, 为什么不用 AVL 树作为底层实现, 那是因为 AVL 树是高度平衡的树, 而每一次对树的修改, 都要 rebalance, 这里的开销会比红黑树大. 红黑树插入只要两次旋转, 删除至多三次旋转. 但不可否认的是, AVL 树搜索的效率是非常稳定的. 选取红黑树, 我认为是一种折中的方案.
黑体字是不正确的，对AVL插一个node或者删一个node，显然不需要每次都做rotation来维持balance。且AVL插入最多也只需要2次旋转。
下面是我的回答：
如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。
其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。
map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。
最坏情况下，AVL树有最多O(logN)次旋转，而红黑树最多三次。当然，这是个结论，谁能给出一个证明啊。。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：4029次
排名：千里之外
原创：48篇
(11)(10)(1)(18)(14)(3)数据结构（5）
原文连接：
红黑树并没有想象的那么难, 初学者觉得晦涩难读可能是因为情况太多. 红黑树的情况可以通过归结, 通过合并来得到更少的情况, 如此可以加深对红黑树的理解. 网络上的大部分红黑树的讲解因为没有「合并」. 红黑树的五个性质:
性质1. 节点是红色或黑色。
性质2. 根是黑色。
性质3. 所有叶子都是黑色（叶子是NIL节点）。
性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。
红黑树的数据结构
摘自 sgi stl 红黑树数据结构定义:
typedef bool _Rb_tree_Color_
const _Rb_tree_Color_type _S_rb_tree_red =
const _Rb_tree_Color_type _S_rb_tree_black =
struct _Rb_tree_node_base
typedef _Rb_tree_Color_type _Color_
typedef _Rb_tree_node_base* _Base_
_Color_type _M_
_Base_ptr _M_
_Base_ptr _M_
_Base_ptr _M_
static _Base_ptr _S_minimum(_Base_ptr __x)
while (__x-&_M_left != 0) __x = __x-&_M_
return __x;
static _Base_ptr _S_maximum(_Base_ptr __x)
while (__x-&_M_right != 0) __x = __x-&_M_
return __x;
template &class _Value&
struct _Rb_tree_node : public _Rb_tree_node_base
typedef _Rb_tree_node&_Value&* _Link_
_Value _M_value_
二叉搜索树的插入删除操作
在展开红黑树之前, 首先来看看普通二叉搜索树的插入和删除. 插入很容易理解, 比当前值大就往右走, 比当前值小就往左走. 详细展开的是删除操作.
二叉树的删除操作有一个技巧, 即在查找到需要删除的节点 X; 接着我们找到要么在它的左子树中的最大元素节点 M、要么在它的右子树中的最小元素节点 M, 并交换(M,X). 此时, M 节点必然至多只有一个孩子; 最后一个步骤就是用 M 的子节点代替 M 节点就完成了. 所以, 所有的删除操作最后都会归结为删除一个至多只有一个孩子的节点, 而我们删除这个节点后, 用它的孩子替换就好了. 将会看到 sgi stl map 就是这样的策略.
在红黑树删除操作讲解中, 我们假设代替 M 的节点是 N(下面的讲述不再出现 M).
红黑树的插入
插入新节点总是红色节点, 因为不会破坏性质 5, 尽可能维持所有性质.
假设, 新插入的节点为 N, N 节点的父节点为 P, P 的兄弟(N 的叔父)节点为 U, P 的父亲(N 的爷爷)节点为 G. 所以有如下的印象图:
插入节点的关键是:
插入算法详解如下, 走一遍红黑树维持其性质的过程:
第 0.0 种情况, N 为根节点, 直接 N-&黑. over
第 0.1 种情况, N 的父节点为黑色, 这不违反红黑树的五种性质. over
第 1 种情况, N,P,U 都红(G 肯定黑). 策略: G-&红, N,P-&黑. 此时, G 红, 如果 G 的父亲也是红, 性质又被破坏了, HACK: 可以将 GPUN 看成一个新的红色 N 节点, 如此递归调整下去; 特俗的, 如果碰巧将根节点染成了红色, 可以在算法的最后强制 root-&黑.
第 2 种情况, P 为红, N 为 P 右孩子, N 为红, U 为黑或缺少. 策略: 旋转变换, 从而进入下一种情况:
第 3 种情况, 可能由第二种变化而来, 但不是一定: P 为红, N 为 P 左孩子, N 为红. 策略: 旋转, 交换 P,G 颜色, 调整后, 因为 P 为黑色, 所以不怕 P 的父节点是红色的情况. over
红黑树的插入就为上面的三种情况. 你可以做镜像变换从而得到其他的情况.
红黑树的删除
假设 N 节点见上面普通二叉树删除中的定义, P 为 N 父节点, S 为 N 的兄弟节点, SL,SR 分别是 S 的左右子节点. 有如下印象图:
没有任何的孩子!
删除节点的关键是:
删除算法详解如下, 走一遍红黑树维持其性质的过程:
第 0.0 情况, N 为根节点. over
第 0.1 情况, 删除的节点为红. over
第 0.2 情况, 删除节点为黑, N 为红.&策略: N-&黑, 重新平衡.&over
第 1 情况, N,P,S,SR,SL 都黑.&策略: S-&红.&通过 PN,PS 的黑色节点数量相同了, 但会比其他路径多一个, 解决的方法是在 P 上从情况 0 开始继续调整. 为什么要这样呢? HANKS: 因为既然 PN,PS 路径上的黑节点数量相同而且比其他路径会少一个黑节点, 那何不将其整体看成了一个 N 节点! 这是递归原理.
第 2 情况, S 红, 根据红黑树性质 P,SL,SR 一定黑.&策略:&旋转, 交换 P,S 颜色.&处理后关注的范围缩小, 下面的情况对应下面的框图, 算法从框图重新开始, 进入下一个情况:
第 2.1 情况, S,SL,SR 都黑.&策略: P-&黑. S-&红,&因为通过 N 的路径多了一个黑节点, 通过 S 的黑节点个数不变, 所以维持了性质 5. over. 将看到, sgi stl map 源代码中将第 2.1 和第 1 情况合并成一种情况, 下节展开.
第 2.2.1 情况, S,SR 黑, SL 红.&策略: 旋转, 变换 SL,S 颜色.&从而又进入下一种情况:
第 2.2.2 情况, S 黑, SR 红.&策略: 旋转, 交换 S,P 颜色, SR-&黑色, 重新获得平衡.
上面情况标号 X.X.X 并不是说这些关系是嵌套的, 只是这样展开容易理解. 此时, 解释三个地方:
红黑树删除重新调整伪代码如下:
// 第 0.0 情况, N 为根节点. over
if N.parent == NULL:
// 第 0.1 情况, 删除的节点为红. over
if color == RED:
// 第 0.2 情况, 删除节点为黑, N 为红, 简单变换: N-&黑, 重新平衡. over
if color == BLACK && N.color == RED:
N.color = BLACK;
// 第 1 种情况, N,P,S,SR,SL 都黑. 策略: S-&红. 通过 N,S 的黑色节点数量相同了, 但会比其他路径多一个, 解决的方法是在 P 上从情况 0 开始继续调整.
if N,P,S,SR,SL.color == BLACK:
S.color = RED;
// 调整节点关系
N.parent = P.parent
S = P.paernt.another_child
SL = S.left_child
SR = S.right_child
// 第 2 情况, S 红, 根据红黑树性质 P,SR,SL 一定黑. 旋转, 交换 P,S 颜色. 此时关注的范围缩小, 下面的情况对应下面的框图, 算法从框图重新开始.
if S.color == RED:
rotate(P);
swap(P.color,S.color);
// 调整节点关系
S = P.another_child
SL = S.left_child
SR = S.right_child
// 第 2.1 情况, S,SL,SR 都黑. 策略: P-&黑. S-&红, 因为通过 N 的路径多了一个黑节点, 通过 S 的黑节点个数不变, 所以维持了性质 5. over. 将看到, sgi stl map 源代码中将第 2.1 和第 1 情况合并成一种情况, 下节展开.
if S,SL,SR.color == BLACK:
P.color = BLACK;
S.color = RED;
// 第 2.2.1 情况, S,SR 黑, SL 红. 策略: 旋转, 变换 SL,S 颜色. 从而又进入下一种情况:
S,SR.color == BLACK && SL.color == RED:
rotate(P);
swap(S.color,SL.color);
// 调整节点关系
SL = S.left_child
SR = S.right_child
// 第 2.2.2 情况, S 黑, SR 红. 策略: 旋转, 交换 S,P 颜色.
if S.color == BLACK && SR.color == RED:
rotate(P);
swap(P.color,S.color);
所以, 插入的情况只有三种, 删除的情况只有两种. 上面的分析, 做镜像处理, 就能得到插入删除的全部算法, 脑补吧.&从上面的分析来看, 红黑树具有以下特性:&插入删除操作都是 0(lnN), 且最多旋转三次.
SGI STL map 实现概述
根据上一节的红黑树分析, 结合 sgi stl map 的实现, 看看红黑树的源码是如何实现的. 以下主要以代码的注释为主.
sgi stl map 底层实现是&_Rb_tree类, 为了方便管理,&_Rb_tree 内置了&_M_header, 用于记录红黑树中的根节点, 最小节点和最大节点. 在插入删除中都会对其进行维护. 找到一副美艳的图片:
我只会展开插入和删除的代码.&_Rb_tree 有 insert_unique() 和 insert_equal() 两种, 前者不允许有重复值, 后者可以.&insert_unique() 判断是否有重复值的方法利用了二叉搜索树的性质. 细节请参看下面的代码.
为什么选择红黑树作为底层实现
红黑树是一种类平衡树, 但它不是高度的平衡树, 但平衡的效果已经很好了. 补充说明另一种 AVL 树, 我之前的博文:&
用过 STL map 么, 你用过 linux 么(这个说大了), 他们都有红黑树的应用. 当你对搜索的效率要求较高，并且数据经常改动的情景，你可以用红黑树, 也就是 map.
至于, 为什么不用 AVL 树作为底层实现, 那是因为 AVL 树是高度平衡的树, 而每一次对树的修改, 都要 rebalance, 这里的开销会比红黑树大. 红黑树插入只要两次旋转, 删除至多三次旋转. 但不可否认的是, AVL 树搜索的效率是非常稳定的. 选取红黑树, 我认为是一种折中的方案.
红黑树源代码剖析
// sgi stl _Rb_tree 插入算法 insert_equal() 实现.
// 策略概述: insert_equal() 在红黑树找到自己的位置,
// 然后交由 _M_insert() 来处理接下来的工作.
// _M_insert() 会将节点插入红黑树中, 接着调整红黑树,
// 维持性质.
template &class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc&
typename _Rb_tree&_Key,_Value,_KeyOfValue,_Compare,_Alloc&::iterator
_Rb_tree&_Key,_Value,_KeyOfValue,_Compare,_Alloc&
::insert_equal(const _Value& __v)
// 在红黑树中有头结点和根节点的概念, 头结点位于根节点之上,
// 头结点只为管理而存在, 根节点是真正存储数据的地方. 头结点和根节点互为父节点,
// 是一种实现的技巧.
_Link_type __y = _M_ // 指向头结点
_Link_type __x = _M_root(); // _M_header-&_M_parent, 即指向根节点
// 寻找插入的位置
while (__x != 0) {
__y = __x;
// 小于当前节点要走左边, 大于等于当前节点走右边
__x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
_S_left(__x) : _S_right(__x);
// __x 为需要插入的节点的位置, __y 为其父节点
return _M_insert(__x, __y, __v);
// sgi stl _Rb_tree 插入算法 insert_unique() 实现.
// 策略概述: insert_unique() 同样也在红黑树中找到自己的位置; 我们知道,
// 如果小于等于当前节点会往右走, 所以遇到一个相同键值的节点后, 会往右走一步,
// 接下来一直往左走, 所以下面的实现会对往左走的情况做特殊的处理.
template &class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc&
pair&typename _Rb_tree&_Key,_Value,_KeyOfValue,_Compare,_Alloc&::iterator,
_Rb_tree&_Key,_Value,_KeyOfValue,_Compare,_Alloc&
::insert_unique(const _Value& __v)
_Link_type __y = _M_ // 指向头结点
_Link_type __x = _M_root(); // 指向根节点, 可能为空
bool __comp =
// 寻找插入的位置
while (__x != 0) {
__y = __x;
__comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
// 小于当前节点要走左边, 大于等于当前节点走右边
__x = __comp ? _S_left(__x) : _S_right(__x);
iterator __j = iterator(__y); // 在 __y 上建立迭代器
// 我认为下面判断树中是否有存在键值的情况有点绕,
// 它充分利用了二叉搜索树的性质, 如此做很 hack, 但不易理解.
// 要特别注意往左边插入的情况.
// 下面的 if 语句是比 __x 小走左边的情况: 会发现, 如果插入一个已存在的键的话,
// __y 最终会定位到已存在键的右子树的最左子树.
// 譬如, 红黑树中已经存在一个键为 100 的节点, 其右孩子节点为 101,
// 此时如果再插入键为 100 的节点, 因为 100&=100, 所以会往右走到达 101 节点,
// 有 100&101, 继而往左走, 会一直往左走.大家稍微画一个例子就能理解.
if (__comp)
// 特殊情况, 如果 __j 指向了最左孩子, 那么肯定要插入新节点.
if (__j == begin())
return pair&iterator,bool&(_M_insert(__x, __y, __v), true);
// 其他情况, 这个时候也是往左边插入, 如果存在重复的键值,
// 那么 --__j 能定位到此重复的键的节点.
// HACKS: 这里比较的是 __j 和 __v, 如果存在键值, 那么 __j == __v,
// 会跳过 if 语句. 否则执行插入. 也就是说如果存在重复的键, 那么 __j
// 的值肯定是等于 __v
if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
return pair&iterator,bool&(_M_insert(__x, __y, __v), true);
// 此时 __y.value = __v, 不允许插入, 返回键值所在位置
return pair&iterator,bool&(__j, false);
// _M_insert() 是真正执行插入的地方.
// 策略概述: 插入策略已经在上篇中详述, 可以根据上篇文章的描述,
// 和下面代码的注释, 加深对红黑树插入算法里理解
template &class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc&
typename _Rb_tree&_Key,_Value,_KeyOfValue,_Compare,_Alloc&::iterator
_Rb_tree&_Key,_Value,_KeyOfValue,_Compare,_Alloc&
::_M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Value& __v)
_Link_type __x = (_Link_type) __x_; // 新节点插入的位置.
// 关于 __x 的疑问:
// 1. 它被放到下面的, 第一个 if 语句中, 我觉得是没有必要的,
// 因为从调用 _M_insert() 的函数来看, __x 总是为空.
// 2. 既然 __x 是新节点插入的位置, 那么为什么不直接在 __x 上创建节点,
// 还要在下面通过比较来决定新节点是左孩子还是右孩子;
// 不如直接用指针的指针或者指针的引用来完成, 省去了下面的判断.
_Link_type __y = (_Link_type) __y_; // 新节点的父节点
_Link_type __z; // 新节点的位置
if (__y == _M_header || __x != 0 ||
_M_key_compare(_KeyOfValue()(__v), _S_key(__y))) {
// 新节点应该为左孩子
__z = _M_create_node(__v);
_S_left(__y) = __z;
// also makes _M_leftmost() = __z
when __y == _M_header
if (__y == _M_header) {
_M_root() = __z;
_M_rightmost() = __z;
else if (__y == _M_leftmost())
_M_leftmost() = __z;
// maintain _M_leftmost() pointing to min node
// 新节点应该为右孩子
__z = _M_create_node(__v);
_S_right(__y) = __z;
if (__y == _M_rightmost())
_M_rightmost() = __z;
// maintain _M_rightmost() pointing to max node
_S_parent(__z) = __y;
_S_left(__z) = 0;
_S_right(__z) = 0;
// 重新调整
_Rb_tree_rebalance(__z, _M_header-&_M_parent);
// 更新红黑树节点数
++_M_node_
// 返回迭代器类型
return iterator(__z);
// 插入新节点后, 可能会破坏红黑树性质, _Rb_tree_rebalance() 负责维持性质.
// __x 新插入的节点
// __root 根节点
// 策略概述: 红黑树插入重新调整的策略已经在上篇中讲述,
// 可以结合上篇文章和这里的代码注释,
// 理解红黑树的插入算法.
inline void
_Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
// 将新插入的节点染成红色
__x-&_M_color = _S_rb_tree_
while (__x != __root && __x-&_M_parent-&_M_color == _S_rb_tree_red) {
// __x 的父节点也是红色的情况. 提示: 如果是黑色节点, 不会破坏红黑树性质.
if (__x-&_M_parent == __x-&_M_parent-&_M_parent-&_M_left) {
// 叔父节点
_Rb_tree_node_base* __y = __x-&_M_parent-&_M_parent-&_M_
if (__y && __y-&_M_color == _S_rb_tree_red) {
// 第 1 种情况, N,P,U 都红(G 肯定黑).
// 策略: G-&红, N,P-&黑. 此时, G 红, 如果 G 的父亲也是红, 性质又被破坏了,
// HACK: 可以将 GPUN 看成一个新的红色 N 节点, 如此递归调整下去;
// 特俗的, 如果碰巧将根节点染成了红色, 可以在算法的最后强制 root-&红.
__x-&_M_parent-&_M_color = _S_rb_tree_
__y-&_M_color = _S_rb_tree_
__x-&_M_parent-&_M_parent-&_M_color = _S_rb_tree_
__x = __x-&_M_parent-&_M_
if (__x == __x-&_M_parent-&_M_right) {
// 第 2 种情况, P 为红, N 为 P 右孩子, U 为黑或缺少.
// 策略: 旋转变换, 从而进入下一种情况:
__x = __x-&_M_
_Rb_tree_rotate_left(__x, __root);
// 第 3 种情况, 可能由第二种变化而来, 但不是一定: P 为红, N 为红.
// 策略: 旋转, 交换 P,G 颜色, 调整后, 因为 P 为黑色, 所以不怕
// P 的父节点是红色的情况. over
__x-&_M_parent-&_M_color = _S_rb_tree_
__x-&_M_parent-&_M_parent-&_M_color = _S_rb_tree_
_Rb_tree_rotate_right(__x-&_M_parent-&_M_parent, __root);
else { // 下面的代码是镜像得出的, 脑补吧.
_Rb_tree_node_base* __y = __x-&_M_parent-&_M_parent-&_M_
if (__y && __y-&_M_color == _S_rb_tree_red) {
__x-&_M_parent-&_M_color = _S_rb_tree_
__y-&_M_color = _S_rb_tree_
__x-&_M_parent-&_M_parent-&_M_color = _S_rb_tree_
__x = __x-&_M_parent-&_M_
if (__x == __x-&_M_parent-&_M_left) {
__x = __x-&_M_
_Rb_tree_rotate_right(__x, __root);
__x-&_M_parent-&_M_color = _S_rb_tree_
__x-&_M_parent-&_M_parent-&_M_color = _S_rb_tree_
_Rb_tree_rotate_left(__x-&_M_parent-&_M_parent, __root);
__root-&_M_color = _S_rb_tree_
// 删除算法, 直接调用底层的删除实现 _Rb_tree_rebalance_for_erase().
template &class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc&
inline void _Rb_tree&_Key,_Value,_KeyOfValue,_Compare,_Alloc&
::erase(iterator __position)
_Link_type __y =
(_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
_M_header-&_M_parent,
_M_header-&_M_left,
_M_header-&_M_right);
destroy_node(__y);
--_M_node_
// 删除节点底层实现, 删除可能会破坏红黑树性质,
// _Rb_tree_rebalance()
// 负责维持性质. 其中:
// __z 需要删除的节点
// __root 根节点
// __leftmost 红黑树内部数据, 即最左子树
// __rightmost 红黑树内部数据, 即最右子树
// 策略概述: _Rb_tree_rebalance_for_erase() 会根据
// 删除节点的位置在红黑树中找到顶替删除节点的节点,
// 即无非是删除节点左子树的最大节点或右子树中的最小节点,
// 此处用的是有一种策略. 接着, 会调整红黑树以维持性质.
// 调整的算法已经在上篇文章中详述, 可以根据上篇文章的描述
// 和此篇的代码注释, 加深对红黑树删除算法的理解.
inline _Rb_tree_node_base*
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z,
_Rb_tree_node_base*& __root,
_Rb_tree_node_base*& __leftmost,
_Rb_tree_node_base*& __rightmost)
// __z 是要删除的节点
// __y 最终会指向要删除的节点
_Rb_tree_node_base* __y = __z;
_Rb_tree_node_base* __x = 0;
// 记录 N 节点的父节点
_Rb_tree_node_base* __x_parent = 0;
// 只有一个孩子或者没有孩子的情况
if (__y-&_M_left == 0)
// __z has at most one non-null child. y == z.
__x = __y-&_M_
// __x might be null.
if (__y-&_M_right == 0)
// __z has exactly one non-null child. y == z.
__x = __y-&_M_
// __x is not null.
// 有两个非空孩子
// __z has two non-null children.
Set __y to
__y = __y-&_M_
__z's successor.
__x might be null.
// __y 取右孩子中的最小节点, __x 记录他的右孩子(可能存在右孩子)
while (__y-&_M_left != 0)
__y = __y-&_M_
__x = __y-&_M_
// __y != __z 说明有两个非空孩子的情况,
// 此时的删除策略就和文中提到的普通二叉搜索树删除策略一样:
// __y 记录了 __z 右子树中最小的节点
// __x 记录了 __y 的右孩子
// 用 __y 顶替 __z 的位置, __x 顶替 __y 的位置, 最后用 __y 指向 __z,
// 从而 __y 指向了要删除的节点
if (__y != __z) {
// relink y in place of z.
y is z's successor
// 将 __z 的记录转移至 __y 节点
__z-&_M_left-&_M_parent = __y;
__y-&_M_left = __z-&_M_
// 如果 __y 不是 __z 的右孩子, __z-&_M_right 有左孩子
if (__y != __z-&_M_right) {
__x_parent = __y-&_M_
// 如果 __y 有右孩子 __x, 必须有那个 __x 替换 __y 的位置
// 替换 __y 的位置
__x-&_M_parent = __y-&_M_
__y-&_M_parent-&_M_left = __x;
// __y must be a child of _M_left
__y-&_M_right = __z-&_M_
__z-&_M_right-&_M_parent = __y;
// __y == __z-&_M_right
__x_parent = __y;
// 如果 __z 是根节点
if (__root == __z)
__root = __y;
// __z 是左孩子
else if (__z-&_M_parent-&_M_left == __z)
__z-&_M_parent-&_M_left = __y;
// __z 是右孩子
__z-&_M_parent-&_M_right = __y;
__y-&_M_parent = __z-&_M_
// 交换需要删除节点 __z 和 替换节点 __y 的颜色
__STD::swap(__y-&_M_color, __z-&_M_color);
__y = __z;
// __y now points to node to be actually deleted
// __y == __z 说明至多一个孩子
// __y == __z
__x_parent = __y-&_M_
if (__x) __x-&_M_parent = __y-&_M_
// 将 __z 的父亲指向 __x
if (__root == __z)
__root = __x;
if (__z-&_M_parent-&_M_left == __z)
__z-&_M_parent-&_M_left = __x;
__z-&_M_parent-&_M_right = __x;
// __leftmost 和 __rightmost 是红黑树的内部数据, 因为 __z 可能是
// __leftmost 或者 __rightmost, 因此需要更新.
if (__leftmost == __z)
if (__z-&_M_right == 0)
// __z-&_M_left must be null also
// __z 左右孩子都为空, 没有孩子
__leftmost = __z-&_M_
// makes __leftmost == _M_header if __z == __root
__leftmost = _Rb_tree_node_base::_S_minimum(__x);
if (__rightmost == __z)
if (__z-&_M_left == 0)
// __z-&_M_right must be null also
__rightmost = __z-&_M_
// makes __rightmost == _M_header if __z == __root
// __x == __z-&_M_left
__rightmost = _Rb_tree_node_base::_S_maximum(__x);
// __y 同样已经指向要删除的节点
// __y 指向要删除的节点
// __x 即为 N 节点
// __x_parent 指向 __x 的父亲, 即 N 节点的父亲
if (__y-&_M_color != _S_rb_tree_red) {
// __y 的颜色为黑色的时候, 会破坏红黑树性质
while (__x != __root && (__x == 0 || __x-&_M_color == _S_rb_tree_black))
// __x 不为红色, 即为空或者为黑. 提示: 如果 __x 是红色, 直接将 __x 替换成黑色
if (__x == __x_parent-&_M_left) { // 如果 __x 是左孩子
_Rb_tree_node_base* __w = __x_parent-&_M_ // 兄弟节点
if (__w-&_M_color == _S_rb_tree_red) {
//第 2 情况, S 红, 根据红黑树性质P,SL,SR 一定黑.
// 策略: 旋转, 交换 P,S 颜色.
__w-&_M_color = _S_rb_tree_
__x_parent-&_M_color = _S_rb_tree_ // 交换颜色
_Rb_tree_rotate_left(__x_parent, __root); // 旋转
__w = __x_parent-&_M_ // 调整关系
if ((__w-&_M_left == 0 ||
__w-&_M_left-&_M_color == _S_rb_tree_black) &&
(__w-&_M_right == 0 ||
__w-&_M_right-&_M_color == _S_rb_tree_black)) {
// 提示: 这是 第 1 情况和第 2.1 情况的合并, 因为处理的过程是一样的.
// 但他们的情况还是要分门别类的. 已经在文章中详细支出,
// 似乎大多数的博文中没有提到这一点.
// 第 1 情况, N,P,S,SR,SL 都黑.
// 策略: S-&红. 通过 PN,PS 的黑色节点数量相同了, 但会比其他路径多一个,
// 解决的方法是在 P 上从情况 0 开始继续调整.
// 为什么要这样呢? HACKS: 因为既然 PN,PS
// 路径上的黑节点数量相同而且比其他路径会少一个黑节点,
// 那何不将其整体看成了一个 N 节点! 这是递归原理.
// 第 2.1 情况, S,SL,SR 都黑.
// 策略: P-&黑. S-&红, 因为通过 N 的路径多了一个黑节点,
// 通过 S 的黑节点个数不变, 所以维持了性质 5. over
// 可能大家会有疑问, 不对啊, 2.1 的情况,
// 策略是交换父节点和兄弟节点的颜色, 此时怎么没有对父节点的颜色赋值呢?
// HACKS: 这就是合并情况的好处, 因为就算此时父节点是红色,
// 而且也将兄弟节点颜色改为红色, 你也可以将 PS,PN 看成一个红色的 N 节点,
// 这样在下一个循环当中, 这个 N 节点也会变成黑色. 因为此函数最后有一句话:
// if (__x) __x-&_M_color = _S_rb_tree_
// 合并情况, 节省代码量
// 当然是可以分开写的
// 兄弟节点染成红色
__w-&_M_color = _S_rb_tree_
// 调整关系
__x = __x_
__x_parent = __x_parent-&_M_
if (__w-&_M_right == 0 ||
__w-&_M_right-&_M_color == _S_rb_tree_black) {
// 第 2.2.1 情况, S,SR 黑, SL 红.
// 策略: 旋转, 变换 SL,S 颜色.
if (__w-&_M_left) __w-&_M_left-&_M_color = _S_rb_tree_
__w-&_M_color = _S_rb_tree_
_Rb_tree_rotate_right(__w, __root);
// 调整关系
__w = __x_parent-&_M_
// 第 2.2.2 情况, S 黑, SR 红.
// 策略: 旋转, 交换 S,P 颜色, SR-&黑色, 重新获得平衡.
__w-&_M_color = __x_parent-&_M_
__x_parent-&_M_color = _S_rb_tree_
if (__w-&_M_right) __w-&_M_right-&_M_color = _S_rb_tree_
_Rb_tree_rotate_left(__x_parent, __root);
// 下面的代码是镜像得出的, 脑补吧.
// same as above, with _M_right &-& _M_left.
_Rb_tree_node_base* __w = __x_parent-&_M_
if (__w-&_M_color == _S_rb_tree_red) {
__w-&_M_color = _S_rb_tree_
__x_parent-&_M_color = _S_rb_tree_
_Rb_tree_rotate_right(__x_parent, __root);
__w = __x_parent-&_M_
if ((__w-&_M_right == 0 ||
__w-&_M_right-&_M_color == _S_rb_tree_black) &&
(__w-&_M_left == 0 ||
__w-&_M_left-&_M_color == _S_rb_tree_black)) {
__w-&_M_color = _S_rb_tree_
__x = __x_
__x_parent = __x_parent-&_M_
if (__w-&_M_left == 0 ||
__w-&_M_left-&_M_color == _S_rb_tree_black) {
if (__w-&_M_right) __w-&_M_right-&_M_color = _S_rb_tree_
__w-&_M_color = _S_rb_tree_
_Rb_tree_rotate_left(__w, __root);
__w = __x_parent-&_M_
__w-&_M_color = __x_parent-&_M_
__x_parent-&_M_color = _S_rb_tree_
if (__w-&_M_left) __w-&_M_left-&_M_color = _S_rb_tree_
_Rb_tree_rotate_right(__x_parent, __root);
if (__x) __x-&_M_color = _S_rb_tree_
return __y;
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：2476次
排名：千里之外
转载：12篇
(6)(1)(3)(4)}