溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
本篇內(nèi)容介紹了“怎么用C語(yǔ)言實(shí)現(xiàn)手寫(xiě)紅黑樹(shù)”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！
#ifndef STUDY_RBTREE_H
#define STUDY_RBTREE_H
#include "charkvlinked.h"
typedef int boolean;//定義一個(gè)布爾類型
#define TRUE 1
#define FALSE 0
enum COL{RED=0,BLACK=1};
typedef struct rBNode
{
char *key; //元素key
void *value; //元素值
int color; //節(jié)點(diǎn)顏色
struct rBNode *left; //左孩子
struct rBNode *right; //右孩子
struct rBNode *parent; //父結(jié)點(diǎn)
}RBNode;
typedef struct rBTree{
RBNode *root; //根結(jié)點(diǎn)
int size; //結(jié)點(diǎn)數(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>
/*
* 打印"紅黑樹(shù)"
*
* key -- 節(jié)點(diǎn)的鍵值
* direction -- 0，表示該節(jié)點(diǎn)是根節(jié)點(diǎn);
* -1，表示該節(jié)點(diǎn)是它的父結(jié)點(diǎn)的左孩子;
* 1，表示該節(jié)點(diǎn)是它的父結(jié)點(diǎn)的右孩子。
*/
static void printRbTree_(RBNode *node, char *data, int direction) {
if (node != NULL) {
int i = isRed(node);
if (direction == 0) // tree是根節(jié)點(diǎn)
{
printf("%s (%s) is root 他的左節(jié)點(diǎn): %s,他的右節(jié)點(diǎn):%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é)點(diǎn)
{
printf("%s (%s) 是 %s' 的 %s 子節(jié)點(diǎn),他的左節(jié)點(diǎn):%s ,他的右節(jié)點(diǎn):%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);
}
}
/*
* 對(duì)紅黑樹(shù)的節(jié)點(diǎn)(x)進(jìn)行左旋轉(zhuǎn)
*
* 左旋示意圖(對(duì)節(jié)點(diǎn)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
*
* 沒(méi)有父節(jié)點(diǎn)的情況,也就表示x是根節(jié)點(diǎn)的情況
* 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;
// 左子樹(shù)不為空，需要更新父節(jié)點(diǎn)
if (y->left != NULL) {
y->left->parent = x;
}
// 3. 空出節(jié)點(diǎn)x的父節(jié)點(diǎn)
y->parent = x->parent;
//4.父節(jié)點(diǎn)指向右兒子
if (x->parent == NULL) { // 右兒子成為新的根節(jié)點(diǎn)
tree->root = y;
} else if (x == x->parent->left) { // 右兒子成為父節(jié)點(diǎn)的左兒子
x->parent->left = y;
} else { // 右兒子成為父節(jié)點(diǎn)的右兒子
x->parent->right = y;
}
//5. 節(jié)點(diǎn)x成為y的左子樹(shù)
y->left = x;
x->parent = y;
}
}
/*
* 對(duì)紅黑樹(shù)的節(jié)點(diǎn)(y)進(jìn)行右旋轉(zhuǎn)
*
* 右旋示意圖(對(duì)節(jié)點(diǎn)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. 空出左兒子的右子樹(shù)
y->left = x->right;
// 右子樹(shù)不為空，需要更新父節(jié)點(diǎn)
if (x->right != NULL) {
x->right->parent = y;
}
// 2. 空出節(jié)點(diǎn)p的父節(jié)點(diǎn)
x->parent = y->parent;
// 父節(jié)點(diǎn)指向左兒子
if (y->parent == NULL) { // 左兒子成為整棵樹(shù)根節(jié)點(diǎn)
tree->root = x;
} else if (y->parent->left == y) { // 左兒子成為父節(jié)點(diǎn)左兒子
y->parent->left = x;
} else { // 左兒子成為父節(jié)點(diǎn)的右兒子
y->parent->right = x;
}
// 3. 順利會(huì)師
x->right = y;
y->parent = x;
}
}
//創(chuàng)建紅黑樹(shù)
RBTree *createRBTree() {
RBTree *tree = (RBTree *) malloc(sizeof(RBTree));
tree->root = NULL;
tree->size = 0;
return tree;
}
//創(chuàng)建節(jié)點(diǎn)
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é)點(diǎn)存在，并且父節(jié)點(diǎn)的顏色是紅色”
while (((parent = parentOf(node)) != NULL) && isRed(parent)) {
gparent = parentOf(parent);
//若“父節(jié)點(diǎn)”是“祖父節(jié)點(diǎn)的左孩子”
if (parent == gparent->left) {
// Case 1條件：叔叔節(jié)點(diǎn)是紅色
RBNode *uncle = gparent->right;
if (isRed(uncle)) {
setBlack(uncle);//父節(jié)點(diǎn)
setBlack(parent);//叔節(jié)點(diǎn)
setRed(gparent);//租節(jié)點(diǎn)
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是右孩子
if (parent->right == node) {
RBNode *tmp;
leftRotateRbTree(tree, parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是左孩子。
setBlack(parent);
setRed(gparent);
rightRotateRbTree(tree, gparent);
} else { //若當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)的右孩子
// Case 1條件：叔叔節(jié)點(diǎn)是紅色
RBNode *uncle = gparent->left;
if (isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是左孩子
if (parent->left == node) {
RBNode *tmp;
rightRotateRbTree(tree, parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是右孩子。
setBlack(parent);
setRed(gparent);
leftRotateRbTree(tree, gparent);
}
}
// 將根節(jié)點(diǎn)設(shè)為黑色
setBlack(tree->root);
}
static void insertRBTree(RBTree *tree, RBNode *node, int type) {
int cmp;
RBNode *y = NULL;
RBNode *x = tree->root;
// 1. 將紅黑樹(shù)當(dāng)作一顆二叉查找樹(shù)，將節(jié)點(diǎn)添加到二叉查找樹(shù)中。
while (x != NULL) {
y = x;//拿到為NULL的上一個(gè)節(jié)點(diǎn)
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é)點(diǎn)的顏色為紅色
node->color = RED;
// 3. 將它重新修正為一顆二叉查找樹(shù)
insertRbTreeFixUp(tree, node);
tree->size++;
}
//插入節(jié)點(diǎn)不允許重復(fù)插入,如果重復(fù)插入，則更新value
void insertOrUpdateRBTreeKey(RBTree *tree, RBNode *node) {
insertRBTree(tree, node, 1);
}
//插入節(jié)點(diǎn)允許重復(fù)插入
void insertRBTreeKeyRepetition(RBTree *tree, RBNode *node) {
insertRBTree(tree, node, 0);
}
/*
* (遞歸實(shí)現(xiàn))查找"紅黑樹(shù)x"中鍵值為key的節(jié)點(diǎn)
*/
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é)點(diǎn)是否存在
boolean isExistRbTree(RBTree *pTree, char *key) {
RBNode *node = searchRbTree(pTree, key);
if (node == NULL) {
return FALSE;
} else {
return TRUE;
}
}
/*
* (非遞歸實(shí)現(xiàn))查找"紅黑樹(shù)x"中鍵值為key的節(jié)點(diǎn)
*/
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ù)刪除修正函數(shù)
*
* 在從紅黑樹(shù)中刪除插入節(jié)點(diǎn)之后(紅黑樹(shù)失去平衡)，再調(diào)用該函數(shù)；
* 目的是將它重新塑造成一顆紅黑樹(shù)。
*
* 參數(shù)說(shuō)明：
* node 待修正的節(jié)點(diǎn)
*/
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的倆個(gè)孩子也都是黑色的
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的倆個(gè)孩子也都是黑色的
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é)點(diǎn)的"左右孩子都不為空"的情況。
if ((node->left != NULL) && (node->right != NULL)) {
// 被刪節(jié)點(diǎn)的后繼節(jié)點(diǎn)。(稱為"取代節(jié)點(diǎn)")
// 用它來(lái)取代"被刪節(jié)點(diǎn)"的位置，然后再將"被刪節(jié)點(diǎn)"去掉。
RBNode *replace = node;
// 獲取后繼節(jié)點(diǎn)
replace = replace->right;
while (replace->left != NULL) {
replace = replace->left;
}
// "node節(jié)點(diǎn)"不是根節(jié)點(diǎn)(只有根節(jié)點(diǎn)不存在父節(jié)點(diǎn))
if (parentOf(node) != NULL) {
if (parentOf(node) == node) {
(parentOf(node))->left = replace;
} else {
(parentOf(node))->right = replace;
}
} else {
// "node節(jié)點(diǎn)"是根節(jié)點(diǎn)，更新根節(jié)點(diǎn)。
tree->root = replace;
}
// child是"取代節(jié)點(diǎn)"的右孩子，也是需要"調(diào)整的節(jié)點(diǎn)"。
// "取代節(jié)點(diǎn)"肯定不存在左孩子！因?yàn)樗且粋€(gè)后繼節(jié)點(diǎn)。
child = replace->right;
parent = parentOf(replace);
// 保存"取代節(jié)點(diǎn)"的顏色
color = colorOf(replace);
// "被刪除節(jié)點(diǎn)"是"它的后繼節(jié)點(diǎn)的父節(jié)點(diǎn)"
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é)點(diǎn)"的顏色
color = node->color;
if (child != NULL) {
child->parent = parent;
}
// "node節(jié)點(diǎn)"不是根節(jié)點(diǎn)
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é)點(diǎn)(z)，并返回被刪除的結(jié)點(diǎn)
*
* 參數(shù)說(shuō)明：
* tree 紅黑樹(shù)的根結(jié)點(diǎn)
* z 刪除的結(jié)點(diǎn)
*/
void removeRbTree(RBTree *tree, char *key) {
RBNode *node;
if ((node = searchRbTree(tree, key)) != NULL) {
removeRbTree_(tree, node);
tree->size--;
}
}
/*
* 銷毀紅黑樹(shù)
*/
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);
}
//樹(shù)結(jié)構(gòu)不建議使用迭代,我們可以使用前序,中序,后續(xù)遍歷來(lái)實(shí)現(xiàn) 需要自己寫(xiě)代碼
//前序遍歷
//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語(yǔ)言實(shí)現(xiàn)手寫(xiě)紅黑樹(shù)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