// rbt_insert_from_slides.
c — Red-Black Tree Insert based on slide analysis
// Compile: gcc rbt_insert_from_slides.c -o rbt
// Run: ./rbt
#include <stdio.h>
#include <stdlib.h>
typedef enum { RED = 0, BLACK = 1 } Color;
typedef struct Node {
int key;
Color color;
struct Node *left, *right, *parent;
} Node;
static Node *NIL = NULL; // shared BLACK sentinel
static Node *root = NULL; // current root
// ---------- setup ----------
static void init_tree(void) {
if (!NIL) {
NIL = (Node*)malloc(sizeof(Node));
NIL->key = 0;
NIL->color = BLACK;
NIL->left = NIL->right = NIL->parent = NULL;
}
root = NIL;
}
static Node* new_node(int key) {
Node* z = (Node*)malloc(sizeof(Node));
z->key = key;
z->color = RED; // slides: new insert is RED
z->left = z->right = z->parent = NIL;
return z;
}
// ---------- rotations ----------
static void left_rotate(Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != NIL) y->left->parent = x;
y->parent = x->parent;
if (x->parent == NIL) root = y;
else if (x == x->parent->left) x->parent->left = y;
else x->parent->right = y;
y->left = x;
x->parent = y;
}
static void right_rotate(Node* x) {
Node* y = x->left;
x->left = y->right;
if (y->right != NIL) y->right->parent = x;
y->parent = x->parent;
if (x->parent == NIL) root = y;
else if (x == x->parent->right) x->parent->right = y;
else x->parent->left = y;
y->right = x;
x->parent = y;
}
// ---------- fix-up per slides ----------
static void insert_fix(Node* z) {
while (z->parent->color == RED) { // violation: red-red
if (z->parent == z->parent->parent->left) {
Node* y = z->parent->parent->right; // uncle
if (y->color == RED) {
// Case: Uncle red → recolor and move up
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->right) {
// Case: LR → rotate parent left
z = z->parent;
left_rotate(z);
}
// Case: LL → rotate grandparent right + recolor
z->parent->color = BLACK;
z->parent->parent->color = RED;
right_rotate(z->parent->parent);
}
} else { // mirror side
Node* y = z->parent->parent->left; // uncle
if (y->color == RED) {
// Uncle red → recolor and move up
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
// Case: RL → rotate parent right
z = z->parent;
right_rotate(z);
}
// Case: RR → rotate grandparent left + recolor
z->parent->color = BLACK;
z->parent->parent->color = RED;
left_rotate(z->parent->parent);
}
}
}
root->color = BLACK; // slides: root must be BLACK
}
// ---------- BST insert + fix ----------
static void rb_insert(int key) {
Node* z = new_node(key);
Node* y = NIL;
Node* x = root;
// Standard BST insert
while (x != NIL) {
y = x;
if (z->key < x->key) x = x->left;
else x = x->right;
}
z->parent = y;
if (y == NIL) root = z;
else if (z->key < y->key) y->left = z;
else y->right = z;
// repair violations
insert_fix(z);
}
// ---------- helpers for testing ----------
static void inorder(Node* x) {
if (x == NIL) return;
inorder(x->left);
printf("%d(%c) ", x->key, x->color == RED ? 'R' : 'B');
inorder(x->right);
}
int main(void) {
init_tree();
int n;
printf("Enter number of keys: ");
if (scanf("%d", &n) != 1 || n < 0) return 0;
printf("Enter %d keys: ", n);
for (int i = 0; i < n; ++i) {
int k; scanf("%d", &k);
rb_insert(k);
}
printf("Inorder (key(color)):
");
inorder(root);
printf("
");
return 0;
}