資料結構與算法三紅黑樹和二叉樹

紅黑樹
- 定義和性質
- 應用
- 紅黑樹的操作
- - 建立代碼
  - 左旋
  - - 代碼實作：
  - 右旋
  - - 代碼實作
  - 添加
  - 删除
二叉排序樹
- 性質
- 優點
- 缺點
- 實作代碼

紅黑樹

定義和性質

R-B Tree，全稱是Red-Black Tree，又稱為“紅黑樹”，它一種自平衡的二叉查找樹。紅黑樹的每個節點上都有存儲位表示節點的顔色，可以是紅(Red)或黑(Black)。

性質：

資料結構與算法(三) 紅黑樹與二叉查找樹紅黑樹二叉排序樹

應用

用途

運用紅黑樹主要用其兩個性質：

A.通過鍵值對方式存儲資訊

運用：

1、多個用戶端與伺服器建立連結時，此時連結為socket實質就是一個int型數字。但是每個用戶端都有自己的id，此時socket與用戶端id有個映射關系。若有大量用戶端連結時，我們就可采用紅黑樹的key-value（socket，id）方式來存儲這個資訊。以便後期查找socket與id之間的互相查找；

2、記憶體中使用：

整塊記憶體還沒有沒配時，mallo配置設定記憶體時将其假如紅黑樹中，後期free時就從紅黑樹找對應的塊将其釋放；

B.使用其中序周遊的特點(按順序存儲)

1、程序的排程：

有些程序處于等待狀态(在某個時刻會運作)，存入紅黑樹中。當在某個時刻準備運作時，利用紅黑樹的中序周遊，将其小于此時間段的程序拿取出來，準備執行。

紅黑樹的操作

建立代碼

typedef int KEY_TYPE;

typedef struct _rbtree_node {
	//此為紅黑樹的性質
	unsigned char color;
	struct _rbtree_node *right;
	struct _rbtree_node *left;
	struct _rbtree_node *parent;
	
	KEY_TYPE key;
	void *value;
} rbtree_node;

typedef struct _rbtree {
	rbtree_node *root;
	rbtree_node *nil; //NULL 所有的葉子結點都指向他 
} rbtree;

左旋

左旋和右旋都是為了調節二叉樹平衡而存在的。

以x為節點進行左旋 
                              z
   x                          /                  
  / \      --(左旋)-->       x
 y   z                      /
                           y

對x進行左旋，意味着，将“x的右孩子”設為“x的父親節點”；即，将 x變成了一個左節點(x成了為z的左孩子)！。是以，左旋中的“左”，意味着“被旋轉的節點将變成一個左節點”。

資料結構與算法(三) 紅黑樹與二叉查找樹紅黑樹二叉排序樹

對x進行左旋，意味着"将x變成一個左節點"。

代碼實作：

//左旋
void rbtree_left_rotate(rbtree *T, rbtree_node *x) {

	rbtree_node *y = x->right;  // x  --> y  ,  y --> x,   right --> left,  left --> right
								//假設的前提：x的右孩子為y
	x->right = y->left; // 将 “y的左孩子” 設為 “x的右孩子”，即 将β設為x的右孩子
	if (y->left != T->nil) { // 将 “x” 設為 “y的左孩子的父親”，即 将β的父親設為x
		y->left->parent = x;
	}

	y->parent = x->parent; //将 “x的父親” 設為 “y的父親”
	if (x->parent == T->nil) { //若x父結點為空結點，将y設為根節點
		T->root = y;
	} else if (x == x->parent->left) { //若x為其父結點的左孩子，則将Y設為“x父結點的左孩子”
		x->parent->left = y;
	} else { //（若x為其父結點的右孩子）則将y設為“x父結點的右孩子””
		x->parent->right = y;
	}

	y->left = x; //将x設為y的左孩子
	x->parent = y; //将x的父結點設為y
}

詳情案例：

資料結構與算法(三) 紅黑樹與二叉查找樹紅黑樹二叉排序樹

右旋

左旋和右旋都是為了調節二叉樹平衡而存在的。

(以x為節點進行右旋)
                              y
   x                            \                 
  / \      --(右旋)-->           x
 y   z                            \
                                   z

對x進行右旋，意味着，将“x的左孩子”設為“x的父親節點”；即，将 x變成了一個右節點(x成了為y的右孩子)！是以，右旋中的“右”，意味着“被旋轉的節點将變成一個右節點”。

資料結構與算法(三) 紅黑樹與二叉查找樹紅黑樹二叉排序樹

對x進行左旋，意味着"将x變成一個左節點"。

代碼實作

