【深度探索 STL】【資料結構】詳解紅黑樹（一）結構及插入

紅黑樹概述

曆史上 AVL 樹流行的另一變種是紅黑樹（red-black tree）。對紅黑樹的操作能保證在最壞情況下動态幾何操作的時間為 O(logN) 。之前介紹過AVL 樹，該樹都是在進行插入和删除操作時通過特定操作保持二叉查找樹的平衡，進而獲得較高的查找性能。但 RB-Tree 出來之後，便很少有應用場合用到 AVL 。

這裡在探索STL源碼時學習紅黑樹的，由于STL中的關聯式容器預設的底層實作都是紅黑樹，以及 Linux 核心中包括程序隊列等結構也是基于紅黑樹的。是以有必要掌握紅黑樹的實作原理和源碼實作。

紅黑樹是二叉查找樹，但在每個節點上增加了一位存儲位表示該節點的顔色，具體可以是 RED 或 BLACK。通過對任一條從根到葉子的路徑上各節點着色方式的限制，紅黑樹確定了沒有一條路徑會比其他路徑長到兩倍，因而基本上是平衡的。它所追求的的是局部平衡而不是AVL樹中的非常嚴格的平衡。

紅黑樹在二叉查找樹的基礎上還必須滿足以下着色規則：

每個節點不是紅色就是黑色
根節點為黑色
如果節點為紅，其子節點必須為黑（一條路徑上不能出現連續的兩個紅色節點）
任一節點至NULL（樹尾端）的任何路徑，所含之黑節點數必須相同

根據規則4，新增節點必須為紅；根據規則3，新增節點之父點必須為黑。當新節點根據二叉查找樹的規則（鍵值大小）到達其插入點，卻未能符合上述條件，就必須調整顔色并旋轉樹形。AVL 樹插入節點後如果不滿足其平衡條件，需要旋轉樹形。紅黑樹并不是基于 AVL 樹的，它是在二叉查找樹的基礎上。

那麼紅黑樹的基本平衡又是如何保證的呢？紅黑樹的着色法則，根據上面的規則，一條路徑上不能出現連續的兩個紅色節點，必須有黑色節點間隔開來，然後紅黑樹的每條路徑中所含黑色節點的數目必須相同，這樣就限制每條路徑之間的高度差，進而達到接近平衡的目的。

插入節點

同 AVL 樹，紅黑樹的插入也要考慮以下幾種情況，然後兼顧上面的着色法則。所有待插入節點初始着色為紅色，最後将根節點重新設定為黑色。

1、空樹

這是最簡單的一種形式，直接添加，着色為黑色（規則2）

2、僅存在根節點（黑色），或待插入節點 X 的父節點 P 為黑色

直接添加即可，無需任何旋轉和調整顔色。這種情況下，直接添加滿足所有的着色法則，不用理會其叔節點的特征。

3、待插入節點 X 的父節點 P 為紅色，且該父節點 P 為X 祖父節點G 的左兒子

這種情況下，又分為幾種情況：

3.1、X 的叔節點 S 為紅色，（X 的叔節點就是 X 的祖父節點的右兒子）

此時存在紅- 紅的情況，父子節點同時為紅色，不滿足着色法則3，需要作出調整。

調整政策就是：将X 節點的父節點和叔節點着黑色，将其祖父節點着紅色，這樣該局部滿足着色法則，但是尚不清楚其曾祖父GG節點的顔色，如果GG為紅色，由于G也為紅色，這樣就不滿足着色法則3，仍需要調整；如果GG為黑色就不需要調整了，這裡的調整政策便是向上疊代調整，就是向上更換目前位置（将原目前位置X，設定為X的祖父節點G），再進行同等判斷調整。如下圖：

【深度探索 STL】【資料結構】詳解紅黑樹（一）結構及插入

3.2、X 的叔節點 S 為黑色（NULL認為是黑色節點）

紅黑樹還有個規則就是NULL節點一律看作是黑節點，如某節點K 的右兒子不存在，即該右兒子看作是黑色節點，這個不影響着色法則。

叔節點S 為黑，這樣就需要通過旋轉和改變顔色來調整了，通過之前的 AVL 樹，我們知道外側插入和内側插入的旋轉不一樣，外側插入（這裡的左左）隻需單旋轉，而内側插入（左右）則需要雙旋轉。

3.2.1、先看看外側插入，即待插入節點X 為其父節點的左兒子

