3.4.3　map的原理

map内部自建一棵红黑树（一种非严格意义上的平衡二叉树），这棵树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。这里简单讲下红黑树的含义。

先来看下算法导论对R-B Tree的介绍：红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接*衡的。红黑树，作为一棵二叉查找树，满足二叉查找树的一般性质。下面，来了解下二叉查找树的一般性质。

二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：①若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③任意节点的左、右子树也分别为二叉查找树；④没有键值相等的节点（no duplicate node）。

因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)。

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(logn)。

它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢？这就引出了红黑树的5个性质：①每个结点要么是红的要么是黑的；②根结点是黑的；③每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的；④如果一个结点是红的，那么它的两个儿子都是黑的；⑤对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(logn)”这一结论成立的原因。

如图3-3所示，是一颗红黑树（图3-3引自wikipedia：http://t.cn/hgvH1l）。

 

图3-3　红黑树

当在对红黑树进行插入和删除等操作时，对树做了修改可能会破坏红黑树的性质。为了继续保持红黑树的性质，可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即通过修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后继续保持它的性质或平衡的目的。

树的旋转分为左旋和右旋，下面借助图来介绍一下左旋和右旋这两种操作。

1）左旋操作（图3-4）。

 

图3.4　左旋操作示意图

如图3-4所示，当在某个结点pivot上，做左旋操作时，假设它的右孩子y不是NIL[T]，pivot可以为任何不是NIL[T]的左子结点。左旋以pivot到Y之间的链为“支轴”进行，它使Y成为该子树的新根，而Y的左孩子b则成为pivot的右孩子，在代码中表示如下所示。

LeftRoate(T, x)

y ← x.right            // y是x的右孩子

x.right ← y.left             // y的左孩子成为x的右孩子

if y.left ≠ T.nil

    y.left.p ← x

y.p ← x.p                   // y成为x的父亲

if x.p = T.nil

    then T.root ← y

else if x = x.p.left

    then x.p.left ← y

else x.p.right ← y

y.left ← x              // x作为y的左孩子

x.p ← y

2）右旋操作（图3-5）。

 

图3-5　右旋操作示意图

右旋与左旋差不多，再此不做详细介绍。

树在经过左旋右旋之后，树的搜索性质保持不变，但树的红黑性质被破坏了，所以红黑树插入和删除数据后，需要利用旋转与颜色重涂来重新恢复树的红黑性质。

由于map的内部实现过于复杂，本章不做详细介绍，有兴趣的读者可自行在网上查资料。