文章目錄

資料結構-紅黑樹
- 1、紅黑樹簡介
- 紅黑樹的性質
- - 紅黑樹結點
  - 紅黑樹的5個性質
- 2、紅黑樹的操作
- - 旋轉
  - 插入操作
  - - 情況 1：z的叔結點y為紅色
    - 情況 2：z的叔結點y為黑色的且z是一個右孩子
    - 情況 3：z的叔結點y為黑色的且z是一個左孩子
  - 删除操作
  - - 情況 1：x的兄弟結點w是紅色的
    - 情況 2：x的兄弟結點w是黑色的，而且w的兩個子結點都是黑色的
    - 情況 3：x的兄弟結點w是黑色的，w的左孩子是紅色的，w的右孩子是黑色的。
    - 情況 4：x的兄弟結點w是黑色的，w的右孩子是紅色的
- 3、紅黑樹的實作

資料結構-紅黑樹

1、紅黑樹簡介

紅黑樹（red-black tree）是一種平衡的搜尋樹，常見的平衡搜尋樹包括

AVL樹

、

B樹

、

AA樹

、

treap樹

、

SBT樹

、

替罪羊樹

、

伸展樹

、

跳表

等。紅黑樹支援在最壞情況下對動态集合操作的時間複雜度為 O ( l g n ) O(lgn) O(lgn)。平衡樹的時間複雜度均為 O ( l g n ) O(lgn) O(lgn)，但是紅黑樹的性能最優，有很多應用。如C++的STL中的集合(set、multiset)、映射（map、multimap），在java中的TreeSet和TreeMap資料結構均用到紅黑樹。

紅黑樹的性質

紅黑樹是一棵二叉搜尋樹，每個結點均有一個顔色位（RED or BLACK）。通過對任何一條從根到葉子的簡單路徑上各個結點的顔色進行限制，紅黑樹確定沒有一條路徑會比其他路徑長出2倍。是以是近似平衡的。

紅黑樹結點

紅黑樹每個結點包括基本的5個域：Color、left、right、p、key。如果一個結點沒有子結點或父節點，則該結點相應指針指向 NIL。我們可以把 NIL實作為空指針（nullptr）或哨兵結點。我們可以把 NIL視為指向葉結點（外部結點）的指針，而把帶有關鍵字的結點視為内部結點。

紅黑樹的5個性質

1、每個結點為BLACK或RED

2、根節點顔色為BLACK

3、每個葉結點（NIL）為BLACK。

4、如果一個結點為RED，那麼它的兩個子結點均為BLACK

5、對于每個結點，該結點到其所有後代葉結點的簡單路徑上，均包含數目相同的BLACK結點。

在後面的實作中，NIL采用哨兵來實作。

下面是一個紅黑樹的示例圖：

資料結構-紅黑樹資料結構-紅黑樹

該樹滿足上面紅黑樹的5個性質。在後面的具體實作中，我們令根和子結點為空的結點相應的指針指向 T . n i l T.nil T.nil。

定理：對于n個結點一棵紅黑樹，它的高度之多為 2 l g ( n + 1 ) 2lg(n+1) 2lg(n+1)。具體證明過程看算法導論。

2、紅黑樹的操作

旋轉

紅黑樹是基于旋轉來維持平衡的，類是有

伸展樹

，

AVL樹

。也有無旋轉的平衡搜尋樹，如：

替罪羊樹

、

fhq reap樹

。幾乎所有的平衡樹都是基于旋轉來進行操作。通過旋轉來維持平衡樹的性質，同時可以保持樹的中序周遊結果不變。

紅黑樹的旋轉隻有左旋和右旋。分别是左旋和右旋的示意圖。

資料結構-紅黑樹資料結構-紅黑樹

下面是

LEFT-ROTATE

的僞代碼，對樹 T T T中的 x x x進行左旋，其中假設 x . r i g h t ! = T . n i l x.right \ != T.nil x.right !=T.nil，且根節點的父節點為 T . n i l T.nil T.nil。