這種情況下，需要進行單旋轉然後調整顔色。關于外側插入的旋轉已經在AVL樹中介紹，這裡是相似的，不再贅述。實作細節看圖便知

【深度探索 STL】【資料結構】詳解紅黑樹（一）結構及插入

調整前後局部根節點還是黑色，也就是這種情況下隻需要局部調整顔色然後單旋轉即可，不需要向上疊代

3.2.2、内側插入，即待插入節點X 為其父節點的右兒子

該情況下，需要先進行左旋轉，然後調整顔色，然後再次進行右旋轉即可，前後局部根節點依舊為黑色節點，同樣不需要考慮上一層的紅-紅問題，實作細節如下圖：

【深度探索 STL】【資料結構】詳解紅黑樹（一）結構及插入

上述第3點考慮的是待插入節點的父節點 P 為X 祖父節點G 的左兒子的情況，其作為右兒子也是類似的操作，差别在于旋轉的先後順序上，同AVL樹的旋轉調整。這裡也順便貼出來，見第4點

4、待插入節點 X 的父節點 P 為紅色，且該父節點 P 為X 祖父節點G 的右兒子

同樣分為以下幾種情況，由于與第3點是對稱性結構，這裡就簡單的貼圖說明：

4.1、X 的叔節點 S 為紅色，（X 的叔節點就是 X 的祖父節點的左兒子）

具體說明參見3.1。同樣需要解決紅-紅（父子節點同時為紅色）的問題，調整位置向上疊代判斷調整

【深度探索 STL】【資料結構】詳解紅黑樹（一）結構及插入

4.2、X 的叔節點 S 為黑色（NULL認為是黑色節點）

也是需要考慮外側插入和内側插入的情況

4.2.1、外側插入，即待插入節點X 為其父節點的右兒子

【深度探索 STL】【資料結構】詳解紅黑樹（一）結構及插入

4.2.2、内側插入，即待插入節點X 為其父節點的左兒子

【深度探索 STL】【資料結構】詳解紅黑樹（一）結構及插入

以上便是紅黑樹插入節點的所有情況。

下面我們通過STL的源碼來剖析上述過程：

先看看兩個關鍵函數：左旋轉和右旋轉

左旋轉：

/*左旋轉*/
inline void
__rb_tree_rotate_left(__rb_tree_node_base* x, __r_node_base*& root)
{
	//X為旋轉點
	__rb_tree_node_base* y = x->right;//令Y為旋轉點的右子節點
	x->right = y->left;//X的右子節點指向Y的左子節點
	if (y->left != 0)
		y->left->parent = x;//如果Y有左兒子，則其左兒子的父節點設定為X
	y->parent = x->parent;//Y的父節點設為X的父節點

	if (x == root)
		root = y;//如果X為根節點，則将Y設為根節點
	else if (x == x->parent->left)
		x->parent->left = y;//如果X為其父節點的左兒子，則将X的父節點的左兒子設為Y
	else
		x->parent->right = y;//如果X為右兒子，則将其父節點的右兒子設為Y
	y->left = x;//Y的左兒子設為X
	x->parent = y;//X的父節點設為Y
}

其旋轉過程參見下圖：

【深度探索 STL】【資料結構】詳解紅黑樹（一）結構及插入

右旋轉：

/*右旋轉，必須将所有父子關系轉接過來*/
inline void
__rb_tree_rotate_right(__rb_tree_node_base* x, __rb_tree_node_base*& root)
{  
	//X為旋轉點
	__rb_tree_node_base* y = x->left;//令Y為旋轉點的左子節點
	x->left = y->right;//X的右子節點指向Y的右子節點
	if (y->right != 0)
		y->right->parent = x;//如果Y有右兒子，則其右兒子的父節點設定為X
	y->parent = x->parent;//Y的父節點設為X的父節點

	/*将Y完全替代X的地位，将X的所有父子關系轉接過來*/
	if (x == root)
		root = y;//如果X為根節點，則将Y設為根節點
	else if (x == x->parent->right)
		x->parent->right = y;//如果X為其父節點的右兒子，則将X的父節點的右兒子設為Y
	else
		x->parent->left = y;//如果X為左兒子，則将其父節點的左兒子設為Y
	y->right = x;//Y的右兒子設為X
	x->parent = y;//X的父節點設為Y
}

旋轉示意圖如下

【深度探索 STL】【資料結構】詳解紅黑樹（一）結構及插入

有了前面的旋轉函數，接下來來看看STL中紅黑樹插入節點後的平衡調整函數：

