C語言實現(xiàn)手寫紅黑樹的示例代碼
更新時間：2022年09月02日 11:39:24 作者：胡安民-獨行者
紅黑樹在表意上就是一棵每個節(jié)點帶有顏色的二叉搜索樹，并通過對節(jié)點顏色的控制，使該二叉搜索樹達(dá)到盡量平衡的狀態(tài)。本文主將用C語言實現(xiàn)手寫紅黑樹，需要的可以參考一下
前沿
寫C的紅黑樹前建議先看我博客這篇文章Java-紅黑樹 主要看原理
紅黑樹代碼
#ifndef STUDY_RBTREE_H
#define STUDY_RBTREE_H
#include "charkvlinked.h"
typedef int boolean;//定義一個布爾類型
#define TRUE 1
#define FALSE 0
enum COL{RED=0,BLACK=1};
typedef struct rBNode
{
char *key; //元素key
void *value; //元素值
int color; //節(jié)點顏色
struct rBNode *left; //左孩子
struct rBNode *right; //右孩子
struct rBNode *parent; //父結(jié)點
}RBNode;
typedef struct rBTree{
RBNode *root; //根結(jié)點
int size; //結(jié)點數(shù)量
} RBTree;
#define isRed(rBNode) ((rBNode != NULL) && (rBNode->color == RED)) ? TRUE : FALSE
#define isBlack(rBNode) ((rBNode != NULL) && (rBNode->color == BLACK)) ? TRUE : FALSE
#define colorOf(rBNode) rBNode != NULL ? rBNode->color : BLACK
#define parentOf(rBNode) rBNode != NULL ? rBNode->parent : NULL
#define setBlack(rBNode) rBNode != NULL ? rBNode->color = BLACK : NULL
#define setRed(rBNode) rBNode != NULL ? rBNode->color = RED : NULL
#define setParent(rBNode,replace) rBNode != NULL ? rBNode->parent = replace : NULL
#define setColor(rBNode,parent) rBNode != NULL ? rBNode->color = colorOf(parent) : NULL
CharKvLinked * getAllKeyAndValueRbTree(RBTree * tree);
RBTree *createRBTree();
RBNode *createRbTreeNode(char *key, void *value);
void insertOrUpdateRBTreeKey(RBTree *tree, RBNode *node);
void insertRBTreeKeyRepetition(RBTree *tree, RBNode *node);
boolean isExistRbTree(RBTree *pTree, char *key);
RBNode *searchRbTree(RBTree *pTree, char *key);
RBNode *iterativeSearchRbTree(RBTree *pTree, char *key);
void removeRbTree(RBTree *tree, char *key);
void destroyRbTree(RBTree *tree) ;
#endif //STUDY_RBTREE_H#include "rbtree.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*
* 打印"紅黑樹"
*
* key -- 節(jié)點的鍵值
* direction -- 0，表示該節(jié)點是根節(jié)點;
* -1，表示該節(jié)點是它的父結(jié)點的左孩子;
* 1，表示該節(jié)點是它的父結(jié)點的右孩子。
*/
static void printRbTree_(RBNode *node, char *data, int direction) {
if (node != NULL) {
int i = isRed(node);
if (direction == 0) // tree是根節(jié)點
{
printf("%s (%s) is root 他的左節(jié)點: %s,他的右節(jié)點:%s ,他的內(nèi)存地址是:%p\n", node->key, i ? "紅" : "黑",
node->left == NULL ? "NULL" : node->left->key,
node->right == NULL ? "NULL" : node->right->key, node);
} else // tree是分支節(jié)點
{
printf("%s (%s) 是 %s' 的 %s 子節(jié)點,他的左節(jié)點:%s ,他的右節(jié)點:%s ,他的內(nèi)存地址是:%p\n",
node->key, i ? "紅" : "黑", data,
direction == 1 ? "right" : "left",
node->left == NULL ? "NULL" : node->left->key,
node->right == NULL ? "NULL" : node->right->key, node);
}
printRbTree_(node->left, node->key, -1);
printRbTree_(node->right, node->key, 1);
}
}
void printRbTreeNode(RBTree *root) {
if (root->root != NULL) {
printRbTree_(root->root, root->root->key, 0);
}
}
/*
* 對紅黑樹的節(jié)點(x)進(jìn)行左旋轉(zhuǎn)
*
* 左旋示意圖(對節(jié)點x進(jìn)行左旋)：
* px px
* / /
* x y
* / \ --(左旋)-. / \
* lx y x ry
* / \ / \
* ly ry lx ly
*
* px px
* \ \
* x y
* / \ --(左旋)-. / \
* lx y x ry
* / \ / \
* ly ry lx ly
*
* 沒有父節(jié)點的情況,也就表示x是根節(jié)點的情況
* x y
* / \ --(左旋)-. / \
* lx y x ry
* / \ / \
* ly ry lx ly
*
* x y
* \ / \
* y x ry
* \
* ry
*
*
*
*/
static void leftRotateRbTree(RBTree *tree, RBNode *x) {
if (x != NULL) {
//1.獲取x的右孩子，即y
RBNode *y = x->right;
//2.將y的左孩子設(shè)置為x的右孩子
x->right = y->left;
// 左子樹不為空，需要更新父節(jié)點
if (y->left != NULL) {
y->left->parent = x;
}
// 3. 空出節(jié)點x的父節(jié)點
y->parent = x->parent;
//4.父節(jié)點指向右兒子
if (x->parent == NULL) { // 右兒子成為新的根節(jié)點
tree->root = y;
} else if (x == x->parent->left) { // 右兒子成為父節(jié)點的左兒子
x->parent->left = y;
} else { // 右兒子成為父節(jié)點的右兒子
x->parent->right = y;
}
//5. 節(jié)點x成為y的左子樹
y->left = x;
x->parent = y;
}
}
/*
* 對紅黑樹的節(jié)點(y)進(jìn)行右旋轉(zhuǎn)
*
* 右旋示意圖(對節(jié)點y進(jìn)行右旋)：
* py py
* / /
* y x
* / \ --(右旋)-. / \
* x ry lx y
* / \ / \
* lx rx rx ry
*
* py py
* \ \
* y x
* / \ --(右旋)-. / \
* x ry lx y
* / \ / \
* lx rx rx ry
*
* y x
* / \ --(右旋)-. / \
* x ry lx y
* / \ / \
* lx rx rx ry
*
*
*
*
*/
static void rightRotateRbTree(RBTree *tree, RBNode *y) {
if (y != NULL) {
// 記錄p的左兒子
RBNode *x = y->left;
// 1. 空出左兒子的右子樹
y->left = x->right;
// 右子樹不為空，需要更新父節(jié)點
if (x->right != NULL) {
x->right->parent = y;
}
// 2. 空出節(jié)點p的父節(jié)點
x->parent = y->parent;
// 父節(jié)點指向左兒子
if (y->parent == NULL) { // 左兒子成為整棵樹根節(jié)點
tree->root = x;
} else if (y->parent->left == y) { // 左兒子成為父節(jié)點左兒子
y->parent->left = x;
} else { // 左兒子成為父節(jié)點的右兒子
y->parent->right = x;
}
// 3. 順利會師
x->right = y;
y->parent = x;
}
}
//創(chuàng)建紅黑樹
RBTree *createRBTree() {
RBTree *tree = (RBTree *) malloc(sizeof(RBTree));
tree->root = NULL;
tree->size = 0;
return tree;
}
//創(chuàng)建節(jié)點
RBNode *createRbTreeNode(char *key, void *value) {
RBNode *node = (RBNode *) malloc(sizeof(RBNode));
node->key = key;
node->value = value;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
node->color = RED;
return node;
}
static void insertRbTreeFixUp(RBTree *tree, RBNode *node) {
RBNode *parent, *gparent;
// 若“父節(jié)點存在，并且父節(jié)點的顏色是紅色”
while (((parent = parentOf(node)) != NULL) && isRed(parent)) {
gparent = parentOf(parent);
//若“父節(jié)點”是“祖父節(jié)點的左孩子”
if (parent == gparent->left) {
// Case 1條件：叔叔節(jié)點是紅色
RBNode *uncle = gparent->right;
if (isRed(uncle)) {
setBlack(uncle);//父節(jié)點
setBlack(parent);//叔節(jié)點
setRed(gparent);//租節(jié)點
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色，且當(dāng)前節(jié)點是右孩子
if (parent->right == node) {
RBNode *tmp;
leftRotateRbTree(tree, parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點是左孩子。
setBlack(parent);
setRed(gparent);
rightRotateRbTree(tree, gparent);
} else { //若當(dāng)前節(jié)點的父節(jié)點是當(dāng)前節(jié)點的祖父節(jié)點的右孩子
// Case 1條件：叔叔節(jié)點是紅色
RBNode *uncle = gparent->left;
if (isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色，且當(dāng)前節(jié)點是左孩子
if (parent->left == node) {
RBNode *tmp;
rightRotateRbTree(tree, parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點是右孩子。
setBlack(parent);
setRed(gparent);
leftRotateRbTree(tree, gparent);
}
}
// 將根節(jié)點設(shè)為黑色
setBlack(tree->root);
}
static void insertRBTree(RBTree *tree, RBNode *node, int type) {
int cmp;
RBNode *y = NULL;
RBNode *x = tree->root;
// 1. 將紅黑樹當(dāng)作一顆二叉查找樹，將節(jié)點添加到二叉查找樹中。
while (x != NULL) {
y = x;//拿到為NULL的上一個節(jié)點
cmp = strcmp(node->key, x->key);
if (cmp < 0) {
x = x->left;
} else {
x = x->right;
}
}
node->parent = y;
if (y != NULL) {
cmp = strcmp(node->key, y->key);
if (cmp < 0) {
y->left = node;
} else if (cmp > 0) {
y->right = node;
} else {
if (type == 1) {
// 如果key相等，則更新value
y->value = node->value;
} else {
//支持重復(fù)插入
y->right = node;
}
}
} else {
tree->root = node;
}
// 2. 設(shè)置節(jié)點的顏色為紅色
node->color = RED;
// 3. 將它重新修正為一顆二叉查找樹
insertRbTreeFixUp(tree, node);
tree->size++;
}
//插入節(jié)點不允許重復(fù)插入,如果重復(fù)插入，則更新value
void insertOrUpdateRBTreeKey(RBTree *tree, RBNode *node) {
insertRBTree(tree, node, 1);
}
//插入節(jié)點允許重復(fù)插入
void insertRBTreeKeyRepetition(RBTree *tree, RBNode *node) {
insertRBTree(tree, node, 0);
}
/*
* (遞歸實現(xiàn))查找"紅黑樹x"中鍵值為key的節(jié)點
*/
static RBNode *searchRbTree_(RBNode *x, char *key) {
if (x == NULL) {
return x;
}
int cmp = strcmp(key, x->key);
if (cmp < 0) {
return searchRbTree_(x->left, key);
} else if (cmp > 0) {
return searchRbTree_(x->right, key);
} else {
return x;
}
}
RBNode *searchRbTree(RBTree *pTree, char *key) {
return searchRbTree_(pTree->root, key);
}
//判斷節(jié)點是否存在
boolean isExistRbTree(RBTree *pTree, char *key) {
RBNode *node = searchRbTree(pTree, key);
if (node == NULL) {
return FALSE;
} else {
return TRUE;
}
}
/*
* (非遞歸實現(xiàn))查找"紅黑樹x"中鍵值為key的節(jié)點
*/
RBNode *iterativeSearchRbTree_(RBNode *x, char *key) {
while (x != NULL) {
int cmp = strcmp(key, x->key);
if (cmp < 0) {
x = x->left;
} else if (cmp > 0) {
x = x->right;
} else {
return x;
}
}
return x;
}
RBNode *iterativeSearchRbTree(RBTree *pTree, char *key) {
return iterativeSearchRbTree_(pTree->root, key);
}
//獲取所有的key和value
void getAllKeyAndValueRbTree_(CharKvLinked *pLinked, RBNode *node) {
if (node != NULL) {
insertCharKvLinkedHeadNode(pLinked, createCharKvLinkedNode(node->key, node->value));
getAllKeyAndValueRbTree_(pLinked, node->left);
getAllKeyAndValueRbTree_(pLinked, node->right);
}
}
//獲取所有的key和value
CharKvLinked *getAllKeyAndValueRbTree(RBTree *tree) {
CharKvLinked *pLinked = createCharKvLinked();
getAllKeyAndValueRbTree_(pLinked, tree->root);
return pLinked;
}
/*
* 紅黑樹刪除修正函數(shù)
*
* 在從紅黑樹中刪除插入節(jié)點之后(紅黑樹失去平衡)，再調(diào)用該函數(shù)；
* 目的是將它重新塑造成一顆紅黑樹。
*
* 參數(shù)說明：
* node 待修正的節(jié)點
*/
static void removeRbTreeFixUp(RBTree *tree, RBNode *node, RBNode *parent) {
RBNode *other;
while ((node == NULL || isBlack(node)) && (node != tree->root)) {
if (parent->left == node) {
other = parent->right;
if (isRed(other)) {
// Case 1: x的兄弟w是紅色的
setBlack(other);
setRed(parent);
leftRotateRbTree(tree, parent);
other = parent->right;
}
if ((other->left == NULL || isBlack(other->left)) &&
(other->right == NULL || isBlack(other->right))) {
// Case 2: x的兄弟w是黑色，且w的倆個孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other->right == NULL || isBlack(other->right)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是紅色，右孩子為黑色。
setBlack(other->left);
setRed(other);
rightRotateRbTree(tree, other);
other = parent->right;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是紅色的，左孩子任意顏色。
setColor(other, parent);
setBlack(parent);
setBlack(other->right);
leftRotateRbTree(tree, parent);
node = tree->root;
break;
}
} else {
other = parent->left;
if (isRed(other)) {
// Case 1: x的兄弟w是紅色的
setBlack(other);
setRed(parent);
rightRotateRbTree(tree, parent);
other = parent->left;
}
if ((other->left == NULL || isBlack(other->left)) &&
(other->right == NULL || isBlack(other->right))) {
// Case 2: x的兄弟w是黑色，且w的倆個孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other->left == NULL || isBlack(other->left)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是紅色，右孩子為黑色。
setBlack(other->right);
setRed(other);
leftRotateRbTree(tree, other);
other = parent->left;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是紅色的，左孩子任意顏色。
setColor(other, parent);
setBlack(parent);
setBlack(other->left);
rightRotateRbTree(tree, parent);
node = tree->root;
break;
}
}
}
if (node != NULL) {
setBlack(node);
}
}
static void removeRbTree_(RBTree *tree, RBNode *node) {
RBNode *child, *parent;
boolean color;
// 被刪除節(jié)點的"左右孩子都不為空"的情況。
if ((node->left != NULL) && (node->right != NULL)) {
// 被刪節(jié)點的后繼節(jié)點。(稱為"取代節(jié)點")
// 用它來取代"被刪節(jié)點"的位置，然后再將"被刪節(jié)點"去掉。
RBNode *replace = node;
// 獲取后繼節(jié)點
replace = replace->right;
while (replace->left != NULL) {
replace = replace->left;
}
// "node節(jié)點"不是根節(jié)點(只有根節(jié)點不存在父節(jié)點)
if (parentOf(node) != NULL) {
if (parentOf(node) == node) {
(parentOf(node))->left = replace;
} else {
(parentOf(node))->right = replace;
}
} else {
// "node節(jié)點"是根節(jié)點，更新根節(jié)點。
tree->root = replace;
}
// child是"取代節(jié)點"的右孩子，也是需要"調(diào)整的節(jié)點"。
// "取代節(jié)點"肯定不存在左孩子！因為它是一個后繼節(jié)點。
child = replace->right;
parent = parentOf(replace);
// 保存"取代節(jié)點"的顏色
color = colorOf(replace);
// "被刪除節(jié)點"是"它的后繼節(jié)點的父節(jié)點"
if (parent == node) {
parent = replace;
} else {
// child不為空
if (child != NULL) {
setParent(child, parent);
}
parent->left = child;
replace->right = node->right;
setParent(node->right, replace);
}
replace->parent = node->parent;
replace->color = node->color;
replace->left = node->left;
node->left->parent = replace;
if (color == BLACK) {
removeRbTreeFixUp(tree, child, parent);
}
node = NULL;
return;
}
if (node->left != NULL) {
child = node->left;
} else {
child = node->right;
}
parent = node->parent;
// 保存"取代節(jié)點"的顏色
color = node->color;
if (child != NULL) {
child->parent = parent;
}
// "node節(jié)點"不是根節(jié)點
if (parent != NULL) {
if (parent->left == node) {
parent->left = child;
} else {
parent->right = child;
}
} else {
tree->root = child;
}
if (color == BLACK) {
removeRbTreeFixUp(tree, child, parent);
}
node = NULL;
}
/*
* 刪除結(jié)點(z)，并返回被刪除的結(jié)點
*
* 參數(shù)說明：
* tree 紅黑樹的根結(jié)點
* z 刪除的結(jié)點
*/
void removeRbTree(RBTree *tree, char *key) {
RBNode *node;
if ((node = searchRbTree(tree, key)) != NULL) {
removeRbTree_(tree, node);
tree->size--;
}
}
/*
* 銷毀紅黑樹
*/
static void destroyRbTree_(RBNode *tree) {
if (tree == NULL) {
return;
}
if (tree->left != NULL) {
destroyRbTree_(tree->left);
}
if (tree->right != NULL) {
destroyRbTree_(tree->right);
}
free(tree);
}
void destroyRbTree(RBTree *tree) {
destroyRbTree_(tree->root);
free(tree);
}
//樹結(jié)構(gòu)不建議使用迭代,我們可以使用前序,中序,后續(xù)遍歷來實現(xiàn) 需要自己寫代碼
//前序遍歷
//void preOrder(RBNode *tree) {
// if (tree != NULL) {
// printf("%s ", tree->key);
// preOrder(tree->left);
// preOrder(tree->right);
// }
//}
測試
int main() {
RBTree *pTree = createRBTree();
for (int i = 0; i < 10; i++) {
char *str = (char *) malloc(sizeof(char) * 10);
sprintf(str, "%d", i);
insertOrUpdateRBTreeKey(pTree, createRbTreeNode(str, str));
}
printRbTreeNode(pTree);
destroyRbTree(pTree);
}
以上就是C語言實現(xiàn)手寫紅黑樹的示例代碼的詳細(xì)內(nèi)容，更多關(guān)于C語言紅黑樹的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++學(xué)習(xí)之Lambda表達(dá)式的用法詳解
Lambda?表達(dá)式（lambda?expression）是一個匿名函數(shù)，Lambda表達(dá)式基于數(shù)學(xué)中的λ演算得名。本文就來為大家詳細(xì)講講C++中Lambda表達(dá)式的使用，需要的可以參考一下2022-07-07
VC實現(xiàn)讓關(guān)閉按鈕成灰色不可用的方法
這篇文章主要介紹了VC實現(xiàn)讓關(guān)閉按鈕成灰色不可用的方法,比較實用的一個特殊功能,需要的朋友可以參考下2014-08-08
這篇文章主要以圖文結(jié)合的方式為大家詳細(xì)介紹了C語言位運算基礎(chǔ)知識，感興趣的小伙伴們可以參考一下,希望能給你帶來幫助2021-10-10
C語言素數(shù)(質(zhì)數(shù))判斷的3種方法舉例
這篇文章主要給大家介紹了關(guān)于C語言素數(shù)(質(zhì)數(shù))判斷的3種方法,質(zhì)數(shù)是只能被1或者自身整除的自然數(shù)(不包括1),稱為質(zhì)數(shù),文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-11-11
C++圖形界面開發(fā)Qt教程:嵌套圓環(huán)示例
這篇文章主要介紹了C++實現(xiàn)圖形界面開發(fā)Qt教程,涉及坐標(biāo)函數(shù)的應(yīng)用及圖形界面程序設(shè)計,需要的朋友可以參考下,希望能給你帶來幫助2021-08-08
GStreamer 是用來構(gòu)建流媒體應(yīng)用的開源多媒體框架(framework)，其目標(biāo)是要簡化音/視頻應(yīng)用程序的開發(fā)，已經(jīng)能夠被用來處理像 MP3、Ogg、MPEG1、MPEG2、AVI、Quicktime 等多種格式的多媒體數(shù)據(jù)2022-07-07
這篇文章主要給大家介紹了關(guān)于C++中多態(tài)的定義及實現(xiàn)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05
C++中std::stringstream多類型數(shù)據(jù)拼接和提取用法小結(jié)
本文主要介紹了C++中std::stringstream多類型數(shù)據(jù)拼接和提取用法小結(jié),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-09-09
用C實現(xiàn)PHP擴(kuò)展 Image_Tool 圖片常用處理工具類的使用
該擴(kuò)展是基于ImageMagick基礎(chǔ)實現(xiàn)的，圖片操作調(diào)用的是ImageMagick API2013-04-04
在本篇文章當(dāng)中主要給大家介紹C語言當(dāng)中一些不常用的特性，比如在main函數(shù)之前和之后設(shè)置我們想要執(zhí)行的函數(shù)，以及各種花式退出程序的方式，需要的可以參考一下2022-10-10