LEFT-ROTATE(T,x)
	y = x.right			//擷取x的右孩子
	x.right = y.left	//擷取新的右孩子
	if y.left != T.nil
		y.left.p = x
	y.p = x.p			//更新與父親結點間的連結
	if x.p == T.nil
		T.root = y
	elseif x == x.p.left
		x.p.left = y
	else
		x.p.right = y
	y.left = x			//将x作為y的左孩子
	x.p = y

右旋的操作與左旋的操作對稱，是以隻需要将其中出現的

left

和

right

進行對調即可。

下面是左旋和右旋的執行個體操作。

資料結構-紅黑樹資料結構-紅黑樹

插入操作

紅黑樹的插入操作（

RB-INSERT

）與BST的插入操作基本一緻，插入操作後，需要額外的操作，如通過旋轉，變換顔色等操作進行調整，使之滿足紅黑樹的性質，這些操作在

RB-INSERT-FIXUP

中完成。

下面是插入操作

RB-INSERT

的僞代碼，将結點 z z z，插入 T T T中合适為止。

RB-INSERT(T,z)
	y = T.nil			//父節點為止
	x = T.root			//插入位置
	while x != T.nil
		y = x
		if z.key < x.key
			x = x.left
		else
			x = x.right
	z.p = y
	if y == T.nil
		T.root = z
	elseif z.key < y.key
		y.left = z
	else y.right = z
	z.left = z.right = T.nil
	z.color = RED
	RB-INSERT-FIXUP(T,z)	//對樹進行調整

這裡不具體證明算法的正确性，可以參考算法導論。

下面是

RB-INSERT-FIXUP

的僞代碼。

RB-INSERT-FIXUP(T,z)
	while z.p.color == RED
		if z.p == z.p.p.left
			y = z.p.p.left			//uncle node
			if y.color == RED
				z.p.color = BLACK	//case 1
				y.color = BLACK		//case 1
				z.p.p.color = RED	//case 1
				z = z.p.p			//case 1
			else
				if z == z.p.right
					z = z.p			//case 2
					LEFT-ROTATE(T,z)//case 2
				z.p.color = BLACK	//case 3
				z.p.p.color = RED	//case 3
				RIGHT-ROTATE(T,z.p.p)//case 3
		else(same as then clause
				with "right" and "left" exchanged)
	T.root.color = BLACK

實際上紅黑樹的插入調整操作一共有6種情況，但是當 x . p x.p x.p為右子樹時，與作為左子樹的情況相對稱，是以，隻需要将處理左子樹的情況中的

left

和

right

進行對調即可。後面将結合例子講以上這三種情況。這三種情況并不是互相獨立，其中 case 2 完成後就可以變為 case 3。

在紅黑樹的插入調整操作中，case 1 通過變色來上升 z z z，使 z z z的叔結點代碼中的 y y y變為黑色轉化為case 2、3，而case 2 和case 3各通過旋轉，最終使其滿足紅黑樹性質。是以隻有case 1 可以不斷疊代，直至根節點時，它的 z . p = T . n i l z.p = T.nil z.p=T.nil。此時恒成立推出，是以時間複雜度為 l g n lgn lgn。

情況 1：z的叔結點y為紅色

如圖所示， z z z所指為目前發生沖突的結點，它與 z . p z.p z.p顔色均為紅色。同時叔結點 y y y為紅色。此時 z z z是左孩子還是右孩子均屬該情況。根據上面case 1的僞代碼，實質上通過将父節點 z . p z.p z.p 和叔結點 y y y變為黑色，同時令 z . p . p z.p.p z.p.p變為新的 z z z，令它為紅色。通過這樣的操作，實質上是将 z z z轉移上升，最終或者到達根節點，那麼推出while後置根節點為黑色，或者使之得到新的叔結點y的顔色為黑色，轉化為case 2 or 3。

資料結構-紅黑樹資料結構-紅黑樹

情況 2：z的叔結點y為黑色的且z是一個右孩子

情況 3：z的叔結點y為黑色的且z是一個左孩子

如圖所示，在case2、3中，此時叔結點 y y y為黑色。如果為case 2，目前 z z z為有右孩子，那麼将 z z z變為 z . p z.p z.p，同時對結點 z z z進行一次左旋，使之變為情況3。在case 3中，将此時 z z z為左孩子，将 z . p z.p z.p置為黑色，同時将 z . p . p z.p.p z.p.p置為紅色，對 z . p . p z.p.p z.p.p進行一次右旋。完成case 3的操作後，此時已經滿足了紅黑樹的性質。

