C语言红黑树
胡安民-独行者 人气:0前沿
写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 ,他的内存地址是:%p\n", 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 ,他的内存地址是:%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);
}
}
/*
* 对红黑树的节点(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);
}
加载全部内容