linux內(nèi)存管理模塊中使用紅黑樹算法來提升虛擬內(nèi)存查找速度，源碼請參考linux內(nèi)核目錄下rbtree.c文件。

紅黑樹算法原理

在閱讀紅黑樹算法源代碼之前最好先了解紅黑樹原理。

rb_insert_color函數(shù)詳解：

void?rb_insert_color(rb_node_t?*?node,?rb_root_t?*?root)
{
	rb_node_t?*?parent,?*?gparent;

	while?((parent?=?node->rb_parent)?&&?parent->rb_color?==?RB_RED)
	{
		gparent?=?parent->rb_parent;

		if?(parent?==?gparent->rb_left)
		{
			{
				register?rb_node_t?*?uncle?=?gparent->rb_right;
				if?(uncle?&&?uncle->rb_color?==?RB_RED)
				{
					uncle->rb_color?=?RB_BLACK;
					parent->rb_color?=?RB_BLACK;
					gparent->rb_color?=?RB_RED;
					node?=?gparent;
					continue;
				}
			}

			if?(parent->rb_right?==?node)
			{
				register?rb_node_t?*?tmp;
				__rb_rotate_left(parent,?root);
				tmp?=?parent;
				parent?=?node;
				node?=?tmp;
			}

			parent->rb_color?=?RB_BLACK;
			gparent->rb_color?=?RB_RED;
			__rb_rotate_right(gparent,?root);
		}?else?{
			{
				register?rb_node_t?*?uncle?=?gparent->rb_left;
				if?(uncle?&&?uncle->rb_color?==?RB_RED)
				{
					uncle->rb_color?=?RB_BLACK;
					parent->rb_color?=?RB_BLACK;
					gparent->rb_color?=?RB_RED;
					node?=?gparent;
					continue;
				}
			}

			if?(parent->rb_left?==?node)
			{
				register?rb_node_t?*?tmp;
				__rb_rotate_right(parent,?root);
				tmp?=?parent;
				parent?=?node;
				node?=?tmp;
			}

			parent->rb_color?=?RB_BLACK;
			gparent->rb_color?=?RB_RED;
			__rb_rotate_left(gparent,?root);
		}
	}

	root->rb_node->rb_color?=?RB_BLACK;
}

注解：

??? 函數(shù)參數(shù)

??????? node：新插入的結點。

??????? root：紅黑樹的根結點。

??? 第5行：往紅黑樹中插入結點時，總是將新插入結點顏色設置為紅色。當新結點的父結點不存在或者父結點顏色為黑色時，不需要做紅黑樹調(diào)整直接跳到第63行。

??? 第7行：獲取node結點的祖父結點。

??? （第9-35行 處理node父結點是其祖父結點左子結點的情況）

??? 第12行：獲取node的叔父結點。

??? 第13-20行：當叔父結點存在并且顏色為紅色，就將node的父結點與叔父結點的顏色設成黑色，并且將node的祖父結點顏色設成紅色?，F(xiàn)在祖父結點的顏色為紅色，但祖父結點的父結點也可能為紅色，不滿足紅黑樹性質(zhì)，因此將祖父結點當做新插入的結點重新進行紅黑樹調(diào)整。

??? 第23-30行：叔父結點不存在或者顏色為黑色，此時node的祖父結點顏色必為黑色（因為node父結點顏色為紅色），針對node的父結點進行一次左旋轉(zhuǎn)，讓父結點成為node的左子結點，并交換父結點與node結點位置，使以前的父結點成為新插入的結點。

??? 第32-34得：將父結點的顏色設為黑色（此時新node的顏色還是紅色），將祖父結點的顏色設為紅色。再針對祖父結點進行一次右旋轉(zhuǎn)，此時node擁有一個黑色的父結點及紅色的兄弟結點。

??? （第36-61行處理node的父結點是其祖父結點的右子結點的情況）

??? 第37行：獲取node的叔父結點。