對于case 2而言，實際是通過旋轉和變色，使 z z z轉化為一個左孩子，然後在case 3中，我們通過旋轉和變色，相當于将C的黑色傳遞給B，令B代替C繼續連接配接上層結點，同時滿足紅黑樹的性質。

資料結構-紅黑樹資料結構-紅黑樹

無論是從case 2到case 3還是直接從case 1到case 3。最多進行2次旋轉，可在常數時間内完成，結合case 1。

RB-TREE-FIXUP

的時間複雜度為 O ( l g n ) O(lgn) O(lgn)。是以，對于一次插入操作，總的時間複雜度為 O ( l g n ) O(lgn) O(lgn)。

删除操作

紅黑樹的删除操作（

RB-DELETE

）相比插入操作更複雜一點。類似BST的實作，删除某個結點，利用該結點的後繼代替該結點位置，若後繼存在右孩子，将其右孩子代替後繼的位置。處理完成後，類似插入操作，需要對樹進行調整，進而滿足紅黑樹的性質，該過程通過RB-DELETE-FIXUP函數完成。

下面使删除操作的僞代碼，将樹 T T T中的結點 z z z删除。

删除過程中，需要采用一個結點替換另外一個結點的位置，采用

RB-TRANSPLANT(T,x,y)

實作，該函數實作用 y y y結點（可以為空，我們的T.nil采用哨兵實作，一定存在，是以可以當成内部結點處理）。

下面是

RB-TRANSPLANT

的僞代碼

RB-TRANSPLANT(T,u,v)
	if u.p == T.nil	//u為根節點
		T.root = v
	elseif u == u.p.left
		u.p.left = v
	else
		u.p.right = v
	v.p = u.p

下面是删除操作

TREE-DELETE

的僞代碼

RB-DELETE(T,z)
	y = z
	y_original_color = y.color
	if z.left == T.nil	//左子樹為空，采用右子樹代替z
		x = z.right
		RB-TRANSPLANT(T,z,z.right)
	elseif z.right == T.nil//右子樹為空，采用左子樹代替z
		x = z.right
		RB-TRANSPLANT(T,z,z.left)
	else
		y = TREE-MINIMUM(z.right)	//采用後繼代替
		y_original_color = y.color
		x = y.right
		if y.p == z	//後繼是z的右孩子
			x.p = y
		else RB-TRANSPLANT(T,y,y.right)//不是右孩子，需要将y用其右孩子替換
			 y.right = z.right
			 y.right.p = y
		RB-TRANSPLANT(T,z,y)
		y.left = z.left
		y.left.p = y
		y.color = z.color
	if y_original_color == BLACK //被取走的後繼是黑色，需要進行調整
		RB-DELETE-FIXUP(T,x)

删除操作中 y y y記錄被删除的結點 z z z或作為替換 z z z的結點，同時 y _ o r i g i n a l _ c o l o r y\_original\_color y_original_color記錄它的顔色。同時記錄 y y y的右子樹 x x x，它是替換 y y y的結點，同時後面可能需要對 x x x為根的子樹進行調整。

假設 z z z隻有單個孩子或沒有孩子，那麼 y = z y = z y=z即是被删除的結點。 x = x . r i g h t x = x.right x=x.right為替換 y y y的結點。同時記錄 y _ o r i g i n a l _ c o l o r y\_original\_color y_original_color，如果 y _ o r i g i n a l _ c o l o r y\_original\_color y_original_color為紅色， ∵ y = z \because y = z ∵y=z最多隻有一個孩子，删除它後用它的孩子代替，不會影響紅黑樹的性質。否則如果 y y y為黑色，那麼将會引起 x x x為根的子樹的黑高減1，需要進行調整。即最後一行判斷語句。
假設 z z z存在兩個孩子，那麼取 y = y = y=TREE-MINIMUM( x . r i g h t x.right x.right)，此時 y y y記錄替換 z z z的結點。同時更新 y _ o r i g i n a l _ c o l o r y\_original\_color y_original_color和 x x x。如果 y y y是 z z z的右孩子，此時我們令 x . p = y x.p = y x.p=y，後面隻需要執行 RB-TRANSPLANT(T,z,y) 用 y y y替換 z z z，更新 y y y的左子樹連結，否則，需要用 x = y . r i g h t x = y.right x=y.right先替換 y y y，更新 y y y的右子樹連結。和上面相同，用 y y y替換 z z z，如果 y y y的顔色是黑色，會引起 x x x為根的子樹的黑高-1，需要後面進行調整。