/*調整紅黑樹，旋轉以及改變顔色*/
inline void
__rb_tree_rebalance(__rb_tree_node_base* x, __rb_tree_node_base*& root)
{
	//X為新插入節點
	x->color = __rb_tree_red;//新插入節點初始為紅色
	while (x != root && x->parent->color == __rb_tree_red)//父節點為紅
	{
		if (x->parent == x->parent->parent->left)//X的父節點為其祖父節點的左兒子
		{
			__rb_tree_node_base* y = x->parent->parent->right;//Y指定為X的叔節點
			if (y && y->color == __rb_tree_red)//如果X的叔節點存在且為紅色
			{
				/*調整顔色，需要向上疊代，直至滿足着色法則第3點（不能紅-紅）*/
				x->parent->color = __rb_tree_black;//X的父節點着黑色
				y->color = __rb_tree_black;//X的叔節點Y着黑色
				x->parent->parent->color = __rb_tree_red;//X的祖父節點着紅色
				x = x->parent->parent;//調整位置，将目前位置重置為X的祖父節點，開始上層疊代調整
			}
			else//X的叔節點不存在或者為黑色
			{
				if (x == x->parent->right)//X為右兒子，即内側插入（左右）
				{
					x = x->parent;//設定旋轉點為X的父節點，不影響後面if外X的值
					__rb_tree_rotate_left(x, root);//以X(實際為原X的父節點)為旋轉點左旋轉
				}
				//因為上面X的指派在随後的左旋轉已經徹底轉換了父子關系，是以後面的X還是指向新插入節點位置(不是值)
				x->parent->color = __rb_tree_black;//将X的父節點着黑色
				x->parent->parent->color = __rb_tree_red;//X的祖父節點
				__rb_tree_rotate_right(x->parent->parent, root);//以X的祖父節點為旋轉點右旋轉
			}
		}
		else//X的父節點為其祖父節點的右兒子
		{
			__rb_tree_node_base* y = x->parent->parent->left;//Y指定為X的叔節點
			if (y && y->color == __rb_tree_red)//如果X的叔節點存在且為紅色
			{
				/*調整顔色，并向上疊代判斷調整*/
				x->parent->color = __rb_tree_black;
				y->color = __rb_tree_black;
				x->parent->parent->color = __rb_tree_red;
				x = x->parent->parent;//調整位置
			}
			else
			{
				if (x == x->parent->left)
				{
					x = x->parent;
					__rb_tree_rotate_right(x, root);//以X(原X的父節點)為旋轉點，右旋轉
				}
				x->parent->color = __rb_tree_black;
				x->parent->parent->color = __rb_tree_red;
				__rb_tree_rotate_left(x->parent->parent, root);//以X的祖父節點為旋轉點進行左旋轉
			}
		}
	}//end while
	root->color = __rb_tree_black;//最後将根節點着色為黑色
}

有了前面的介紹，相信不難了解這個程式。上面便是紅黑樹插入節點後的核心部分程式

再來看看紅黑樹的插入函數，在了解紅黑樹的插入操作之前，有必要先了解紅黑樹的資料結構以及構造和記憶體管理

先看看紅黑樹的節點結構

/*紅黑樹rb_tree 的節點結構*/
struct __rb_tree_node_base
{
	typedef __rb_tree_color_type color_type;
	typedef __rb_tree_node_base* base_ptr;

	color_type color;
	base_ptr parent;
	base_ptr left;
	base_ptr right;

	/*求取X節點以下的最小值(小于等于X的最小值)*/
	static base_ptr minimum(base_ptr x)
	{
		while (x->left != 0) x = x->left;
		return x;
	}
	/*求取X節點以下的最大值（大于等于X的最大值）*/
	static base_ptr maximum(base_ptr x)
	{
		while (x->right != 0) x = x->right;
		return x;
	}
};

接下來紅黑樹rb_tree 的類體結構，由于比較大，這裡隻摘取相關部分

template <class Key, class Value, class KeyOfValue, class Compare,
class Alloc = alloc>
class rb_tree {
protected:
	/*typedef 資料類型*/
	typedef void* void_pointer;
	typedef __rb_tree_node_base* base_ptr;
	typedef __rb_tree_node<Value> rb_tree_node;
	typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;
	typedef __rb_tree_color_type color_type;
public:
	……
	typedef rb_tree_node* link_type;
 
protected:
	/*配置設定節點空間*/
	link_type get_node() { return rb_tree_node_allocator::allocate(); }
	/*釋放節點空間*/
	void put_node(link_type p) { rb_tree_node_allocator::deallocate(p); }