??? 第38行：當node的叔父結點存在并且顏色為紅色，就將node的父結點與叔父結點設置為黑色，并將node的祖父結點設置為紅色。再將祖父結點當做新插入的結點重新進行紅黑樹調(diào)整。

??? 第48-55行：如果node結點是其父結點的左子結點，就針對node的父結點進行一次右旋轉(zhuǎn)，讓其父結點成為node的右子結點，并交換父結點與node的位置，讓以前的父結點成為新插入的結點

??? 第57-59行：將父結點的顏色設為黑色（此時新node的顏色還是紅色），將祖父結點的顏色設置為紅色。再針對祖父結點進行一次左旋轉(zhuǎn)，此時node擁有一個黑色的父結點及紅色的兄弟結點。

??? 第63行：將根結點的顏色設為黑色。這一步是有必要的，當新插入的結點為根結點或者在樹調(diào)整過程中將根結點顏色變成了紅色，這一行將根結點的顏色設成黑色。

?rb_erase函數(shù)詳解：

void?rb_erase(rb_node_t?*?node,?rb_root_t?*?root)
{
	rb_node_t?*?child,?*?parent;
	int?color;

	if?(!node->rb_left)
		child?=?node->rb_right;
	else?if?(!node->rb_right)
		child?=?node->rb_left;
	else
	{
		rb_node_t?*?old?=?node,?*?left;

		node?=?node->rb_right;
		while?((left?=?node->rb_left))
			node?=?left;
		child?=?node->rb_right;
		parent?=?node->rb_parent;
		color?=?node->rb_color;

		if?(child)
			child->rb_parent?=?parent;
		if?(parent)
		{
			if?(parent->rb_left?==?node)
				parent->rb_left?=?child;
			else
				parent->rb_right?=?child;
		}
		else
			root->rb_node?=?child;

		if?(node->rb_parent?==?old)
			parent?=?node;
		node->rb_parent?=?old->rb_parent;
		node->rb_color?=?old->rb_color;
		node->rb_right?=?old->rb_right;
		node->rb_left?=?old->rb_left;

		if?(old->rb_parent)
		{
			if?(old->rb_parent->rb_left?==?old)
				old->rb_parent->rb_left?=?node;
			else
				old->rb_parent->rb_right?=?node;
		}?else
			root->rb_node?=?node;

		old->rb_left->rb_parent?=?node;
		if?(old->rb_right)
			old->rb_right->rb_parent?=?node;
		goto?color;
	}

	parent?=?node->rb_parent;
	color?=?node->rb_color;

	if?(child)
		child->rb_parent?=?parent;
	if?(parent)
	{
		if?(parent->rb_left?==?node)
			parent->rb_left?=?child;
		else
			parent->rb_right?=?child;
	}
	else
		root->rb_node?=?child;

?color:
	if?(color?==?RB_BLACK)
		__rb_erase_color(child,?parent,?root);
}

注解：

??? 函數(shù)參數(shù)：

? ? ? ??node： 將要刪除的結點

? ? ? ? root： 紅黑樹的根結點

??? （第6-9行處理被刪結點至多只有一個子結點的情況，并找出不為空的子結點）

? ? 第6-7行：判斷node的左子結點是否存在，如果不存在child針指就指向右子結點（右子結點也可能不存在）。

??? 第8-9行：判斷node的右子結點是否存在，如果不存在child指針就指向其左子結點。

??? （第11-53行 處理被刪結點有兩個非空子結點的情況。當結點存在兩個非空子結點時就找出其左子樹中元素最大的結點或者右子樹中元素最小的結點，并將該結點替換到將要被刪除的結點位置上，再刪除元素最大或者最小的結點。這時就將刪除有兩個非空子結點的問題變成刪除至多只有一個非空子結點的問題。linux內(nèi)存管理模塊中的紅黑樹是按結點所在的內(nèi)存首地址來排序存儲的，如父結點的內(nèi)存首地址一定會大于其左子結點首地址且小于右子結點首地址，因此在替換結點時只替換結點的位置不能改變結點的首地址）。