詳細的證明參考算法導論

最後是

RB-DELETE-FIXUP

的僞代碼

RB-DELETE-FIXUP(T,x)
	while x != T.root AND x.color == BLACK
		if x == x.p.left
			w = x.p.right	//brother node
			if w.color == RED
				w.color = BLACK		//case 1
				x.p.color = RED		//case 1
				LEFT-ROTATE(T,x.w)	//case 1
				w = w.p.right		//case 1
			if  w.left.color == BLAKC AND w.right.color == BLACK
				w.color = RED		//case 2
				x = x.p				//case 2
			else
				if w.right.color == BLACK	
					w.color = RED			//case 3
					w.left.color =BLACK		//case 3
					RIGHT-ROTATE(T,w)		//case 3
					w = x.p.right			//case 3
				w.color = x.p.color			//case 4
				x.p.color = BLACK			//case 4
				w.right.color = BLACK		//case 4
				LEFT-ROTATE(T,x.p)			//case 4
				x = T.root					//case 4
		else (same as then clause with "right" and "left" exchanged)
	x.color = BLACK

上面講到，用删除 y y y 或 y y y 代替 z z z後，如果 y _ o r i g i n a l _ c o l o r y\_original\_color y_original_color為黑色，會引起 x x x為根的子樹的黑高減1。對于這個黑高減1，我們可以把它了解為将 y y y 的黑色加到了結點 x x x上，此時 x x x為雙黑色或紅黑色，RB-DELETE-FIXUP的過程實質上就是通過旋轉和變色等操作，将結點 x x x上多出來的黑色抽取出來，放在另一個節點上，然後通過調整樹，使之滿足紅黑樹的性質。

紅黑樹的删除調整操作中，可以分為8種情況，類似插入調整操作。删除調整操作根據結點 x x x是左孩子還是右孩子分為對稱的4種操作。這裡實作 x x x為左孩子的情形，當 x x x為右孩子時，隻需要将處理左孩子的情況中出現的

left

和

right

進行對調即可。

首先注意， w h i l e while while循環時， x x x始終指向雙黑色結點，直到 x x x到達根節點，或者 x . c o l o r = R E D x.color = RED x.color=RED,即 x x x抽取出黑色，放置到其他點上，并滿足紅黑樹的性質。

這裡簡單概述下這4種情況。這4種情況并不是互相獨立的。

對于case 1，兄弟結點 w w w為紅色時，那麼可以通過旋轉變色擷取 w w w的一個黑色孩子，作為自己新的兄弟。當 x x x的兄弟為黑色時，此時轉化為case 2，3，4。
在 w w w的孩子均為黑色結點時，此時為case 2，我們可以将 x x x和 w w w的黑色抽出，傳遞給 x . p x.p x.p，此時 x . p x.p x.p成為新的 x x x進入下一輪循環。
若 w w w左孩子為紅色，右孩子為黑色，此時為case 3，然後我們通過旋轉和變色，令 w w w的右孩子為紅色，進而轉化為case 4。
當case 4時， w w w為紅色，同時它的右孩子為紅色，然後通過旋轉和變色，将 w w w的黑色抽取出來，放置在原來的父結點上，同時令 x = T . r o o t x = T.root x=T.root跳出循環。

下面将具體讨論 x x x為左孩子的4種情況。

情況 1：x的兄弟結點w是紅色的

如圖，此時結點 x x x為雙黑色，結點 w w w為紅色，那麼根據紅黑樹的性質4， w w w的父子結點均為黑色。我們将 x . p x.p x.p和 w w w的顔色交換，然後對 x . p x.p x.p進行進行一次左旋，最後更新 w w w，通過這樣的操作，我們将原來 w w w的一個黑色的孩子作為 x x x的兄弟。進而換為case 2，3，4。