//右旋
void rbtree_right_rotate(rbtree *T, rbtree_node *y) {

	rbtree_node *x = y->left; // 前提：這裡假設y的左孩子為x。下面開始正式操作

	y->left = x->right; // 将 “x的右孩子” 設為 “y的左孩子”，即 将β設為y的左孩子
	if (x->right != T->nil) {
		x->right->parent = y; // 将 “y” 設為 “x的右孩子的父親”，即 将β的父親設為y
	}

	x->parent = y->parent; // 将 “y的父親” 設為 “x的父親”
	if (y->parent == T->nil) {
		T->root = x; // 情況1：如果 “y的父親” 是空節點，則将x設為根節點
	} else if (y == y->parent->right) {
		y->parent->right = x; // 情況2：如果 y是它父節點的右孩子，則将x設為“y的父節點的左孩子”
	} else {
		y->parent->left = x; // 情況3：(y是它父節點的左孩子) 将x設為“y的父節點的左孩子”
	}

	x->right = y; // 将 “y” 設為 “x的右孩子”
	y->parent = x;  // 将 “y的父節點” 設為 “x”
}

詳情案例：

資料結構與算法(三) 紅黑樹與二叉查找樹紅黑樹二叉排序樹

仔細觀察上面"左旋"和"右旋"的示意圖。我們能清晰的發現，它們是對稱的。無論是左旋還是右旋，被旋轉的樹，在旋轉前是二叉查找樹，并且旋轉之後仍然是一顆二叉查找樹。

資料結構與算法(三) 紅黑樹與二叉查找樹紅黑樹二叉排序樹

添加

為了滿足紅黑樹的5條性質，一般插入結點時，将結點設定為紅色，這樣不會改變黑色的高度，這樣更容易滿足性質。

若目前結點為紅色，待插入的位置其父結點也為紅色，就要進行調整，recolor。

需要調整分為三種情況：

資料結構與算法(三) 紅黑樹與二叉查找樹紅黑樹二叉排序樹

(Case 1)叔叔是紅色

1.1 現象說明

目前節點(即，被插入節點)的父節點是紅色，且目前節點的祖父節點的另一個子節點（叔叔節點）也是紅色。

1.2 處理政策

(01) 将“父節點”設為黑色。

(02) 将“叔叔節點”設為黑色。

(03) 将“祖父節點”設為“紅色”。

(04) 将“祖父節點”設為“目前節點”(紅色節點)；即，之後繼續對“目前節點”進行操作。

資料結構與算法(三) 紅黑樹與二叉查找樹紅黑樹二叉排序樹

2. (Case 2)叔叔是黑色，且目前節點是右孩子

2.1 現象說明

目前節點(即，被插入節點)的父節點是紅色，叔叔節點是黑色，且目前節點是其父節點的右孩子

2.2 處理政策

(01) 将“父節點”作為“新的目前節點”。

(02) 以“新的目前節點”為支點進行左旋。

資料結構與算法(三) 紅黑樹與二叉查找樹紅黑樹二叉排序樹

3. (Case 3)叔叔是黑色，且目前節點是左孩子

3.1 現象說明

目前節點(即，被插入節點)的父節點是紅色，叔叔節點是黑色，且目前節點是其父節點的左孩子

3.2 處理政策

(01) 将“父節點”設為“黑色”。

(02) 将“祖父節點”設為“紅色”。

(03) 以“祖父節點”為支點進行右旋。

資料結構與算法(三) 紅黑樹與二叉查找樹紅黑樹二叉排序樹

void rbtree_insert(rbtree *T, rbtree_node *z) {
//紅黑樹隻能在葉子節點插入
	rbtree_node *y = T->nil;
	rbtree_node *x = T->root;

	while (x != T->nil) { //查找待插入的位置
		y = x;
		if (z->key < x->key) {
			x = x->left;
		} else if (z->key > x->key) {
			x = x->right;
		} else { //Exist
			return ;
		}
	}

	z->parent = y; //
	if (y == T->nil) { //将z結點插入其中
		T->root = z;
	} else if (z->key < y->key) {
		y->left = z;
	} else {
		y->right = z;
	}

	z->left = T->nil;
	z->right = T->nil;
	z->color = RED; //新結點置成紅色

	rbtree_insert_fixup(T, z); //調整結點
}

