写一份c++红黑树代码
时间: 2023-03-12 20:19:53 浏览: 113
红黑树C++代码实现
4星 · 用户满意度95%
C语言红黑树代码:#include <stdio.h>
#include <stdlib.h>
// 树节点的定义
struct node
{
int key;
char color;
struct node *left;
struct node *right;
struct node *parent;
};
// 根节点的定义
struct node *root = NULL;
// 左旋转函数
void leftRotate(struct node *x)
{
struct node *y = x->right;
// 将y的左孩子变成x的右孩子
x->right = y->left;
if (y->left != NULL)
y->left->parent = x;
// 将x的父节点变成y的父节点
y->parent = x->parent;
if (x->parent == NULL)
root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
// 将x变成y的左孩子
y->left = x;
x->parent = y;
}
// 右旋转函数
void rightRotate(struct node *x)
{
struct node *y = x->left;
// 将y的右孩子变成x的左孩子
x->left = y->right;
if (y->right != NULL)
y->right->parent = x;
// 将x的父节点变成y的父节点
y->parent = x->parent;
if (x->parent == NULL)
root = y;
else if (x == x->parent->right)
x->parent->right = y;
else
x->parent->left = y;
// 将x变成y的右孩子
y->right = x;
x->parent = y;
}
阅读全文