資料結構-紅黑樹資料結構-紅黑樹

情況 2：x的兄弟結點w是黑色的，而且w的兩個子結點都是黑色的

如圖，其中灰色的結點對顔色無要求，既可以是紅色也可以是黑色，實際程式設計中，不存在灰色結點。

此時， w w w為黑色，同時孩子均為黑色。此時，我們将 w . c o l o r = R E D w.color = RED w.color=RED，該操作實質上是将 x x x和 w w w的黑色抽出，放置到 x . p x.p x.p中，然後 x = x . p x = x.p x=x.p，此時 x . p x.p x.p稱為新的 x x x，因為此時它具有雙重顔色，或者紅黑色，或者雙黑色。如果是通過case 1轉化為case 2，那麼新的 x x x為紅黑色，此時将會跳出循環，同時，我們令 x . c o l o r = B L A C K x.color = BLACK x.color=BLACK，完成後，此時成功将 x x x的黑色抽出放在另一個結點上，同時滿足紅黑樹性質。如果 x . p x.p x.p原來為黑色，那麼它将變為雙黑色，則進入下一次 w h i l e while while循環。

最壞情況下，每次 w w w和它的孩子均是黑色，此時時間複雜度為 l g ( n ) lg(n) lg(n)。

資料結構-紅黑樹資料結構-紅黑樹

情況 3：x的兄弟結點w是黑色的，w的左孩子是紅色的，w的右孩子是黑色的。

在case 2下面的else分支時，此時 w w w為黑色，進入該分支，說明 w w w的左子樹或者右子樹為紅色。我們的最終目的是使 w w w的右孩子為紅色結點。是以，在下面的

if x.right.color == BLACK

分支中，說明 w w w的左孩子為紅色，此時，我們通過交換 w w w和 w . l e f t w.left w.left的顔色，然後對 w w w進行一次右旋，進而使 w w w獲得一個紅色的右孩子，最後更新 w = x . p . r i g h t w = x.p.right w=x.p.right，成功為case 4。如果 i f if if分支不成立，說明本身具備紅色的右孩子，後面的操作也不需要關注左孩子的顔色，此時即為case 4。

如圖：

資料結構-紅黑樹資料結構-紅黑樹

情況 4：x的兄弟結點w是黑色的，w的右孩子是紅色的

如圖，當 w w w為紅色，其他的右孩子是紅色時，此時，我們可以交換 x . p x.p x.p和 w w w的顔色，同時将 x . r i g h t x.right x.right置為黑色，然後左旋 x . p x.p x.p結點。最終滿足紅黑樹性質。令 x . p x.p x.p為黑色，實質上是使 x x x為根的子樹的黑高加1，相當于抽取出，x為黑色，此時x滿足性質1，x為根的子樹黑高加1滿足性質5，同時w的左子樹，即圖中的C的黑高不變。但是此時 w w w的右子樹黑高減1，但是我們可以通過将 w . r i g h t w.right w.right即圖中的E置為黑色，進而使其黑高不變，此時整體滿足紅黑樹性質，置 x = T . r o o t x = T.root x=T.root退出循環。

資料結構-紅黑樹資料結構-紅黑樹

對于

RB-DELETE-FIXUP

唯一可能進行疊代的是case 2，沿樹上升至多 O ( l g n ) O(lgn) O(lgn)次期間不進行任何旋轉，對于case 1，3，4的旋轉操作，最多盡量3次。是以

RB-DELETE-FIXUP

的時間複雜度為 O ( l g n ) O(lgn) O(lgn)。

3、紅黑樹的實作

下面紅黑樹采用C++實作，為了和上面的僞代碼形式一緻，便于了解，沒有采用類封裝操作，隻包含一些C++特性。