??? 第12行：保存node到old變量中。

??? 第14-16行：找出node的右子樹中首地址最小的結點。如果找到就將該結點當做將要被刪除的結點。

??? 第17行：獲取node的右子結點，經(jīng)過第14-16行的處理現(xiàn)在node結點的首地址最小，所以node不可能存在左子結點，但右子結點可能會存在。

??? 第18行：獲取node的父結點。

??? 第19行：獲取node的顏色屬性。

??? 第21-22行：如果node的子結點存在，就設置其子結點的父結點為node的父結點（因為node結點將要被刪除）。

??? 第23-29行：如果node的父結點存在，當node是其父結點的左子結點時就設置node的子結點為其父結點的左子結點，否則就設置為其父結點的右子結點。

??? 第30-31行：這種情況不可能會發(fā)生。

??? 第33-34行：如果node等于old，說明old（old中保存有rb_erase函數(shù)中node參數(shù)的值，即要被替換的結點）的右子結點沒有子結點，將父結點指向node結點（當node等于old時，在node替換old之后，node與其子結點的關系保持不變）。

??? （第35-38行 這里將node結點替換掉old結點）

??? 第35行：設置node的父結點為old結點的父結點。

??? 第36行：將old結點顏色替換到node結點中。

??? 第37行：將node的右子結點設置為old的右子結點。

??? 第38行：將node的左子結點設置為old的左子結點。

??? 第40-46行：如果old的父結點存在，當old是其父結點的左子結點時就將node變成其父結點的左子結點，否則為其父結點的右子結點。

??? 第47行：如果old為根結點就設置node為根結點。

??? 第49行：將node設置為old左子結點的父結點。

??? 第50-51行：如果old的右子結點存在，設置node為old右子結點的父結點。

??? 第52行：跳轉(zhuǎn)到70行進一步處理。

??? （第55-68行 進一步處理被刪結點至多只有一個非空子結點的情況）

??? 第55-56行：獲取node的父結點及顏色。

??? 第58-59行：如果node的子結點存在，就設置其子結點的父結點為node的父結點。

??? 第60-66行：node的父結點存在且node是其父結點的左子結點時就設置node的子結點為父結點的左了結點，否則為父結點的右子結點。

??? 第67-68行：當node為根結點時，刪除node后，其子結點成為根結點。

??? 第70-72行：如果被刪結點顏色為紅色，此時不影響紅黑樹性質(zhì)，否則調(diào)用__rb_erase_color函數(shù)進一步處理。

??? 當rb_erase函數(shù)刪除有兩個非空子結點的結點時比較復雜，難以理解。下面提供兩張刪除結點的示例圖便于理解，本想提供flash動畫的，但不知道怎么發(fā)到博客上來。

???? 示例1：假設被刪結點為父結點的左子結點，且被刪結點的右子結點沒有子結點

??? 示例2：假設被刪結點是父結點的右子結點，且被刪結點的右子結點存在兩個非空子結點

__rb_erase_color函數(shù)詳解：