	/*建立一個節點*/
	link_type create_node(const value_type& x) 
	{
		link_type tmp = get_node();//擷取空間
        //……省略捕獲異常  
		construct(&tmp->value_field, x);//構造内容
	}

	link_type clone_node(link_type x)//複制一個節點（值和顔色）
	{
		link_type tmp = create_node(x->value_field);
		tmp->color = x->color;
		tmp->left = 0;
		tmp->right = 0;
		return tmp;
	}

	void destroy_node(link_type p)//删除節點
	{
		destroy(&p->value_field);//析構内容
		put_node(p);//釋放節點空間
	}

protected:
	size_type node_count; // keeps track of size of tree
	link_type header;//這是實作上的一個技巧，該類沒有單獨指定根節點，header->parent就是指向根節點
	Compare key_compare;

	/*以下三個函數用來友善取得 header 的成員*/
	link_type& root() const { return (link_type&)header->parent; }//樹的根節點
	link_type& leftmost() const { return (link_type&)header->left; }//樹的最小節點
	link_type& rightmost() const { return (link_type&)header->right; }//樹的最大節點

	/*以下六個函數用來友善取得節點 X 的成員*/
	static link_type& left(link_type x) { return (link_type&)(x->left); }
	static link_type& right(link_type x) { return (link_type&)(x->right); }
	static link_type& parent(link_type x) { return (link_type&)(x->parent); }
	static reference value(link_type x) { return x->value_field; }
	static const Key& key(link_type x) { return KeyOfValue()(value(x)); }
	static color_type& color(link_type x) { return (color_type&)(x->color); }

	/*省略類型base_ptr的同類函數，功能一樣*/
	
	/*求取極小值*/
	static link_type minimum(link_type x) {
		return (link_type)__rb_tree_node_base::minimum(x);
	}
	/*求取極大值*/
	static link_type maximum(link_type x) {
		return (link_type)__rb_tree_node_base::maximum(x);
	}

private:
	iterator __insert(base_ptr x, base_ptr y, const value_type& v);
	link_type __copy(link_type x, link_type p);
	void __erase(link_type x);
	/*下面這個函數需要說明一下*/
	void init() {
		header = get_node();//産生一個節點空間，讓 header 指向它
		color(header) = __rb_tree_red; //令header 為紅色，用于區分root

		root() = 0;//header->parent = 0
		leftmost() = header;//令header 的左兒子為自己
		rightmost() = header;//令header 的右兒子為自己
	}
public:
	// allocation/deallocation
	rb_tree(const Compare& comp = Compare())
		: node_count(0), key_compare(comp) {
		init();
	}
	/*拷貝構造函數*/
	rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x)
		: node_count(0), key_compare(x.key_compare) 
	{
		header = get_node();
		color(header) = __rb_tree_red;
		if (x.root() == 0)//拷貝空樹，僅存在header
		{
			/*設定 header*/
			root() = 0;
			leftmost() = header;
			rightmost() = header;
		}
		else 
		{
			/*樹結構拷貝*/
			root() = __copy(x.root(), header);//x.root()就是樹x的根節點
			//省略異常處理部分
			/*設定最大值和最小值
			header 的父節點指向根節點，然後左子節點指向最小節點，右子結點指向最大節點*/
			leftmost() = minimum(root());//不為空樹，root()則傳回根節點(header的父節點)
			rightmost() = maximum(root());
		}
		node_count = x.node_count;
	}
	/*析構函數*/
	~rb_tree() 
	{
		clear();
		put_node(header);
	}
	/*指派構造函數*/
	rb_tree<Key, Value, KeyOfValue, Compare, Alloc>&
		operator=(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x);

    ……
};

這裡對上面的 header 節點說明一下，樹狀結構的各種操作，最需注意的就是邊界情況的發生，也就是走到根節點是要有特殊的處理，這裡STL 特别為根節點再設計了一個父節點 header，而當插入節點後，header 的父節點指向根節點，其左子節點指向樹的最小節點，右子結點指向樹的最大節點。類似于連結清單的表頭，這裡也多了個頭節點不實際存儲資料，為管理而存在。

【深度探索 STL】【資料結構】詳解紅黑樹（一）結構及插入

也就是在一棵非空紅黑樹中，header->parent 就是指的該樹的根節點，header->left 就是指該樹的最小節點，header->right 就是指該樹的最大節點。