#include<iostream>
#include<vector>
#include<queue>
#include<random>
#include<ctime>
using namespace std;
//定義顔色宏
enum COLOR{RED,BLACK};
//結點定義
template<typename T>
struct Node
{
	Node<T>* left;
	Node<T>* right;
	Node<T>* p;
	T key;
	COLOR color;
	Node():color(BLACK){}
};
//結點指針定義
template<typename T>
using pNode=Node<T>*;
//紅黑樹定義
template<typename T>
struct RBTree
{	
	static pNode<T> nil;
	/**
	 * Singleton Model
	 * 采用local-static對象
	 * 使模闆參數相同的對象公用一個nil
	 * 在main函數前被使用。
	 * 具體參考 下面這篇部落格
	 * https://blog.csdn.net/qq_40512922/article/details/90589657#41_274
	 */
	static pNode<T> getInstance(){
		static Node<T> one_instance;
		return &one_instance;
	}
	pNode<T> root;
	RBTree():root(nil){}
};
//初始化 nil
template<typename T>
pNode<T> RBTree<T>::nil=RBTree<T>::getInstance();
/*
	Function Decleration
	----------------------------------------
 */
template<typename T>//插入
void RBTree_insert(RBTree<T> &t,pNode<T> z);
template<typename T>//插入調整
void RBTree_insert_fixup(RBTree<T> &t,pNode<T> z);
template<typename T>//删除
void RBTree_delete(RBTree<T> &t,pNode<T> z);
template<typename T>//删除調整
void RBTree_delete_fixup(RBTree<T> &t,pNode<T> x);
template<typename T>//O(1)空間複雜度疊代中序周遊
void inorder_travel_iterative(pNode<T> x);
template<typename T>//正常遞歸中序周遊
void inorder_travel_recursive(pNode<T> x);
template<typename T>//結點x的後繼
pNode<T> tree_successor(pNode<T> x);
template<typename T>//利用後繼函數在O(n)有序周遊
void tree_travel_successor(pNode<T> x);
template<typename T>//左旋
void left_rotate(RBTree<T> &t,pNode<T> z);
template<typename T>//右旋
void right_rotate(RBTree<T> &t,pNode<T> z);
template<typename T>//結點x為根的子樹的最小值
pNode<T> tree_minimum(pNode<T> x);
template<typename T>//初始化Vector
void getInitVec(vector<pNode<T>> &vec);
template<typename T>//釋放記憶體
void freeVec(vector<pNode<T>> &vec);
template<typename T>//列印結點x
void print(const Node<T>*x);

/*
	Function Definition
	----------------------------------------
 */