//調整樹中的z結點
void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {

//樹的層級很多，用循環始終保持疊代 若z的父結點為紅色紀要一直疊代
	while (z->parent->color == RED) { //z ---> RED
		if (z->parent == z->parent->parent->left) { //若parent為祖父節點的左子樹，便于區分左旋右旋
			rbtree_node *y = z->parent->parent->right; //擷取z的叔父結點
			if (y->color == RED) {//情況1：若叔父結點為紅色，(若z的父節點和叔父結點都為紅色，則祖父結點一定為黑色，紅黑樹性質決定的)
				z->parent->color = BLACK; //将父結點/叔父結點置黑色
				y->color = BLACK;
				z->parent->parent->color = RED; //祖父結點置紅

				z = z->parent->parent; //z --> RED //注意：此為疊代的關鍵：z指向了其祖父節點，後期對祖父節點進行疊代
			} else { //情況2： 若叔父結點為黑色，

				if (z == z->parent->right) { //且z為父結點的右孩子(實質：祖父節點到叔父結點的黑高大于祖父節點到z結點的黑高)
					z = z->parent; //
					rbtree_left_rotate(T, z); //左旋，
				}

				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				rbtree_right_rotate(T, z->parent->parent);
			}
		}else {
			rbtree_node *y = z->parent->parent->left;
			if (y->color == RED) {
				z->parent->color = BLACK;
				y->color = BLACK;
				z->parent->parent->color = RED;

				z = z->parent->parent; //z --> RED
			} else {
				if (z == z->parent->left) {
					z = z->parent;
					rbtree_right_rotate(T, z);
				}

				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				rbtree_left_rotate(T, z->parent->parent);
			}
		}
		
	}

	T->root->color = BLACK;
}

删除

二叉排序樹

性質

二叉查找樹（BST）具備什麼特性呢？

1.左子樹上所有結點的值均小于或等于它的根結點的值。

2.右子樹上所有結點的值均大于或等于它的根結點的值。

3.左、右子樹也分别為二叉排序樹。

優點

利用二分查找的思想，使得查找所需的最大次數等于二叉查找樹的高度。插入結點時，也是一層一層的比較大小，找到新結點适合插入的位置。

缺點

當插入的值幾乎都比根節點小/大時，此時的二叉樹就類似與連結清單的結構，這樣效率就大打折扣。

資料結構與算法(三) 紅黑樹與二叉查找樹紅黑樹二叉排序樹

為了解決：二叉查找樹多次插入結點可能導緻不平衡的問題，就建立了自平衡的二叉查找樹，也就是紅黑樹。

實作代碼

建立二叉樹：

typedef int KEY_VALUE;

struct bstree_node {
	KEY_VALUE data;
	struct bstree_node *left;
	struct bstree_node *right;
};

struct bstree {
	struct bstree_node *root;
};

struct bstree_node *bstree_create_node(KEY_VALUE key) {
	struct bstree_node *node = (struct bstree_node*)malloc(sizeof(struct bstree_node));
	if (node == NULL) {
		assert(0);
	}
	node->data = key;
	node->left = node->right = NULL;

	return node;
}

二叉樹的插入：

int bstree_insert(struct bstree *T, int key) {

	assert(T != NULL);

	if (T->root == NULL) {//若為空樹，直接指派
		T->root = bstree_create_node(key);
		return 0;
	}

	struct bstree_node *node = T->root;
	struct bstree_node *tmp = T->root;

//查找該插入的位置
	while (node != NULL) { //直到Node為底層了
		tmp = node;
		if (key < node->data) {
			node = node->left;
		} else {
			node = node->right;
		}
	}

	if (key < tmp->data) {
		tmp->left = bstree_create_node(key);
	} else {
		tmp->right = bstree_create_node(key);
	}
	
	return 0;
}

二叉樹的中序周遊：

int bstree_traversal(struct bstree_node *node) {
	if (node == NULL) return 0;
	
	bstree_traversal(node->left);
	printf("%4d ", node->data);
	bstree_traversal(node->right);
}

紅黑樹的定義：

資料結構與算法(三) 紅黑樹與二叉查找樹紅黑樹二叉排序樹

參考資料：

參考資料一

參考資料二

資料結構與算法(三) 紅黑樹與二叉查找樹紅黑樹二叉排序樹

資料結構與算法三紅黑樹和二叉樹

紅黑樹

定義和性質

應用

紅黑樹的操作

建立代碼

左旋

代碼實作：

右旋

代碼實作

添加

删除

二叉排序樹

性質

優點

缺點

實作代碼

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

【資料結構】醫院選址

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

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

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

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

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

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

Dijkstra--簡易版（最短路徑）

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

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

hdu7108哈希

資料結構與算法(三) 紅黑樹與二叉查找樹紅黑樹二叉排序樹

資料結構與算法三 紅黑樹和二叉樹

紅黑樹

定義和性質

應用

紅黑樹的操作

建立代碼

左旋

代碼實作：

右旋

代碼實作

添加

删除

二叉排序樹

性質

優點

缺點

實作代碼

繼續閱讀

資料結構與算法三紅黑樹和二叉樹