C语言实现手写红黑树的示例代码
目录
- 前沿
- 红黑树代码
- 测试
前沿
写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);
}
以上就是C语言实现手写红黑树的示例代码的详细内容，更多关于C语言红黑树的资料请关注我们其它相关文章！
赞 (0)
相关推荐
-
C语言实现红黑树的实例代码
因为看内核的时候感觉红黑树挺有意思的,所以利用周末的时间来实现一下玩玩.红黑树的操作主要是插入和删除,而删除的时候需要考虑的情况更多一些.具体的操作就不在这里罗嗦了,百度文库里面有一个比较有好的文章,已经说的很明白了. 在看具体的操作的时候有的人可能感觉有些情况是没有考虑到的(如果没有这种感觉的人很有可能根本没有仔细地想).但是那些"遗漏"的情况如果存在的话,操作之前的红黑树将违反那几个规则. 写代码的时候很多次因为少考虑情况而导致错误,细节比较多,刚开始rb_node中没有指向父节点
-
C语言实现红黑树详细步骤+代码
目录 红黑树的概念 红黑树的性质 红黑树的定义与树结构 插入 新增结点插入后维护红黑树性质的主逻辑 拆解讨论: 旋转 验证 红黑树与AVl树的比较 红黑树的应用 总结 红黑树的概念 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的 概念总结:红黑树是二叉搜索树的升级,结点里面存放的成员col标记当前结点的颜色,它的最长路径最多是最短
-
C语言实现手写红黑树的示例代码
目录 前沿 红黑树代码 测试 前沿 写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
-
C语言实现手写Map(数组+链表+红黑树)的示例代码
目录 要求 结构 红黑树和链表转换策略 hash 使用 要求 需要准备数组集合(List) 数据结构 需要准备单向链表(Linked) 数据结构 需要准备红黑树(Rbtree)数据结构 需要准备红黑树和链表适配策略(文章内部提供,可以自行参考) 建议先去阅读我博客这篇文章C语言-手写Map(数组+链表)(全功能)有助于理解 hashmap使用红黑树的原因是: 当某个节点值过多的时候那么链表就会非常长,这样搜索的时候查询速度就是O(N) 线性查询了,为了避免这个问题我们使用了红黑树,当链表长度大于
-
C语言手写集合List的示例代码
目录 前沿 定义结构 创建List 扩容 创建数据节点 给集合添加值 删除集合内指定的值 删除集合内指定下标的值 打印集合 迭代器 查询指定元素的下标(第一个) 末尾查询指定元素下标(第一个) 判断数组是否有序 二分查询 修改集合指定元素的值 快速排序 集合去重 集合复制 集合合并 集合差集 集合补集 集合并集 集合交集 销毁集合 前沿 数组长度是固定的,那么在很多时候我们并不知道到底有多少数据需要存储,这时候我么就需要一个可变长度的数组来进行存储,在C语言中需要我们自己进行定义,我们称为集合
-
超详细PyTorch实现手写数字识别器的示例代码
前言 深度学习中有很多玩具数据,mnist就是其中一个,一个人能否入门深度学习往往就是以能否玩转mnist数据来判断的,在前面很多基础介绍后我们就可以来实现一个简单的手写数字识别的网络了 数据的处理 我们使用pytorch自带的包进行数据的预处理 import torch import torchvision import torchvision.transforms as transforms import numpy as np import matplotlib.pyplot as plt
-
PyTorch实现手写数字识别的示例代码
目录 加载手写数字的数据 数据加载器(分批加载) 建立模型 模型训练 测试集抽取数据,查看预测结果 计算模型精度 自己手写数字进行预测 加载手写数字的数据 组成训练集和测试集,这里已经下载好了,所以download为False import torchvision # 是否支持gpu运算 # device = torch.device('cuda' if torch.cuda.is_available() else 'cpu') # print(device) # print(torch.cud
-
利用Java手写阻塞队列的示例代码
目录 前言 需求分析 阻塞队列实现原理 线程阻塞和唤醒 数组循环使用 代码实现 成员变量定义 构造函数 put函数 offer函数 add函数 take函数 重写toString函数 完整代码 总结 前言 在我们平时编程的时候一个很重要的工具就是容器,在本篇文章当中主要给大家介绍阻塞队列的原理,并且在了解原理之后自己动手实现一个低配版的阻塞队列. 需求分析 在前面的两篇文章ArrayDeque(JDK双端队列)源码深度剖析和深入剖析(JDK)ArrayQueue源码当中我们仔细介绍了队列的原理,
-
手写Java LockSupport的示例代码
目录 前言 LockSupport实现原理 自己动手实现自己的LockSupport 实现原理 自己实现LockSupport协议规定 工具 具体实现 完整代码 JVM实现一瞥 总结 前言 在JDK当中给我们提供的各种并发工具当中,比如ReentrantLock等等工具的内部实现,经常会使用到一个工具,这个工具就是LockSupport.LockSupport给我们提供了一个非常强大的功能,它是线程阻塞最基本的元语,他可以将一个线程阻塞也可以将一个线程唤醒,因此经常在并发的场景下进行使用. Lo
-
Java实现手写自旋锁的示例代码
目录 前言 自旋锁 原子性 自己动手写自旋锁 自己动手写可重入自旋锁 总结 前言 我们在写并发程序的时候,一个非常常见的需求就是保证在某一个时刻只有一个线程执行某段代码,像这种代码叫做临界区,而通常保证一个时刻只有一个线程执行临界区的代码的方法就是锁.在本篇文章当中我们将会仔细分析和学习自旋锁,所谓自旋锁就是通过while循环实现的,让拿到锁的线程进入临界区执行代码,让没有拿到锁的线程一直进行while死循环,这其实就是线程自己“旋”在while循环了,因而这种锁就叫做自旋锁. 自旋锁 原子性
-
Java实现手写线程池的示例代码
目录 前言 线程池给我们提供的功能 工具介绍 Worker设计 线程池设计 总结 前言 在我们的日常的编程当中,并发是始终离不开的主题,而在并发多线程当中,线程池又是一个不可规避的问题.多线程可以提高我们并发程序的效率,可以让我们不去频繁的申请和释放线程,这是一个很大的花销,而在线程池当中就不需要去频繁的申请线程,他的主要原理是申请完线程之后并不中断,而是不断的去队列当中领取任务,然后执行,反复这样的操作.在本篇文章当中我们主要是介绍线程池的原理,因此我们会自己写一个非常非常简单的线程池,主要帮