template<typename T>
void print(const Node<T>*x)
{
	cout << x->key;
	if(x->color==BLACK)
		cout << "[BLACK] ";
	else
		cout << "[RED] ";
}
template<typename T>
void inorder_travel_recursive(pNode<T> x)
{
	if(x!=RBTree<T>::nil)
	{
		inorder_travel_recursive(x->left);
		print(x);
		inorder_travel_recursive(x->right);
	}
}
template<typename T>
void inorder_travel_iterative(pNode<T> x)
{
	if(x==RBTree<T>::nil)return;
	pNode<T> y=RBTree<T>::nil;
	while(true)
	{
		if(y!=x->left)
			while(x->left!=RBTree<T>::nil)
				x=x->left;
		print(x);
		if(x->right!=RBTree<T>::nil)
		{
			x=x->right;
			continue;
		}
		do{
			y=x;
			x=x->p;
			if(x==RBTree<T>::nil)
				return;
		}while(y==x->right);
	}
}
template<typename T>
void left_rotate(RBTree<T> &t,pNode<T> x) 
{
	pNode<T> y=x->right;
	x->right=y->left;
	if(y->left!=RBTree<T>::nil)
		y->left->p=x;
	y->p=x->p;
	if(x->p==RBTree<T>::nil)
		t.root=y;
	else if(x->p->left==x)
		x->p->left=y;
	else
		x->p->right=y;
	y->left=x;
	x->p=y;
}
template<typename T>
void right_rotate(RBTree<T> &t,pNode<T> x)
{
	pNode<T> y=x->left;
	x->left=y->right;
	if(y->right!=RBTree<T>::nil)
		y->right->p=x;
	y->p=x->p;
	if(x->p==RBTree<T>::nil)
		t.root=y;
	else if(x->p->left==x)
		x->p->left=y;
	else
		x->p->right=y;
	y->right=x;
	x->p=y;
}
template<typename T>
void RBTree_insert(RBTree<T> &t,pNode<T> z)
{
	pNode<T> y=RBTree<T>::nil;
	pNode<T> x=t.root;
	while(x!=RBTree<T>::nil)
	{
		y=x;
		if(z->key<x->key)
			x=x->left;
		else
			x=x->right;
	}
	z->p=y;
	if(y==RBTree<T>::nil)
		t.root=z;
	else if(z->key<y->key)
		y->left=z;
	else
		y->right=z;
	z->left=z->right=RBTree<T>::nil;
	z->color=RED;
	RBTree_insert_fixup(t,z);
}
template<typename T>
void RBTree_insert_fixup(RBTree<T> &t,pNode<T> z)
{
	while(z->p->color==RED)
	{
		if(z->p==z->p->p->left)
		{
			pNode<T> y=z->p->p->right;
			if(y->color==RED)
			{
				z->p->color=BLACK;	//case 1
				y->color=BLACK;
				z->p->p->color=RED;
				z=z->p->p;
			}
			else
			{
				if(z==z->p->right)
				{
					z=z->p;			//case 2
					left_rotate(t,z);
				}
				z->p->color=BLACK;	//case 3
				z->p->p->color=RED;
				right_rotate(t,z->p->p);
			}
		}//end-if
		else
		{
			pNode<T> y=z->p->p->left;
			if(y->color==RED)
			{
				z->p->color=BLACK;
				y->color=BLACK;
				z->p->p->color=RED;
				z=z->p->p;
			}
			else
			{
				if(z==z->p->left)
				{
					z=z->p;
					right_rotate(t,z);
				}
				z->p->color=BLACK;
				z->p->p->color=RED;
				left_rotate(t,z->p->p);
			}
		}//end-else
	}//end while
	t.root->color=BLACK;
}
template<typename T>
pNode<T> tree_minimum(pNode<T> x)
{
	while(x->left!=RBTree<T>::nil)
		x=x->left;
	return x;
}
template<typename T>
void RBTree_transplant(RBTree<T> &t,pNode<T> u,pNode<T> v)
{
	if(u->p==RBTree<T>::nil)
		t.root=v;
	else if(u==u->p->left)
		u->p->left=v;
	else
		u->p->right=v;
	v->p=u->p;
}
template<typename T>
void RBTree_delete(RBTree<T> &t,pNode<T> z)
{
	pNode<T> y=z;
	pNode<T> x;
	COLOR y_original_color=y->color;
	if(z->left==RBTree<T>::nil)
	{
		x=z->right;
		RBTree_transplant(t,z,z->right);
	}
	else if(z->right==RBTree<T>::nil)
	{
		x=z->left;
		RBTree_transplant(t,z,z->left);
	}
	else
	{
		y=tree_minimum(z->right);
		y_original_color=y->color;
		x=y->right;
		if(y->p==z)
			x->p=y;
		else
		{
			RBTree_transplant(t,y,y->right);
			y->right=z->right;
			y->right->p=y;
		}
		RBTree_transplant(t,z,y);
		y->left=z->left;
		y->left->p=y;
		y->color=z->color;
	}
	if(y_original_color==BLACK)
		RBTree_delete_fixup(t,x);
}
template<typename T>
void RBTree_delete_fixup(RBTree<T> &t,pNode<T> x)
{
	while(x!=t.root&&x->color==BLACK)
	{
		if(x==x->p->left)
		{
			pNode<T> w=x->p->right;//兄弟
			if(w->color==RED)
			{
				w->color=BLACK;		//case 1
				x->p->color=RED;
				left_rotate(t,x->p);
				w=x->p->right;
			}
			if(w->left->color==BLACK&&w->right->color==BLACK)
			{
				w->color=RED;	//case 2
				x=x->p;
			}
			else
			{
				if(w->right->color==BLACK)
				{
					w->left->color=BLACK;	//case 3
					w->color=RED;
					right_rotate(t,w);
					w=x->p->right;
				}
				w->color=x->p->color;	//case 4
				x->p->color=BLACK;
				w->right->color=BLACK;
				left_rotate(t,x->p);
				x=t.root;
			}
		}//end-if
		else
		{
			pNode<T> w=x->p->left;//兄弟
			if(w->color==RED)
			{
				w->color=BLACK;		//case 1
				x->p->color=RED;
				right_rotate(t,x->p);
				w=x->p->left;
			}
			if(w->left->color==BLACK&&w->right->color==BLACK)
			{
				w->color=RED;	//case 2
				x=x->p;
			}
			else
			{
				if(w->left->color==BLACK)
				{
					w->right->color=BLACK;	//case 3
					w->color=RED;
					left_rotate(t,w);
					w=x->p->left;
				}
				w->color=x->p->color;	//case 4
				x->p->color=BLACK;
				w->left->color=BLACK;
				right_rotate(t,x->p);
				x=t.root;
			}
		}//end-else
	}
	x->color=BLACK;
}
template<typename T>
pNode<T> RBTree_search(RBTree<T> t,T key)
{
	pNode<T> x=t.root;
	while(x!=RBTree<T>::nil)
	{
		if(key==x->key)
			return x;
		else if(key<x->key)
			x=x->left;
		else
			x=x->right;
	}
	return x;
}
template<typename T>
pNode<T> tree_successor(pNode<T> x)
{
	if(x->right!=RBTree<T>::nil)
		return tree_minimum(x->right);
	pNode<T> y=x->p;
	while(y!=RBTree<T>::nil&&x==y->right)
	{
		x=y;
		y=y->p;
	}
	return y;
}
template<typename T>
void tree_travel_successor(pNode<T> x)
{
	if(x==RBTree<T>::nil)
		return;
	x=tree_minimum(x);
	do{
		print(x);
		x=tree_successor(x);
	}while(x!=RBTree<T>::nil);
}
/*
 *特例化 integer類型的随機初始化模闆。
 *因為下面的 uniform_int_distrbution隻支援整型。
 */
