用C++写一个红黑树代码
时间: 2023-03-20 09:03:05 浏览: 56
很高兴能回答您的问题。红黑树是一种平衡二叉搜索树,它的特性是每个节点的左子树和右子树的高度差不能超过1,下面是一个用C语言实现的红黑树代码:#define RED 0
#define BLACK 1// 定义红黑树节点
struct node
{
int data;
int color;
node * left, * right, * parent;
}; // 定义红黑树类
class RBTree
{
node *root;
public :
// 构造函数
RBTree() { root = NULL; }
// 插入节点
void insert(int data);
// 中序遍历
void inorder();
// 删除节点
void remove(int data);
}; // 插入节点
void RBTree::insert(int data)
{
node *z = new node;
z->data = data;
z->left = z->right = z->parent = NULL;
z->color = RED;
node *y = NULL;
node *x = this->root;
while (x != NULL)
{
y = x;
if (z->data < x->data)
x = x->left;
else
x = x->right;
}
z->parent = y;
if (y == NULL)
this->root = z;
else if (z->data < y->data)
y->left = z;
else
y->right = z;
fix(z);
} // 修复树
void RBTree::fix(node *z)
{
node *y;
while (z->parent->color == RED)
{
if (z->parent == z->parent->parent->left)
{
y = z->parent->parent->right;
if (y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if (z == z->parent->right)
{
z = z->parent;
leftRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rightRotate(z->parent->parent);
}
}
else
{
y = z->parent->parent->left;
if (y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if (z == z->parent->left)
{
z = z->parent;
rightRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
leftRotate(z->parent->parent);
}
}
}
this->root->color = BLACK;
}