Red-Black tree
Posté : dim. sept. 08, 2024 5:36 pm
Code : Tout sélectionner
#include <stdio.h>
#include <stdlib.h>
typedef enum { RED, BLACK } Color;
typedef struct Node {
int data;
Color color;
struct Node* parent;
struct Node* left;
struct Node* right;
} Node;
typedef struct RedBlackTree {
Node* root;
} RedBlackTree;
Node* createNode(int data, Color color, Node* parent, Node* left, Node* right) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
perror("Erreur lors de l'allocation de mémoire pour le nœud.");
exit(EXIT_FAILURE);
}
newNode->data = data;
newNode->color = color;
newNode->parent = parent;
newNode->left = left;
newNode->right = right;
return newNode;
}
void leftRotate(RedBlackTree* tree, Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != NULL) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL) {
tree->root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
void rightRotate(RedBlackTree* tree, Node* y) {
Node* x = y->left;
y->left = x->right;
if (x->right != NULL) {
x->right->parent = y;
}
x->parent = y->parent;
if (y->parent == NULL) {
tree->root = x;
} else if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
x->right = y;
y->parent = x;
}
void insertFixup(RedBlackTree* tree, Node* z) {
while (z != tree->root && z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
Node* y = z->parent->parent->right;
if (y != NULL && 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(tree, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rightRotate(tree, z->parent->parent);
}
} else {
Node* y = z->parent->parent->left;
if (y != NULL && 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(tree, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
leftRotate(tree, z->parent->parent);
}
}
}
tree->root->color = BLACK;
}
void insertNode(RedBlackTree* tree, int data) {
Node* z = createNode(data, RED, NULL, NULL, NULL);
Node* y = NULL;
Node* x = tree->root;
while (x != NULL) {
y = x;
if (z->data < x->data) {
x = x->left;
} else {
x = x->right;
}
}
z->parent = y;
if (y == NULL) {
tree->root = z;
} else if (z->data < y->data) {
y->left = z;
} else {
y->right = z;
}
insertFixup(tree, z);
}
void printTree(Node* root, int level) {
if (root != NULL) {
printTree(root->right, level + 1);
for (int i = 0; i < level; i++) {
printf(" ");
}
printf("%d(%s)\n", root->data, (root->color == RED) ? "RED" : "BLACK");
printTree(root->left, level + 1);
}
}
void testRedBlackTree() {
RedBlackTree tree = { NULL };
int values[] = { 7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13 , 23 , 12 , 4 , 8 , 27 , 1 , 2 , 9 };
int numValues = sizeof(values) / sizeof(values[0]);
for (int i = 0; i < numValues; i++) {
insertNode(&tree, values[i]);
printf("Arbre après insertion de %d :\n", values[i]);
printTree(tree.root, 0);
printf("\n");
}
}
int main() {
testRedBlackTree();
return 0;
}