template<> void getInitVec(vector<pNode<int>> &vec)
{
	static default_random_engine e(time(nullptr));
	static uniform_int_distribution<int> d(0,50000);
	int key;
	for(auto &i:vec){
		i=new Node<int>();
		i->key=d(e);
	}
}
/*
 *	特例化double類型的随機初始化模闆
 */
template<> void getInitVec(vector<pNode<double>> &vec)
{
	static default_random_engine e(time(nullptr));
	static uniform_real_distribution<double> d(0,50000);
	double key;
	for(auto &i:vec){
		i=new Node<double>();
		i->key=d(e);
	}
}
template<typename T>
void freeVec(vector<pNode<T>> &vec)
{
	for(auto i:vec)
	{
		delete i;
		i=nullptr;
	}
}

void RBTree_property_test()
{
	int cnt;
	cout << "Input the cnt:" << endl;
	cin >> cnt;
	RBTree<int> T;
	vector<pNode<int>> vec(cnt);
	getInitVec(vec);
	clock_t sta=clock();
	for(auto i:vec)
		RBTree_insert(T,i);
	for(auto i:vec)
		RBTree_delete(T,i);
	clock_t interval=clock()-sta;
	cout << "CLOCKS_PER_SEC = " << CLOCKS_PER_SEC << endl;
	cout << "succed\n" << interval << " clocks (when CLOCKS_PER_SEC=1000,equal to ms)" << endl;
	cout << interval/CLOCKS_PER_SEC << " s" << endl;
}
int main()
{
	RBTree_property_test();
	return 0;
}

資料結構-紅黑樹資料結構-紅黑樹

文章目錄

資料結構-紅黑樹

1、紅黑樹簡介

紅黑樹的性質

紅黑樹結點

紅黑樹的5個性質

2、紅黑樹的操作

旋轉

插入操作

情況 1：z的叔結點y為紅色

情況 2：z的叔結點y為黑色的且z是一個右孩子

情況 3：z的叔結點y為黑色的且z是一個左孩子

删除操作

情況 1：x的兄弟結點w是紅色的

情況 2：x的兄弟結點w是黑色的，而且w的兩個子結點都是黑色的

情況 3：x的兄弟結點w是黑色的，w的左孩子是紅色的，w的右孩子是黑色的。

情況 4：x的兄弟結點w是黑色的，w的右孩子是紅色的

3、紅黑樹的實作

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器