static?void?__rb_erase_color(rb_node_t?*?node,?rb_node_t?*?parent,
			?????rb_root_t?*?root)
{
	rb_node_t?*?other;

	while?((!node?||?node->rb_color?==?RB_BLACK)?&&?node?!=?root->rb_node)
	{
		if?(parent->rb_left?==?node)
		{
			other?=?parent->rb_right;
			if?(other->rb_color?==?RB_RED)
			{
				other->rb_color?=?RB_BLACK;
				parent->rb_color?=?RB_RED;
				__rb_rotate_left(parent,?root);
				other?=?parent->rb_right;
			}
			if?((!other->rb_left?||
			?????other->rb_left->rb_color?==?RB_BLACK)
			????&&?(!other->rb_right?||
				other->rb_right->rb_color?==?RB_BLACK))
			{
				other->rb_color?=?RB_RED;
				node?=?parent;
				parent?=?node->rb_parent;
			}
			else
			{
				if?(!other->rb_right?||
				????other->rb_right->rb_color?==?RB_BLACK)
				{
					register?rb_node_t?*?o_left;
					if?((o_left?=?other->rb_left))
						o_left->rb_color?=?RB_BLACK;
					other->rb_color?=?RB_RED;
					__rb_rotate_right(other,?root);
					other?=?parent->rb_right;
				}
				other->rb_color?=?parent->rb_color;
				parent->rb_color?=?RB_BLACK;
				if?(other->rb_right)
					other->rb_right->rb_color?=?RB_BLACK;
				__rb_rotate_left(parent,?root);
				node?=?root->rb_node;
				break;
			}
		}
		else
		{
			other?=?parent->rb_left;
			if?(other->rb_color?==?RB_RED)
			{
				other->rb_color?=?RB_BLACK;
				parent->rb_color?=?RB_RED;
				__rb_rotate_right(parent,?root);
				other?=?parent->rb_left;
			}
			if?((!other->rb_left?||
			?????other->rb_left->rb_color?==?RB_BLACK)
			????&&?(!other->rb_right?||
				other->rb_right->rb_color?==?RB_BLACK))
			{
				other->rb_color?=?RB_RED;
				node?=?parent;
				parent?=?node->rb_parent;
			}
			else
			{
				if?(!other->rb_left?||
				????other->rb_left->rb_color?==?RB_BLACK)
				{
					register?rb_node_t?*?o_right;
					if?((o_right?=?other->rb_right))
						o_right->rb_color?=?RB_BLACK;
					other->rb_color?=?RB_RED;
					__rb_rotate_left(other,?root);
					other?=?parent->rb_left;
				}
				other->rb_color?=?parent->rb_color;
				parent->rb_color?=?RB_BLACK;
				if?(other->rb_left)
					other->rb_left->rb_color?=?RB_BLACK;
				__rb_rotate_right(parent,?root);
				node?=?root->rb_node;
				break;
			}
		}
	}
	if?(node)
		node->rb_color?=?RB_BLACK;
}

注解：

??? 函數(shù)參數(shù)：

??????? node：被刪結點的子結點

??????? parent：被刪結點的父結點

??????? root：紅黑樹根結點

??? 第6行：如果node是根結點或者其顏色為紅色while循環(huán)結束（調(diào)用__rb_erase_color函數(shù)的條件是被刪結點顏色為黑色，直接將被刪結點的子結點node置為黑色就滿足紅黑樹性質(zhì)）。

??? （第8-47行 處理node是其父結點的左子結點情況）

??? 第10行：獲取node的兄弟結點，保存到other變量中。

??? 第11-17行：當other結點顏色為紅色時（other父結點顏色必為黑），將其父結點置為紅色，other結點置為黑色。并針對其父結點進行一次左旋轉(zhuǎn)讓other的父結點成為它的左子結點（此種情況的詳細步驟請參考上面提起過的紅黑樹原理網(wǎng)站中刪除結點的情況2），并從新獲取node的兄弟結點。

??? 第18-26行：如果other的兩個子結點都為黑色，這時就將other置為紅色。重新在node的父結點上做紅黑樹調(diào)整（參考紅黑樹原理網(wǎng)站中刪除結點的情況4）。

??? （第28-46行 處理other的子結點顏色為紅色的情況）

??? 第29-38行：當other的右子結點為黑色時（此時other的左子結點必為紅色），將other的左子結點置為黑色，other置為紅色并針對other進行一次右旋轉(zhuǎn)，使other的左子結點成為other的父結點（參考紅黑樹原理網(wǎng)站中刪除結點的情況5），重新獲取node的兄弟結點，保存到other變量中。

??? 第39-44行：設置other的顏色為其父結點的顏色，將父結點的顏色置為黑色，設置other的右子結點顏色為黑色并針對node的父結點進行一次左旋轉(zhuǎn)（參考紅黑樹原理網(wǎng)站中刪除結點的情況6）。

??? 第49-87行：這里的處理步驟與8-47行類似。

??? 第89-90行：將根結點置為黑色。