Red Black Tree
A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer who called them "symmetric binary B-trees", but acquired its modern name in a paper in 1978 by Leonidas J. Guibas and Robert Sedgewick. It is complex, but has good worst-case running time for its operations and is efficient in practice: it can search, insert, and delete in O(log n) time, where n is total number of elements in the tree. Put very simply, a red-black tree is a binary search tree which inserts and removes intelligently, to ensure the tree is reasonably balanced.
#include <stdlib.h>
#include "fatal.h"
typedef int ElementType;
#define NegInfinity (-10000)
#ifndef _RedBlack_H
#define _RedBlack_H
struct RedBlackNode;
typedef struct RedBlackNode *Position;
typedef struct RedBlackNode *RedBlackTree;
RedBlackTree MakeEmpty(RedBlackTree T);
Position Find(ElementType X, RedBlackTree T);
Position FindMin(RedBlackTree T);
Position FindMax(RedBlackTree T);
RedBlackTree Initialize(void);
RedBlackTree Insert(ElementType X, RedBlackTree T);
RedBlackTree Remove(ElementType X, RedBlackTree T);
ElementType Retrieve(Position P);
void PrintTree(RedBlackTree T);
#endif /* _RedBlack_H */
#include "redblack.h"
#include <stdlib.h>
#include "fatal.h"
typedef enum ColorType {
Red, Black
} ColorType;
struct RedBlackNode {
ElementType Element;
RedBlackTree Left;
RedBlackTree Right;
ColorType Color;
};
static Position NullNode = NULL; /* Needs initialization */
/* Initialization procedure */
RedBlackTree
Initialize(void) {
RedBlackTree T;
if (NullNode == NULL) {
NullNode = malloc(sizeof ( struct RedBlackNode));
if (NullNode == NULL)
FatalError("Out of space!!!");
NullNode->Left = NullNode->Right = NullNode;
NullNode->Color = Black;
NullNode->Element = 12345;
}
/* Create the header node */
T = malloc(sizeof ( struct RedBlackNode));
if (T == NULL)
FatalError("Out of space!!!");
T->Element = NegInfinity;
T->Left = T->Right = NullNode;
T->Color = Black;
return T;
}
/* END */
void
Output(ElementType Element) {
printf("%d\n", Element);
}
/* Print the tree, watch out for NullNode, */
/* and skip header */
static void
DoPrint(RedBlackTree T) {
if (T != NullNode) {
DoPrint(T->Left);
Output(T->Element);
DoPrint(T->Right);
}
}
void
PrintTree(RedBlackTree T) {
DoPrint(T->Right);
}
/* END */
static RedBlackTree
MakeEmptyRec(RedBlackTree T) {
if (T != NullNode) {
MakeEmptyRec(T->Left);
MakeEmptyRec(T->Right);
free(T);
}
return NullNode;
}
RedBlackTree
MakeEmpty(RedBlackTree T) {
T->Right = MakeEmptyRec(T->Right);
return T;
}
Position
Find(ElementType X, RedBlackTree T) {
if (T == NullNode)
return NullNode;
if (X < T->Element)
return Find(X, T->Left);
else
if (X > T->Element)
return Find(X, T->Right);
else
return T;
}
Position
FindMin(RedBlackTree T) {
T = T->Right;
while (T->Left != NullNode)
T = T->Left;
return T;
}
Position
FindMax(RedBlackTree T) {
while (T->Right != NullNode)
T = T->Right;
return T;
}
/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */
static Position
SingleRotateWithLeft(Position K2) {
Position K1;
K1 = K2->Left;
K2->Left = K1->Right;
K1->Right = K2;
return K1; /* New root */
}
/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights, then return new root */
static Position
SingleRotateWithRight(Position K1) {
Position K2;
K2 = K1->Right;
K1->Right = K2->Left;
K2->Left = K1;
return K2; /* New root */
}
/* Perform a rotation at node X */
/* (whose parent is passed as a parameter) */
/* The child is deduced by examining Item */
static Position
Rotate(ElementType Item, Position Parent) {
if (Item < Parent->Element)
return Parent->Left = Item < Parent->Left->Element ?
SingleRotateWithLeft(Parent->Left) :
SingleRotateWithRight(Parent->Left);
else
return Parent->Right = Item < Parent->Right->Element ?
SingleRotateWithLeft(Parent->Right) :
SingleRotateWithRight(Parent->Right);
}
static Position X, P, GP, GGP;
static
void HandleReorient(ElementType Item, RedBlackTree T) {
X->Color = Red; /* Do the color flip */
X->Left->Color = Black;
X->Right->Color = Black;
if (P->Color == Red) /* Have to rotate */ {
GP->Color = Red;
if ((Item < GP->Element) != (Item < P->Element))
P = Rotate(Item, GP); /* Start double rotate */
X = Rotate(Item, GGP);
X->Color = Black;
}
T->Right->Color = Black; /* Make root black */
}
RedBlackTree
Insert(ElementType Item, RedBlackTree T) {
X = P = GP = T;
NullNode->Element = Item;
while (X->Element != Item) /* Descend down the tree */ {
GGP = GP;
GP = P;
P = X;
if (Item < X->Element)
X = X->Left;
else
X = X->Right;
if (X->Left->Color == Red && X->Right->Color == Red)
HandleReorient(Item, T);
}
if (X != NullNode)
return NullNode; /* Duplicate */
X = malloc(sizeof ( struct RedBlackNode));
if (X == NULL)
FatalError("Out of space!!!");
X->Element = Item;
X->Left = X->Right = NullNode;
if (Item < P->Element) /* Attach to its parent */
P->Left = X;
else
P->Right = X;
HandleReorient(Item, T); /* Color it red; maybe rotate */
return T;
}
RedBlackTree
Remove(ElementType Item, RedBlackTree T) {
printf("Remove is unimplemented\n");
if (Item)
return T;
return T;
}
ElementType
Retrieve(Position P) {
return P->Element;
}
#include "redblack.h"
#include <stdio.h>
#define N 800
main() {
RedBlackTree T;
Position P;
int i;
int j = 0;
T = Initialize();
T = MakeEmpty(T);
for (i = 0; i < N; i++, j = (j + 7) % N)
T = Insert(j, T);
printf("Inserts are complete\n");
for (i = 0; i < N; i++)
if ((P = Find(i, T)) == NULL || Retrieve(P) != i)
printf("Error at %d\n", i);
printf("Min is %d, Max is %d\n", Retrieve(FindMin(T)),
Retrieve(FindMax(T)));
return 0;
}