Реализация

Ниже мы приводим коды, реализующие работу с красно-черными деревьями на Си. Операторы 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)

 /* Red-Black tree description */

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;

     /* establish y->parent link */

    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;

    }

     /* link x and y */

    y->right = x;

    if (x != NIL) x->parent = y;

}

 void insertFixup(Node *x) {

     /*************************************

    *  maintain Red-Black tree balance  *

    *  after inserting node x           *

    *************************************/

     /* check Red-Black properties */

    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) {

                  /* uncle is RED */

                x->parent->color = BLACK;

                y->color = BLACK;

                x->parent->parent->color = RED;

                x = x->parent->parent;

            } else {

                  /* uncle is BLACK */

                if (x == x->parent->right) {

                    /* make x a left child */

                    x = x->parent;

                    rotateLeft(x);

                }

                  /* recolor and rotate */

                x->parent->color = BLACK;

                x->parent->parent->color = RED;

                rotateRight(x->parent->parent);

            }

        } else {

             /* mirror image of above code */

            Node *y = x->parent->parent->left;

            if (y->color == RED) {

                  /* uncle is RED */

                x->parent->color = BLACK;

                y->color = BLACK;

                x->parent->parent->color = RED;

                x = x->parent->parent;

            } else {

                  /* uncle is BLACK */

                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 *insertNode(T data) {

    Node *current, *parent, *x;

     /***********************************************

    *  allocate node for data and insert in tree  *

    ***********************************************/

     /* find where node belongs */

    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;

    }

     /* setup new node */

    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;

     /* insert node in tree */

    if(parent) {

        if(compLT(data, parent->data))

            parent->left = x;

        else

            parent->right = x;

    } else {

        root = x;

    }

Продолжение кода в лекции 11