樹算法之紅黑樹
羅朝輝（http://www.shnenglu.com/kesalin）
轉載請注明出處
紅黑樹本質是二叉查找樹的一種，它的性能高于普通的二叉查找樹，即使是在最壞的情況下也能保證時間復雜度為O(lgn)。紅黑樹在每個結點上增加一個存儲位表示結點的顏色（或紅或黑，故稱紅黑樹）。通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹可以保證沒有一條路徑會比其他路徑長出兩倍，因而是接近平衡的。
紅黑樹的每個結點至少包含五個域：color，key，left，right 和 parent（一般我們都會在結點中存儲額外的數據 data，但前面的五個域是必不可少的），如果某個結點沒有子結點或者
結節點，則將相應的指針設置為空值（NIL，注意不是 NULL，NIL是一個特定的空結點對象，類似于Obj-C 中 Nil對象）。我們將這些 NIL 當作葉子
結點（在實際處理過程中，往往將最底層的孩子
結點和根
結點的父親都指向同一個 NIL
結點，
以便于處理紅黑樹代碼中的邊界條件），而將其它
結點當作內結點。
滿足如下 5 個性質的二叉樹就是一顆紅黑樹：
一，每個結點只有一種顏色，或紅色或黑色；
二，根結點是黑色的；
三，每個葉結點是黑色的；
四，如果一個結點是紅色的，那么它的兩個孩子結點必須是黑色的；
五，對每個結點，從該結點到其子孫結點的所有路徑上包含相同數目 H 的黑色結點， H 即為該節點的高度。
紅黑樹的實現，
linux 內核中有現成實現算法，園子里也有不少同學（
那誰 等）實現過。在這里我重復制造一下輪子，當然我這里的實現與前面提到的有些不同，這里是按照《算法導論》上的算法描述實現的。
具體算法過程，請參考《算法導論》中紅黑樹那一章。
下面先來看
看頭文件中包含的數據結構，接口函數：
#ifndef __RED_BLACK_TREE_H__
#define __RED_BLACK_TREE_H__
enum RBColor
{
RB_Red,
RB_Black,
};
struct RBNode
{
RBColor color;
int key;
RBNode* leftChild;
RBNode* rightChild;
RBNode* parent;
};
typedef RBNode* RBTree;
RBNode* RBTree_nil();
// 最小關鍵字元素
RBNode* RBTree_minimum(RBNode* node);
// 最大關鍵字元素
RBNode* RBTree_maximum(RBNode* node);
// 中序遍歷中的前驅
RBNode* RBTree_predecessor(RBNode* node);
// 中序遍歷中的后繼
RBNode* RBTree_successor(RBNode* node);
void RBTree_insert(RBTree* tree, RBNode* node);
RBNode* RBTree_delete(RBTree* tree, RBNode* node);
RBNode* RBTree_search(const RBTree tree, int key);
void RBTree_print(RBTree tree, int her = 1);
#endif // __RED_BLACK_TREE_H__下面來看具體實現：
#include "RedBlackTree.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
static RBNode RBNode_Nil = {RB_Black, 0, 0, 0, 0};
RBNode* RBTree_nil()
{
return &RBNode_Nil;
}
void RBTree_print(RBTree tree, int her)
{
int i;
RBNode* node = tree;
assert(node);
if (node != &RBNode_Nil) {
for (i = 0; i < her; i++) {
printf(" ");
}
printf("第 %d 層， %d(%c)\n",
her, node->key, node->color == RB_Black ? 'B' : 'R');
if (node->leftChild != &RBNode_Nil) {
RBTree_print(node->leftChild, her + 1);
}
if (node->rightChild != &RBNode_Nil) {
RBTree_print(node->rightChild, her + 1);
}
}
}
// 最小關鍵字元素
RBNode* RBTree_minimum(RBNode* node)
{
assert(node);
RBNode* temp = node;
while (temp->leftChild != &RBNode_Nil) {
temp = temp->leftChild;
}
return temp;
}
// 最大關鍵字元素
RBNode* RBTree_maximum(RBNode* node)
{
assert(node);
RBNode* temp = node;
while (temp->rightChild != &RBNode_Nil) {
temp = temp->rightChild;
}
return temp;
}
// 中序遍歷中的前驅
RBNode* RBTree_predecessor(RBNode* node)
{
assert(node);
RBNode* child = node->leftChild;
// 沒有左孩子，返回自身
if (child == &RBNode_Nil) {
return node;
}
// 只有左孩子，則左孩子是其直接前驅
else if (child->rightChild == &RBNode_Nil) {
return child->leftChild;
}
// 左右孩子均有，則右孩子樹中最大的元素為其直接前驅
else {
return RBTree_maximum(child->rightChild);
}
}
// 中序遍歷中的后繼
RBNode* RBTree_successor(RBNode* node)
{
// 有右孩子，則右孩子樹中最小的元素為其直接后繼
if (node->rightChild != &RBNode_Nil) {
return RBTree_minimum(node->rightChild);
}
// 沒有右孩子，向上找到的第一個左分支節點為其直接后繼，
// 即 node 為其直接后繼的左孩子樹中的最大元素。
RBNode* temp = node;
RBNode* parent = temp->parent;
while (parent != &RBNode_Nil && temp == parent->rightChild) {
temp = parent;
parent = temp->parent;
}
return parent;
}
RBNode* RBTree_search(const RBTree tree, int key)
{
RBNode* node = tree;
while (node != &RBNode_Nil) {
if (node->key == key) {
return node;
}
else if (node->key < key) {
node = node->rightChild;
}
else {
node = node->leftChild;
}
}
return &RBNode_Nil;
}
// 左旋
// node right
// / \ / \
// a right --> node c
// / \ / \
// b c a b
//
void RBTree_left_rotate(RBTree* tree, RBNode* node)
{
assert(node->rightChild && (*tree)->parent == &RBNode_Nil);
RBNode* right = node->rightChild;
// set b
node->rightChild = right->leftChild;
if (right->leftChild != &RBNode_Nil) {
right->leftChild->parent = node;
}
right->parent = node->parent;
if (node->parent == &RBNode_Nil) {
*tree = right;
}
else if (node->parent->leftChild == node) {
node->parent->leftChild = right;
}
else {
node->parent->rightChild = right;
}
right->leftChild = node;
node->parent = right;
}
// 右旋
// node left
// / \ / \
// left c --> a node
// / \ / \
// a b b c
//
void RBTree_right_rotate(RBTree* tree, RBNode* node)
{
assert(node->leftChild && (*tree)->parent == &RBNode_Nil);
RBNode* left = node->leftChild;
// set b
node->leftChild = left->rightChild;
if (left->rightChild != &RBNode_Nil) {
left->rightChild->parent = node;
}
left->parent = node->parent;
if (node->parent == &RBNode_Nil) {
*tree = left;
}
else if (node->parent->leftChild == node) {
node->parent->leftChild = left;
}
else {
node->parent->rightChild = left;
}
left->rightChild = node;
node->parent = left;
}
// 插入調整
void RBTree_insert_fixup(RBTree* tree, RBNode* node)
{
assert(tree && node);
RBNode* parent = NULL;
RBNode* uncle = NULL;
RBNode* grand = NULL;
RBNode* temp = NULL;
parent = node->parent;
while (parent->color == RB_Red) {
// 根據紅黑樹性質，以及 node 的父親的顏色為紅色，
// 可以肯定 node 的祖父節點一定存在
grand = parent->parent;
// 確定叔父節點
if (parent == grand->leftChild) {
uncle = grand->rightChild;
// case 1: 叔父節點為紅色
// grand(B) new node -> grand(R)
// / \ / \
// parent(R) uncle(R) --> node(B) uncle(B)
// / \ / \ / \ / \
// a node(R) d e parent node(R) d e
// / \ / \
// b c b c
//
if (uncle->color == RB_Red) {
parent->color = RB_Black;
uncle->color = RB_Black;
grand->color = RB_Red;
node = grand;
parent = node->parent;
}
// case 2, case 3：叔父節點為黑色
// case 2 ---> case 3 --> done
// parent is as new node
// grand(B) grand(B) node(B)
// / \ / \ / \
// parent(R) d node(R) d parent(R) grand(R)
// / \ / \ / \ / \
// a node(R) parent(R) c a b c d
// / \ / \
// b c a b
//
else {
// 將 case 2 裝換成 case 3
if (parent->rightChild == node) {
RBTree_left_rotate(tree, parent);
temp = parent;
parent = node;
node = temp;
}
// case 3
parent->color = RB_Black;
grand->color = RB_Red;
RBTree_right_rotate(tree, grand);
}
}
else {
// 與上面的情況對稱
uncle = grand->leftChild;
if (uncle->color == RB_Red) {
parent->color = RB_Black;
uncle->color = RB_Black;
grand->color = RB_Red;
node = grand;
parent = node->parent;
}
else {
// 將 case 2 裝換成 case 3
if (parent->leftChild == node) {
RBTree_right_rotate(tree, parent);
temp = parent;
parent = node;
node = temp;
}
// case 3
parent->color = RB_Black;
grand->color = RB_Red;
RBTree_left_rotate(tree, grand);
}
}
}
(*tree)->color = RB_Black;
}
// 將節點 node 插入樹 tree 內，然后將 node 著色為紅色，此時，樹可能不再
// 滿足紅黑樹性質，因此調用 RBTree_insert_fixup 來對節點重新著色調整。
void RBTree_insert(RBTree* tree, RBNode* node)
{
assert(tree && node);
RBNode* parent = &RBNode_Nil;
RBNode* temp = *tree;
// 像二叉樹一樣，在樹中查找適當的位置插入
while (temp != &RBNode_Nil) {
parent = temp;
if (node->key < temp->key) {
temp = temp->leftChild;
}
else {
temp = temp->rightChild;
}
}
node->parent = parent;
// 樹為空
if (parent == &RBNode_Nil) {
*tree = node;
}
else if (node->key < parent->key) {
parent->leftChild = node;
}
else {
parent->rightChild = node;
}
// 為節點著色
node->leftChild = &RBNode_Nil;
node->rightChild = &RBNode_Nil;
node->color = RB_Red;
// 調整樹使之滿足紅黑樹性質
RBTree_insert_fixup(tree, node);
}
// 刪除調整
void RBTree_delete_fixup(RBTree* tree, RBNode* node)
{
RBNode* brother = NULL;
RBNode* parent = NULL;
while (node != *tree && node->color == RB_Black) {
parent = node->parent;
// 確定兄弟節點
if (node == parent->leftChild) {
brother = parent->rightChild;
// case 1: 兄弟節點為紅色
if (brother->color == RB_Red) {
brother->color = RB_Black;
parent->color = RB_Red;
RBTree_left_rotate(tree, parent);
brother = node->parent->rightChild;
}
// case 2: 兄弟節點的兩孩子均為黑色
if (brother->leftChild->color == RB_Black
&& brother->rightChild->color == RB_Black) {
brother->color = RB_Red;
node = parent;
}
else {
// case 3: 兄弟節點的左孩子為紅色，右孩子為黑色
if (brother->rightChild->color == RB_Black) {
brother->leftChild->color = RB_Black;
brother->color = RB_Red;
RBTree_right_rotate(tree, brother);
brother = node->parent->rightChild;
}
// case 4:兄弟節點的右孩子為紅色
brother->color = parent->color;
parent->color = RB_Black;
brother->rightChild->color = RB_Black;
RBTree_left_rotate(tree, parent);
node = *tree;
}
}
else {
brother = node->parent->leftChild;
// case 1: 兄弟節點為紅色
if (brother->color == RB_Red) {
brother->color = RB_Black;
parent->color = RB_Red;
RBTree_right_rotate(tree, parent);
brother = node->parent->leftChild;
}
// case 2: 兄弟節點的兩孩子均為黑色
if (brother->leftChild->color == RB_Black
&& brother->rightChild->color == RB_Black) {
brother->color = RB_Red;
node = parent;
}
else {
// case 3: 兄弟節點的左孩子為紅色，右孩子為黑色
if (brother->rightChild->color == RB_Black) {
brother->leftChild->color = RB_Black;
brother->color = RB_Red;
RBTree_left_rotate(tree, brother);
brother = node->parent->rightChild;
}
// case 4:兄弟節點的右孩子為紅色
brother->color = parent->color;
parent->color = RB_Black;
brother->leftChild->color = RB_Black;
RBTree_right_rotate(tree, parent);
node = *tree;
}
}
}
node->color = RB_Black;
}
// 刪除
RBNode* RBTree_delete(RBTree* tree, RBNode* node)
{
RBNode* successor = NULL;
RBNode* temp = NULL;
if (node->leftChild == &RBNode_Nil || node->rightChild == &RBNode_Nil) {
successor = node;
}
else {
successor = RBTree_successor(node);
}
if (successor->leftChild != &RBNode_Nil) {
temp = successor->leftChild;
}
else {
temp = successor->rightChild;
}
temp->parent = successor->parent;
if (successor->parent == &RBNode_Nil) {
*tree = temp;
}
else {
if (successor == successor->parent->leftChild) {
successor->parent->leftChild = temp;
}
else {
successor->parent->rightChild = temp;
}
}
if (successor != node) {
node->key = successor->key;
}
if (successor->color == RB_Black) {
RBTree_delete_fixup(tree, temp);
}
return successor;
}
測試代碼，測試數組中的數字與測試步驟是經過仔細挑選的，以確保各個分支都可以測試到：
void test_redblacktree_delete(RBTree* tree, int key)
{
RBNode* node = RBTree_search(*tree, key);
assert(node != RBTree_nil());
printf("\n刪除節點 %d \n", node->key);
node = RBTree_delete(tree, node);
free(node);
RBTree_print(*tree);
}
void test_redblacktree()
{
const int length = 14;
int array[length] = {
2, 3, 4, 6, 7, 11, 9, 18, 12, 14, 19, 17, 22, 20
};
int i;
RBTree tree = RBTree_nil();
RBNode* node = NULL;
// 插入節點生成樹
for (i = 0; i < length; i++) {
node = (RBNode*)malloc(sizeof(RBNode));
node->key = array[i];
node->color = RB_Red;
node->parent = RBTree_nil();
node->leftChild = RBTree_nil();
node->rightChild = RBTree_nil();
RBTree_insert(&tree, node);
}
RBTree_print(tree);
// 插入測試
node = (RBNode*)malloc(sizeof(RBNode));
node->key = 21;
printf("\n插入節點 %d\n", node->key);
RBTree_insert(&tree, node);
RBTree_print(tree);
// 查找測試
i = 6;
node = RBTree_search(tree, i);
if (node != RBTree_nil()) {
printf("\n在紅黑樹中找到節點 %d\n", node->key);
}
else {
printf("\n在紅黑樹中找不到節點 %d\n", i);
}
// 刪除測試
//
i = 4;// 取值 1, 2, 3, 4，分別對應 case 1, 2, 3, 4
switch (i)
{
case 1: // 兄弟為紅色
test_redblacktree_delete(&tree, 3);
break;
case 2: // 兄弟為黑色，且兄弟的兩孩子均為黑色
test_redblacktree_delete(&tree, 12);
break;
case 3: // 兄弟為黑色，且兄弟的左孩子為紅色，右孩子均為黑色
test_redblacktree_delete(&tree, 19);
break;
case 4: // 兄弟為黑色，且兄弟的右孩子為紅色
test_redblacktree_delete(&tree, 9);
break;
}
test_redblacktree_delete(&tree, 21);
// 刪除樹
for (i = 0; i < length; i++) {
node = RBTree_search(tree, array[i]);
if (node != RBTree_nil()) {
printf("刪除 %d\n", node->key);
node = RBTree_delete(&tree, node);
free(node);
}
}
assert(tree == RBTree_nil());
}
測試結果
===============================================
創建紅黑樹
-------------------------------
第 1 層， 6(B)
第 2 層， 3(B)
第 3 層， 2(B)
第 3 層， 4(B)
第 2 層， 12(B)
第 3 層， 9(R)
第 4 層， 7(B)
第 4 層， 11(B)
第 3 層， 18(R)
第 4 層， 14(B)
第 5 層， 17(R)
第 4 層， 20(B)
第 5 層， 19(R)
第 5 層， 22(R)
插入節點 21
-------------------------------
第 1 層， 6(B)
第 2 層， 3(B)
第 3 層， 2(B)
第 3 層， 4(B)
第 2 層， 12(R)
第 3 層， 9(B)
第 4 層， 7(B)
第 4 層， 11(B)
第 3 層， 18(B)
第 4 層， 14(B)
第 5 層， 17(R)
第 4 層， 20(R)
第 5 層， 19(B)
第 5 層， 22(B)
第 6 層， 21(R)
在紅黑樹中找到節點 6
-------------------------------
刪除節點 9
-------------------------------
第 1 層， 6(B)
第 2 層， 3(B)
第 3 層， 2(B)
第 3 層， 4(B)
第 2 層， 18(R)
第 3 層， 12(B)
第 4 層， 11(B)
第 5 層， 7(R)
第 4 層， 14(B)
第 5 層， 17(R)
第 3 層， 20(B)
第 4 層， 19(B)
第 4 層， 22(B)
第 5 層， 21(R)
刪除節點 21
-------------------------------
第 1 層， 6(B)
第 2 層， 3(B)
第 3 層， 2(B)
第 3 層， 4(B)
第 2 層， 18(R)
第 3 層， 12(B)
第 4 層， 11(B)
第 5 層， 7(R)
第 4 層， 14(B)
第 5 層， 17(R)
第 3 層， 20(B)
第 4 層， 19(B)
第 4 層， 22(B)
刪除 2
刪除 3
刪除 4
刪除 6
刪除 7
刪除 11
刪除 18
刪除 12
刪除 14
刪除 19
刪除 17
刪除 22
刪除 20
測試結束