<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
C語言實現手寫紅黑樹的範例程式碼
2022-09-02 18:02:19
前沿
寫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; //節點顏色
struct rBNode *left; //左孩子
struct rBNode *right; //右孩子
struct rBNode *parent; //父結點
}RBNode;
typedef struct rBTree{
RBNode *root; //根結點
int size; //結點數量
} 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 -- 節點的鍵值
* direction -- 0，表示該節點是根節點;
* -1，表示該節點是它的父結點的左孩子;
* 1，表示該節點是它的父結點的右孩子。
*/
static void printRbTree_(RBNode *node, char *data, int direction) {
if (node != NULL) {
int i = isRed(node);
if (direction == 0) // tree是根節點
{
printf("%s (%s) is root 他的左節點: %s,他的右節點:%s ,他的記憶體地址是:%pn", node->key, i ? "紅" : "黑",
node->left == NULL ? "NULL" : node->left->key,
node->right == NULL ? "NULL" : node->right->key, node);
} else // tree是分支節點
{
printf("%s (%s) 是 %s' 的 %s 子節點,他的左節點:%s ,他的右節點:%s ,他的記憶體地址是:%pn",
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);
}
}
/*
* 對紅黑樹的節點(x)進行左旋轉
*
* 左旋示意圖(對節點x進行左旋)：
* px px
* / /
* x y
* / --(左旋)-. /
* lx y x ry
* / /
* ly ry lx ly
*
* px px
*
* x y
* / --(左旋)-. /
* lx y x ry
* / /
* ly ry lx ly
*
* 沒有父節點的情況,也就表示x是根節點的情況
* 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的左孩子設定為x的右孩子
x->right = y->left;
// 左子樹不為空，需要更新父節點
if (y->left != NULL) {
y->left->parent = x;
}
// 3. 空出節點x的父節點
y->parent = x->parent;
//4.父節點指向右兒子
if (x->parent == NULL) { // 右兒子成為新的根節點
tree->root = y;
} else if (x == x->parent->left) { // 右兒子成為父節點的左兒子
x->parent->left = y;
} else { // 右兒子成為父節點的右兒子
x->parent->right = y;
}
//5. 節點x成為y的左子樹
y->left = x;
x->parent = y;
}
}
/*
* 對紅黑樹的節點(y)進行右旋轉
*
* 右旋示意圖(對節點y進行右旋)：
* 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;
// 右子樹不為空，需要更新父節點
if (x->right != NULL) {
x->right->parent = y;
}
// 2. 空出節點p的父節點
x->parent = y->parent;
// 父節點指向左兒子
if (y->parent == NULL) { // 左兒子成為整棵樹根節點
tree->root = x;
} else if (y->parent->left == y) { // 左兒子成為父節點左兒子
y->parent->left = x;
} else { // 左兒子成為父節點的右兒子
y->parent->right = x;
}
// 3. 順利會師
x->right = y;
y->parent = x;
}
}
//建立紅黑樹
RBTree *createRBTree() {
RBTree *tree = (RBTree *) malloc(sizeof(RBTree));
tree->root = NULL;
tree->size = 0;
return tree;
}
//建立節點
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;
// 若「父節點存在，並且父節點的顏色是紅色」
while (((parent = parentOf(node)) != NULL) && isRed(parent)) {
gparent = parentOf(parent);
//若「父節點」是「祖父節點的左孩子」
if (parent == gparent->left) {
// Case 1條件：叔叔節點是紅色
RBNode *uncle = gparent->right;
if (isRed(uncle)) {
setBlack(uncle);//父節點
setBlack(parent);//叔節點
setRed(gparent);//租節點
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色，且當前節點是右孩子
if (parent->right == node) {
RBNode *tmp;
leftRotateRbTree(tree, parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當前節點是左孩子。
setBlack(parent);
setRed(gparent);
rightRotateRbTree(tree, gparent);
} else { //若當前節點的父節點是當前節點的祖父節點的右孩子
// Case 1條件：叔叔節點是紅色
RBNode *uncle = gparent->left;
if (isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色，且當前節點是左孩子
if (parent->left == node) {
RBNode *tmp;
rightRotateRbTree(tree, parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當前節點是右孩子。
setBlack(parent);
setRed(gparent);
leftRotateRbTree(tree, gparent);
}
}
// 將根節點設為黑色
setBlack(tree->root);
}
static void insertRBTree(RBTree *tree, RBNode *node, int type) {
int cmp;
RBNode *y = NULL;
RBNode *x = tree->root;
// 1. 將紅黑樹當作一顆二叉查詢樹，將節點新增到二叉查詢樹中。
while (x != NULL) {
y = x;//拿到為NULL的上一個節點
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 {
//支援重複插入
y->right = node;
}
}
} else {
tree->root = node;
}
// 2. 設定節點的顏色為紅色
node->color = RED;
// 3. 將它重新修正為一顆二叉查詢樹
insertRbTreeFixUp(tree, node);
tree->size++;
}
//插入節點不允許重複插入,如果重複插入，則更新value
void insertOrUpdateRBTreeKey(RBTree *tree, RBNode *node) {
insertRBTree(tree, node, 1);
}
//插入節點允許重複插入
void insertRBTreeKeyRepetition(RBTree *tree, RBNode *node) {
insertRBTree(tree, node, 0);
}
/*
* (遞迴實現)查詢"紅黑樹x"中鍵值為key的節點
*/
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);
}
//判斷節點是否存在
boolean isExistRbTree(RBTree *pTree, char *key) {
RBNode *node = searchRbTree(pTree, key);
if (node == NULL) {
return FALSE;
} else {
return TRUE;
}
}
/*
* (非遞迴實現)查詢"紅黑樹x"中鍵值為key的節點
*/
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;
}
/*
* 紅黑樹刪除修正函數
*
* 在從紅黑樹中刪除插入節點之後(紅黑樹失去平衡)，再呼叫該函數；
* 目的是將它重新塑造成一顆紅黑樹。
*
* 引數說明：
* node 待修正的節點
*/
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;
// 被刪除節點的"左右孩子都不為空"的情況。
if ((node->left != NULL) && (node->right != NULL)) {
// 被刪節點的後繼節點。(稱為"取代節點")
// 用它來取代"被刪節點"的位置，然後再將"被刪節點"去掉。
RBNode *replace = node;
// 獲取後繼節點
replace = replace->right;
while (replace->left != NULL) {
replace = replace->left;
}
// "node節點"不是根節點(只有根節點不存在父節點)
if (parentOf(node) != NULL) {
if (parentOf(node) == node) {
(parentOf(node))->left = replace;
} else {
(parentOf(node))->right = replace;
}
} else {
// "node節點"是根節點，更新根節點。
tree->root = replace;
}
// child是"取代節點"的右孩子，也是需要"調整的節點"。
// "取代節點"肯定不存在左孩子！因為它是一個後繼節點。
child = replace->right;
parent = parentOf(replace);
// 儲存"取代節點"的顏色
color = colorOf(replace);
// "被刪除節點"是"它的後繼節點的父節點"
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;
// 儲存"取代節點"的顏色
color = node->color;
if (child != NULL) {
child->parent = parent;
}
// "node節點"不是根節點
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;
}
/*
* 刪除結點(z)，並返回被刪除的結點
*
* 引數說明：
* tree 紅黑樹的根結點
* z 刪除的結點
*/
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);
}
//樹結構不建議使用迭代,我們可以使用前序,中序,後續遍歷來實現 需要自己寫程式碼
//前序遍歷
//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語言實現手寫紅黑樹的範例程式碼的詳細內容，更多關於C語言紅黑樹的資料請關注it145.com其它相關文章！
相關文章
-
黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列
综合看Anker超能充系列的性价比很高，并且与不仅和iPhone12/苹果<em>Mac</em>Book很配，而且适合多设备充电需求的日常使用或差旅场景，不管是安卓还是Switch同样也能用得上它，希望这次分享能给准备购入充电器的小伙伴们有所
2021-06-01 09:31:42
-
吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！
除了L4WUDU与吴亦凡已经多次共事，成为了明面上的厂牌成员，吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节，这也是20XXCLUB首次全员合照，王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让
2021-06-01 09:31:34
-
IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？
目前应用IPFS的机构：1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆，历史资料永久保存在 IPFS 6 加
2021-06-01 09:31:24
-
有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊
开拓者的车机是兼容苹果和<em>安卓</em>，虽然我不怎么用，但确实兼顾了我家人的很多需求：副驾的门板还配有解锁开关，有的时候老婆开车，下车的时候偶尔会忘记解锁，我在副驾驶可以自己开门：第二排设计很好，不仅配置了一个很大的
2021-06-01 09:30:48
-
iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？
不仅是<em>安卓</em>手机，苹果手机的降价力度也是前所未有了，iPhone12也“跳水价”了，发布价是6799元，如今已经跌至5308元，降价幅度超过1400元，最新定价确认了。iPhone12是苹果首款5G手机，同时也是全球首款5nm芯片的智能机，它
2021-06-01 09:30:45