Introduction to Red-Black Trees in C Programming
Red-Black Trees are a type of self-balancing binary search tree (BST) commonly used in computer science due to their guaranteed logarithmic height, ensuring efficient operations. They were introduced by Rudolf Bayer and later popularized by his doctoral student Lee Johnson in 1972. These trees are essential for data storage and retrieval in applications where maintaining sorted data structure and ensuring balanced tree operations are critical.
Basic Structure
A Red-Black Tree is structurally similar to a Binary Search Tree; it consists of nodes that store data, with each node having at most two children. What distinguishes Red-Black Trees from regular BSTs are the following properties:
- Node Color: Each node is colored either red or black.
- Root Property: The root node is always black.
- Leaf Property: All leaf nodes (NIL nodes) are black.
- Red Property: If a node is red, then both its children must be black.
- Black Height: Every path from a node (including root) to its descendant NIL nodes must contain the same number of black nodes.
These properties ensure that the tree remains approximately balanced, resulting in operations like insertion, deletion, and lookup to run in O(log n) time complexity, where n is the number of nodes in the tree.
Representation of Red-Black Trees in C
In C programs, Red-Black trees can be represented using structures. Here’s a typical way to define a Red-Black Tree node:
#include <stdio.h>
#include <stdlib.h>
// Define colors for nodes
typedef enum { RED, BLACK } Color;
struct Node {
int key; // Data stored in the node
Color color; // Color of the node
struct Node *parent; // Pointer to the parent node
struct Node *left; // Pointer to the left child node
struct Node *right; // Pointer to the right child node
};
typedef struct Node* RBTreeNode;
The above code defines an enum Color representing the possible colors a node can have (RED or BLACK). The Node structure holds the key value, and pointers to the parent, left, and right child nodes, alongside its color property.
Operations on Red-Black Trees
Several key operations are supported on Red-Black Trees, including search, insert, delete, and rotate. We will focus on these operations here.
Search Operation
The search operation in a Red-Black Tree works just like any other Binary Search Tree. It involves comparing the search key with keys in the nodes of the tree and traversing the tree accordingly until the desired key is found or NULL (i.e., end of tree) is reached.
RBTreeNode searchNode(RBTreeNode root, int key) {
RBTreeNode current = root;
while (current != NULL && current->key != key) {
if (key < current->key) {
current = current->left;
} else {
current = current->right;
}
}
return current;
}
Rotations
Tree rotations are used to maintain balance during insertions and deletions. There are two types of rotations: left rotation and right rotation.
Left Rotation
During left rotation, the subtree rooted at a node x is transformed such that x becomes the left child of its right child, y.
void leftRotate(RBTreeNode* root, RBTreeNode x) {
RBTreeNode y = x->right; // Set y as the right of x
x->right = y->left; // Change the right of x to the left of y
if (y->left != NULL) { // If y's left child exists, set its parent to x
y->left->parent = x;
}
y->parent = x->parent; // Move y's parent to x's
if (x->parent == NULL) { // If x was root, change root to y
(*root) = y;
} else if (x == x->parent->left) { // Check if x was left child or right child
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x; // Put x on y's left
x->parent = y;
}
Right Rotation
Right rotation performs the opposite transformation of y becoming the left child of its former parent x.
void rightRotate(RBTreeNode* root, RBTreeNode y) {
RBTreeNode x = y->left;
y->left = x->right;
if (x->right != NULL) {
x->right->parent = y;
}
x->parent = y->parent;
if (y->parent == NULL) {
(*root) = x;
} else if (y == y->parent->right) {
y->parent->right = x;
} else {
y->parent->left = x;
}
x->right = y;
y->parent = x;
}
Insertion Operation
Insertion into a Red-Black Tree involves adding a new node while preserving the tree's properties. This requires re-coloring and rotations.
void fixUpInsert(RBTreeNode* root, RBTreeNode z) {
while (z->parent != NULL && z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
RBTreeNode uncle = z->parent->parent->right;
if (uncle != NULL && uncle->color == RED) {
z->parent->color = BLACK;
uncle->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->right) {
z = z->parent;
leftRotate(root, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rightRotate(root, z->parent->parent);
}
} else {
RBTreeNode uncle = z->parent->parent->left;
if (uncle != NULL && uncle->color == RED) {
z->parent->color = BLACK;
uncle->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
rightRotate(root, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
leftRotate(root, z->parent->parent);
}
}
}
(*root)->color = BLACK; // Ensure the root is black
}
RBTreeNode createNode(int value) {
RBTreeNode node = malloc(sizeof(struct Node));
node->key = value;
node->color = RED;
node->parent = NULL;
node->left = NULL;
node->right = NULL;
return node;
}
void insertNode(RBTreeNode* root, RBTreeNode newNode) {
RBTreeNode x = NULL;
RBTreeNode y = *root;
while (y != NULL) {
x = y;
if (newNode->key < y->key) {
y = y->left;
} else {
y = y->right;
}
}
newNode->parent = x;
if (x == NULL) {
*root = newNode;
} else if (newNode->key < x->key) {
x->left = newNode;
} else {
x->right = newNode;
}
newNode->left = NULL;
newNode->right = NULL;
newNode->color = RED;
fixUpInsert(root, newNode);
}
Deletion Operation
Deleting a node may disrupt the properties of the Red-Black Tree, thus requiring adjustments using rotations and re-coloring.
void fixUpDelete(RBTreeNode* root, RBTreeNode x) {
RBTreeNode w;
while (x != *root && x->color == BLACK) {
if (x == x->parent->left) {
w = x->parent->right;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
leftRotate(root, x->parent);
w = x->parent->right;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
rightRotate(root, w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
leftRotate(root, x->parent);
x = *root;
}
} else {
w = x->parent->left;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rightRotate(root, x->parent);
w = x->parent->left;
}
if (w->right->color == BLACK && w->left->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
leftRotate(root, w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rightRotate(root, x->parent);
x = *root;
}
}
}
x->color = BLACK;
}
void transplant(RBTreeNode* root, RBTreeNode toDelete, RBTreeNode replacementNode) {
if (toDelete->parent == NULL) {
*root = replacementNode;
} else if (toDelete == toDelete->parent->left) {
toDelete->parent->left = replacementNode;
} else {
toDelete->parent->right = replacementNode;
}
if (replacementNode != NULL) {
replacementNode->parent = toDelete->parent;
}
}
RBTreeNode findMinimum(RBTreeNode node) {
while (node->left != NULL) {
node = node->left;
}
return node;
}
void deleteNode(RBTreeNode* root, RBTreeNode z) {
RBTreeNode y = z;
RBTreeNode x;
Color yOriginalColor = y->color;
if (z->left == NULL) {
x = z->right;
transplant(root, z, z->right);
} else if (z->right == NULL) {
x = z->left;
transplant(root, z, z->left);
} else {
y = findMinimum(z->right);
yOriginalColor = y->color;
x = y->right;
if (y->parent == z) {
x->parent = y;
} else {
transplant(root, y, y->right);
y->right = z->right;
y->right->parent = y;
}
transplant(root, z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
if (yOriginalColor == BLACK) {
fixUpDelete(root, x);
}
}
Application of Red-Black Trees
Red-BlackTrees are used in various applications primarily for their guaranteed O(log n) times for core operations:
- Databases: Efficient indexing and searching of records.
- File Systems: Managing directories and files efficiently.
- Symbol Tables: In compilers, symbol tables need to grow and shrink dynamically while providing fast lookup and modifications.
- Library Data Structures: Many libraries use Red-Black Trees to implement associative arrays, sets, and ordered maps.
Key Points to Remember
- Balanced: Always O(log n) operations.
- Properties: Five defining properties ensure balance.
- Complexity: Inserts and Deletes require complex adjustments with rotations and re-coloring.
- Performance: Reduces the worst-case scenario of unbalanced BSTs.
Summary
Red-Black Trees are essential data structures in computer science, known for their balanced nature and efficiency in performing dynamic operations. Their introduction of specific coloring and balancing strategies ensures they retain their logarithmic complexity in operations such as search, insert, and delete. Understanding and implementing these trees require careful attention to the properties and the methods used to maintain them. In terms of real-world applications, they find their use in various systems that require fast access to sorted data, making them an indispensable tool in software development.
C Programming Data Structures: Red-Black Trees Introduction
Data structures are essential tools in programming that help in organizing and storing data efficiently. Among various data structures, Red-Black Trees offer a balanced tree structure with efficient insertion, deletion, and lookup operations. This article will introduce you to Red-Black Trees in the context of C programming and provide a step-by-step guide to implementing and running an application using these data structures.
What are Red-Black Trees?
Red-Black Trees are a type of self-balancing binary search tree where each node contains an extra bit for denoting the color of the node, either red or black. The balancing is achieved by ensuring certain conditions hold true after every insertion and deletion operation:
- Every node is either red or black.
- All NULL nodes (leaves) are black.
- If a node is red, both its children must be black.
- Every path from a given node to any of its descendant leaves has the same number of black nodes.
These properties guarantee that the tree remains approximately balanced, with O(log n) operations for insertion, deletion, and lookup.
Setting Up the Environment
Before diving into coding, ensure you have a development environment set up with a C compiler. Common choices include GCC on Linux/Unix-based systems or MinGW for Windows. Use an Integrated Development Environment like Code::Blocks, Visual Studio Code, or CLion to facilitate coding and debugging tasks.
Step-by-Step Implementation of Red-Black Tree in C
Define Node Structure The first step is defining the structure of the nodes used in the Red-Black Tree.
typedef enum {RED, BLACK} Color; typedef struct node { int data; Color color; struct node* parent; struct node* left; struct node* right; } Node;Memory Allocation and Initialization of Nodes
Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->color = RED; newNode->left = newNode->right = newNode->parent = NULL; return newNode; }Perform Basic Tree Operations
- Left rotation
- Right rotation
- Fix the tree to maintain Red-Black properties after insertion or deletion
void rotateLeft(Node** rootRef, 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) *rootRef = y; else if(x == x->parent->left) x->parent->left = y; else x->parent->right = y; y->left = x; x->parent = y; } void rotateRight(Node** rootRef, 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) *rootRef = x; else if(y == y->parent->right) y->parent->right = x; else y->parent->left = x; x->right = y; y->parent = x; } void fixInsertViolation(Node** rootRef, Node* node) { while(node != *rootRef && node->parent != *rootRef && node->parent->color == RED) { if(node->parent == node->parent->parent->left) { Node* uncle = node->parent->parent->right; // Case 1: Uncle is red if(uncle && uncle->color == RED) { node->parent->color = BLACK; uncle->color = BLACK; node->parent->parent->color = RED; node = node->parent->parent; } else { // Case 2: Uncle is black and node is a right child if(node == node->parent->right) { node = node->parent; rotateLeft(rootRef, node); } // Case 3: Uncle is black and node is a left child node->parent->color = BLACK; node->parent->parent->color = RED; rotateRight(rootRef, node->parent->parent); } } else { Node* uncle = node->parent->parent->left; // Case 1: Uncle is red if(uncle && uncle->color == RED) { node->parent->color = BLACK; uncle->color = BLACK; node->parent->parent->color = RED; node = node->parent->parent; } else { // Case 2: Uncle is black and node is a left child if(node == node->parent->left) { node = node->parent; rotateRight(rootRef, node); } // Case 3: Uncle is black and node is a right child node->parent->color = BLACK; node->parent->parent->color = RED; rotateLeft(rootRef, node->parent->parent); } } } (*rootRef)->color = BLACK; } void insertBST(Node** rootRef, Node* node) { if(*rootRef == NULL) { *rootRef = node; (*rootRef)->color = BLACK; return; } Node* temp = *rootRef; while(1) { if(node->data < temp->data) { if(temp->left != NULL) temp = temp->left; else { temp->left = node; node->parent = temp; break; } } else { if(temp->right != NULL) temp = temp->right; else { temp->right = node; node->parent = temp; break; } } } } void insertRBTNode(Node** rootRef, int key) { Node* node = createNode(key); insertBST(rootRef, node); fixInsertViolation(rootRef, node); }Traversal Methods In-order, Pre-order, and Post-order Traversal functions can be implemented to read the contents of the Red-Black Tree.
Helper Functions Create additional utility functions such as tree search, delete operations, and balancing.
Running the Application
With the above implementation, you can now build a simple console-based application in C that allows users to insert elements into a Red-Black Tree and perform other operations like searching and deleting elements.
#include <stdio.h>
#include <stdlib.h>
int main() {
Node* root = NULL;
insertRBTNode(&root, 10);
insertRBTNode(&root, 20);
insertRBTNode(&root, 30);
// Perform other operations like searching and deleting...
return 0;
}
Frontend and Backend
Though this specific implementation is purely on the backend side (console application), it can be extended to create a frontend in languages like HTML/CSS/JavaScript (for web applications) or Tkinter (GUI applications). The backend logic will remain unchanged, but the way it's interacted with by the user will differ.
Example: Simple Web Interface using HTML & JavaScript
Create a web page that uses AJAX to communicate with a server-side C application (compiled as CGI script).
<html>
<head>
<script>
function addNode() {
var input = document.getElementById("nodeInput").value;
var xhr = new XMLHttpRequest();
xhr.onreadystatechange = function() {
if (xhr.readyState == 4 && xhr.status == 200) {
document.getElementById("response").innerHTML = "Node Inserted!";
}
};
xhr.open("GET", "/cgi-bin/add_node.cgi?data=" + input, true);
xhr.send();
}
</script>
</head>
<body>
<h1>Red-Black Tree Management</h1>
<input type="text" id="nodeInput"><button onclick="addNode()">Add Node</button>
<div id="response"></div>
</body>
</html>
Example: CGI Script (add_node.cgi)
This script compiles the C code that inserts a node into the Red-Black Tree using the data provided via GET request.
#include <stdio.h>
#include <stdlib.h>
#include "rbt.c" // Include our Red Black Tree source file
int main(void) {
int data;
printf("Content-Type: text/html\n\n");
sscanf(getenv("QUERY_STRING"), "data=%d", &data);
Node* root = NULL;
insertRBTNode(&root, data);
// Assuming we also have a function to print the tree
// printInOrder(root); // For demonstration purposes
return 0;
}
Note: The above examples are simplified and for illustration purposes only. Actual implementation would require handling errors, security issues, and more robust data management.
Conclusion
Implementing Red-Black Trees requires careful attention to maintain the balance properties of the tree. By following these steps, you can successfully create and run applications that utilize these efficient data structures. Further enhancing your code with a frontend interface opens possibilities for interactive user experiences. Happy coding!
Top 10 Questions and Answers about C Programming Data Structures: Red-Black Trees (Intro)
Question 1: What is a Red-Black Tree?
Answer: A Red-Black Tree is a self-balancing binary search tree where each node contains an extra bit for denoting the color of the node, either red or black. The balancing properties of Red-Black Trees ensure that the longest path from the root to a leaf is no more than twice as long as the shortest path, leading to relatively balanced trees and efficient operations such as insertion, deletion, and lookup with a time complexity of O(log n).
Question 2: What are the properties of Red-Black Trees?
Answer: To maintain balance, Red-Black Trees adhere to the following five properties:
- Node Color Property: Each node is either red or black.
- Root Property: The root of the tree is always black.
- Leaf Property: All leaf (NIL) nodes are black. NIL nodes do not contain data and act as sentinels.
- Red Property: If a node is red, both its children must be black.
- Black Property: Every path from the node to its descendant leaves must have the same number of black nodes.
These properties enforce balance and allow for fast operations.
Question 3: Why use Red-Black Trees over other types of balanced trees?
Answer: Red-Black Trees are used over other types of balanced trees because they provide a good balance between simplicity and performance. Compared to AVL trees, which require rotations on every insert/delete operation to maintain balance, Red-Black Trees require amortized constant time per rotation during insertions and deletions. This results in overall faster insert and delete operations, making them suitable for applications where frequent modifications occur, such as databases and file systems.
Question 4: What are the basic operations that can be performed on a Red-Black Tree?
Answer: The fundamental operations that can be performed on Red-Black Trees include:
- Insertion: Adding a new node while ensuring the tree remains a valid Red-Black Tree.
- Deletion: Removing a node while maintaining the Red-Black properties.
- Search: Locating a node using the binary search property.
- Traversal: Performing in-order, pre-order, or post-order traversal to examine all the nodes in the tree.
Question 5: How does the insertion process work in Red-Black Trees?
Answer: Inserting a node into a Red-Black Tree involves these steps:
- Binary Search Tree Insertion: Start by inserting the node as you would in an unbalanced Binary Search Tree.
- Coloring the Node Red: Set the color of the newly inserted node to red. This helps avoid immediate violation of the Black Property.
- Fixing Violations: After insertion, the tree may violate some Red-Black properties. The violations are fixed primarily by re-coloring and rotating nodes until the tree becomes a valid Red-Black Tree again.
Re-coloring and rotations can vary depending on the parent and uncle colors of the inserted node, but common scenarios include:
- Case 1: Uncle is red, re-color the parent, grands parent, and Uncle as per rules.
- Case 2 & Case 3: Uncle is black and the inserted node's parent is tilted to one side with respect to the grandparent. Perform a single or double rotation along with re-coloring based on conditions.
Question 6: How is re-coloring applied in fixing Red-Black Tree violations after insertion?
Answer: Re-coloring is a mechanism to fix the Red-Black Properties involving recoloring specific nodes. Typically, it is applied when the inserted node and its parent are both red, violating the Red Property. Re-coloring can be summarized into the following scenarios:
- Uncle Node is Red: Both the parent and uncle nodes are recolored to black, and the grandparent is recolored to red. This may cause further violations up the tree, requiring additional re-coloring.
- Uncle Node is Black: Re-coloring alone will not resolve the violations unless accompanied by rotations.
After potential re-coloring, if violations persist (due to uncle being black), rotations are necessary to correct the structure of the tree.
Question 7: How do rotations help in maintaining Red-Black Trees’ balance?
Answer: Rotations serve two critical functions in maintaining the balance of Red-Black Trees:
Single Rotation: Used when the tree needs a simple adjustment like rearranging nodes at consecutive levels. It consists of either a leftRotation or rightRotation based on the configuration of the inserted node, its parent, and the grandparent. For example, if the newly inserted red node’s parent is red and its uncle is black, a single rotation (either left or right) may be sufficient to restructure the tree.
- Left Rotation: The left rotation fixes a situation where the right child of a node is red, and its left child or both children are black.
- Right Rotation: Conversely, right rotation fixes a situation where the left child of a node is red and its right child or both children are black.
Double Rotation: Needed when violations involve two red nodes not in a single line or consecutive levels (zig-zag pattern). A double rotation involves applying a single rotation to the inserted node and its parent first, followed by another single rotation between the original parent and grandparent.
Question 8: Can you explain the structure of a Red-Black Tree?
Answer: The structural components of a Red-Black Tree are:
- Nodes: Each node contains a value, pointers to its left and right children, and a color attribute (red or black).
- Root Node: The topmost node of the tree, which is black and serves as the entry point.
- NIL Nodes: These are sentinel nodes representing the leaves of the tree. They are black and do not contain any data.
- Pointers and References: Every node points to its parent (except the root), left child, and right child. Managing these pointers correctly is crucial during rotations and rebalancing.
The diagrammatic representation of a Red-Black Tree typically includes:
struct RBTreeNode {
int key; // Data stored in node
struct RBTreeNode *left; // Pointer to left child
struct RBTreeNode *right; // Pointer to right child
struct RBTreeNode *parent;// Pointer to parent
char color; // 'R' for red, 'B' for black
};
struct RBTree {
struct RBTreeNode *root; // Root of the tree
struct RBTreeNode *nil; // Sentinel NIL node, initialized to black
};
Question 9: What is the time complexity of operations on a Red-Black Tree?
Answer: The time complexity for the primary operations on a Red-Black Tree is O(log n), where n is the number of nodes in the tree:
- Search: Given the binary search properties, locating an element takes O(log n) time.
- Insertion: Inserting a new element requires traversing the tree to find the appropriate position (O(log n) due to height), followed by possible rotations and re-coloring (which remain in O(log n)).
- Deletion: Similarly, deleting a node involves locating the node (O(log n)), adjustments for potential black-height violation (requiring a series of rotations and re-colorings, still in O(log n)), and maintaining overall tree integrity.
- Traversal: Traversal methods like in-order, pre-order, or post-order take O(n) time since each node needs to be accessed once.
Question 10: How would you implement a basic Red-Black Tree in C?
Answer: Implementing a basic Red-Black Tree involves defining node structures, initializing the tree, and implementing key operations like insertion, deletion, and rotation while respecting the Red-Black Properties. Below is a concise skeleton outline of a Red-Black Tree implementation in C:
Firstly, define the node structure:
#include <stdio.h>
#include <stdlib.h>
typedef enum { RED, BLACK } COLOR;
typedef struct Node {
int value;
COLOR color;
struct Node *left;
struct Node *right;
struct Node *parent;
} Node;
typedef struct RBTree {
Node *root;
Node *nil; // Sentinel NIL node, which is always black
} RBTree;
Initialize the NIL node and create the tree:
Node* newNode(int value, Node* nil) {
Node* node = (Node*) malloc(sizeof(Node));
node->value = value;
node->color = RED; // New nodes start red
node->left = nil;
node->right = nil;
node->parent = NULL;
return node;
}
RBTree* createRBTree() {
RBTree* tree = (RBTree*)malloc(sizeof(RBTree));
tree->nil = newNode(-1, NULL);
tree->nil->color = BLACK;
tree->root = tree->nil;
return tree;
}
Define utility functions:
void rotateLeft(RBTree* tree, Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != tree->nil)
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 rotateRight(RBTree* tree, Node* y) {
Node* x = y->left;
y->left = x->right;
if (x->right != tree->nil)
x->right->parent = y;
x->parent = y->parent;
if (y->parent == NULL)
tree->root = x;
else if (y == y->parent->right)
y->parent->right = x;
else
y->parent->left = x;
x->right = y;
y->parent = x;
}
Implement insertion and balancing logic:
void insertFixup(RBTree* tree, Node* z) {
while (z->parent && z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
Node* y = z->parent->parent->right;
if (y != tree->nil && 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;
rotateLeft(tree, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rotateRight(tree, z->parent->parent);
}
}
else {
Node* y = z->parent->parent->left;
if (y != tree->nil && 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;
rotateRight(tree, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rotateLeft(tree, z->parent->parent);
}
}
}
tree->root->color = BLACK;
}
void insertRBTree(RBTree* tree, int value) {
Node* z = newNode(value, tree->nil);
Node* y = tree->nil;
Node* x = tree->root;
while (x != tree->nil) {
y = x;
if (z->value < x->value)
x = x->left;
else
x = x->right;
}
z->parent = y;
if (y == tree->nil)
tree->root = z;
else if (z->value < y->value)
y->left = z;
else
y->right = z;
z->left = tree->nil;
z->right = tree->nil;
z->color = RED;
insertFixup(tree, z);
}
This code sets up a Red-Black Tree structure and provides the core logic for insertion and necessary rotations to maintain Red-Black Properties. Further implementations would involve similar procedures for searching, deleting nodes, and possibly adding more utility functions.
While this is a basic implementation, Red-Black Trees require careful handling of various cases to ensure the balancing properties continue to hold. The provided functions form the foundation for building a fully operational Red-Black Tree in C.