Ниже мы приводим коды, реализующие работу с красно-черными деревьями на Си. Операторы typedef T, а также сравнивающие compLT и compEQ следует изменить так, чтобы они соответствовали данным, хранимым в узлах дерева. В каждом узле типа Node хранятся указатели left, right на двух потомков и parent на предка. Цвет узла хранится в поле color и может быть либо RED, либо BLACK. Собственно данные хранятся в поле data. Все листья дерева являются "сторожевыми" (sentinel), что сильно упрощает коды. Узел root является корнем дерева и в самом начале является сторожевым.Функция insertNode запрашивает память под новый узел, устанавливает нужные значения его полей и вставляет в дерево. Соответственно, она вызывает insertFixup, которая следит за сохранением красно-черных свойств. Функция deleteNode удаляет узел из дерева. Она вызывает deleteFixup, которая восстанавливает красно-черные свойства. Функция findNode ищет в дереве нужный узел.
// Коды для красно-черных деревьев
typedef int T; /* type of item to be sorted */
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)
typedef enum { BLACK, RED } nodeColor;
typedef struct Node_ {
struct Node_ *left; /* left child */
struct Node_ *right; /* right child */
struct Node_ *parent; /* parent */
nodeColor color; /* node color (BLACK, RED) */
T data; /* data stoRED in node */
} Node;
#define NIL &sentinel /* all leafs are sentinels */
Node sentinel = { NIL, NIL, 0, BLACK, 0};
Node *root = NIL; /* root of Red-Black tree */
void rotateLeft(Node *x) {
/**************************
* rotate node x to left *
**************************/
Node *y = x->right;
/* establish x->right link */
x->right = y->left;
if (y->left != NIL) y->left->parent = x;
/* establish y->parent link */
if (y != NIL) y->parent = x->parent;
if (x->parent) {
if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
} else {
root = y;
}
/* link x and y */
y->left = x;
if (x != NIL) x->parent = y;
}
void rotateRight(Node *x) {
/****************************
* rotate node x to right *
****************************/
Node *y = x->left;
/* establish x->left link */
x->left = y->right;
if (y->right != NIL) y->right->parent = x;
if (y != NIL) y->parent = x->parent;
if (x->parent) {
if (x == x->parent->right)
x->parent->right = y;
else
x->parent->left = y;
} else {
root = y;
}
y->right = x;
if (x != NIL) x->parent = y;
}
* maintain Red-Black tree balance *
* after inserting node x *
*************************************/
while (x != root && x->parent->color == RED) {
/* we have a violation */
if (x->parent == x->parent->parent->left) {
Node *y = x->parent->parent->right;
if (y->color == RED) {
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
} else {
if (x == x->parent->right) {
/* make x a left child */
x = x->parent;
rotateLeft(x);
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateRight(x->parent->parent);
}
} else {
Node *y = x->parent->parent->left;
if (y->color == RED) {
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
} else {
if (x == x->parent->left) {
x = x->parent;
rotateRight(x);
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateLeft(x->parent->parent);
}
}
}
root->color = BLACK;
}
Node *current, *parent, *x;
* allocate node for data and insert in tree *
***********************************************/
current = root;
parent = 0;
while (current != NIL) {
if (compEQ(data, current->data)) return (current);
parent = current;
current = compLT(data, current->data) ?
current->left : current->right;
}
if ((x = malloc (sizeof(*x))) == 0) {
printf ("insufficient memory (insertNode)\n");
exit(1);
}
x->data = data;
x->parent = parent;
x->left = NIL;
x->right = NIL;
x->color = RED;
if(parent) {
if(compLT(data, parent->data))
parent->left = x;
else
parent->right = x;
} else {
root = x;
}
Продолжение кода в лекции 11