有了前面的了解，接下來看看紅黑樹的插入操作。

/*插入節點：節點鍵值不允許重複，若重複則插入無效
傳回值是個pair，第一進制素是個 rb_tree 疊代器，指向新增節點*/
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
pair<rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator, bool>
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(const Value& v)
{
	link_type y = header;//y為根節點的父節點
	link_type x = root();//x為根節點
	bool comp = true;
	while (x != 0)//從根節點開始，往下尋找适當的插入點
	{
		//二叉查找樹特性插入
		y = x;
		comp = key_compare(KeyOfValue()(v), key(x));//比較新增值v 和x節點的鍵值
		x = comp ? left(x) : right(x);//v遇"大"則往左，遇"小或等于"往右
	}//while内單次每次運作結束，y總為x的父節點
	
	iterator j = iterator(y);//此時y節點必為葉子節點
	if (comp)//v小于比較值，将插入左側
	{	
		if (j == begin())//begin()實際就是header->left，也就是樹的最左節點
			return pair<iterator, bool>(__insert(x, y, v), true);//轉入實際插入函數__insert()
		else//如果插入點之父節點不為最左節點
			--j;//調整j，--重載，調用decrement()，即找到比目前節點小的最大節點
		//與此同時還有++重載，調用increment()，找到比目前節點大的最小節點
	}
	if (key_compare(key(j.node), KeyOfValue()(v)))//遇"小"将插入右側(v值大)
		return pair<iterator, bool>(__insert(x, y, v), true);
	/*以上，x為新插入點位置，y為插入點之父節點，v為鍵值*/

	return pair<iterator, bool>(j, false);//存在重複鍵值就不插入
}

/*插入節點：節點鍵值允許重複
傳回值是一個 rb_tree 疊代器，指向新增節點*/
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(const Value& v)
{
	link_type y = header;//y為根節點的父節點
	link_type x = root(); //x為根節點
	while (x != 0)//從根節點開始，往下尋找适當的插入點
	{
		y = x;
		//直接找到合适位置，無需考慮鍵值是否重複
		x = key_compare(KeyOfValue()(v), key(x)) ? left(x) : right(x);
	}
	return __insert(x, y, v);
}

從上面可知，真正的插入操作是__insert()

/*x為新增節點位置，y為新增節點的父節點，v為新增節點的鍵值*/
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::
__insert(base_ptr x_, base_ptr y_, const Value& v) {
	link_type x = (link_type)x_;
	link_type y = (link_type)y_;
	link_type z;

	if (y == header || x != 0 || key_compare(KeyOfValue()(v), key(y)))
	{
		z = create_node(v);//為新節點配置空間
		left(y) = z;                // also makes leftmost() = z when y == header
		if (y == header)//如果y為頭節點，也就是空樹第一次插入節點
		{
			root() = z;//z為根節點，與header節點互為父節點
			rightmost() = z;//樹的最大節點
		}
		else if (y == leftmost())//如果y為最左節點
			leftmost() = z;//修正最小節點
	}
	else//上面三種全不滿足，即插入鍵值大于插入點的父節點，右側插入
	{
		z = create_node(v);
		right(y) = z;//使新節點成為插入點的父節點y的右子結點
		if (y == rightmost())
			rightmost() = z;          // maintain rightmost() pointing to max node
	}
	//設定新增節點z的關系
	parent(z) = y;
	left(z) = 0;
	right(z) = 0;
	//平衡紅黑樹
	__rb_tree_rebalance(z, header->parent);

	++node_count;//節點數累加
	return iterator(z);//傳回疊代器，指向新增節點
}

以上就是紅黑樹的整個節點插入操作過程

參考資料：《STL 源碼剖析》

【深度探索 STL】【資料結構】詳解紅黑樹（一）結構及插入

繼續閱讀

GlobalMapper20把地形資料（tif）轉為可列印的STL格式模型一、為什麼要把地形轉為stl？二、轉換流程

HDU 5199 Gunner

gdb腳本 - 檢視stl變量

<Effectives STL>筆記之在STL容器中删除元素的方法選擇

C++ STL基本容器比較

STL--vector容器STL—vector容器

STL相關

【CF 125D】 Two progressions 劃分等差數列

STL六大元件以及互相關系

STL 六大元件概要

初識 STL

STL——deque 雙向隊列

c++中指針的指針和指針的引用的使用

pat（B）1009. 說反話（逆疊代器）

C++ heap學習

PAT (Top Level) Practise 1007 Red-black Tree (35)