请编写一下C语言红黑树代码
时间: 2023-03-10 09:57:18 浏览: 120
C语言红黑树的代码如下:
#include<stdio.h>
#include<stdlib.h> /*
* 定义红黑树的节点
*/
struct rb_node
{
int key;
struct rb_node *left;
struct rb_node *right;
struct rb_node *parent;
int color;
};/*
* 定义红黑树的根节点
*/
struct rb_root
{
struct rb_node *rb_node;
};/*
* 初始化红黑树
*/
void rb_init(struct rb_root *root)
{
root->rb_node = NULL;
}/*
* 对红黑树节点x进行左旋转
*/
void left_rotate(struct rb_root *root, struct rb_node *x)
{
// 设置x的右孩子为y
struct rb_node *y = x->right;
// 将 “y的左孩子” 设为 “x的右孩子”;
// 如果y的左孩子非空,将 “x” 设为 “y的左孩子的父亲”
x->right = y->left;
if (y->left != NULL)
y->left->parent = x;
// 将 “x的父亲” 设为 “y的父亲”
y->parent = x->parent;
if (x->parent == NULL)
{
root->rb_node = y; // 如果 “x的父亲” 是空节点,则将y设为根节点
}
else
{
if (x->parent->left == x)
x->parent->left = y; // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”
else
x->parent->right = y; // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”
}
// 将 “x” 设为 “y的左孩子”
y->left = x;
// 将 “x的父节点” 设为 “y”
x->parent = y;
}/*
* 对红黑树节点y进行右旋转
*/
void right_rotate(struct rb_root *root, struct rb_node *y)
{
// 设置x是当前节点的左孩子。
struct rb_node *x = y->left;
// 将 “x的右孩子” 设为 “y的左孩子”;
// 如果"x的右孩子"不为空的话,将 “y” 设为 “x的右孩子的父亲”
y->left = x->right;
if (x->right != NULL)
x->right->parent = y;
// 将 “y的父亲” 设为 “x的父亲”
x->parent = y->parent;
if (y->parent == NULL)
{
root->rb_node = x; // 如果 “y的父亲” 是空节点,则将x设为根节点
}
else
{
if (y == y->parent->right)
y->parent->right = x; // 如果 y是它父节点的右孩子,则将x设为“y的父节点的右孩子”
else
y->parent->left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
}
// 将 “y” 设为 “x的右孩子”
x->right = y;
// 将 “y的父节点” 设为 “x”
y->parent = x;
}
阅读全文