Сортування й пошук: Рецептурний довідник, страница 17

                w->color = RED;

                x = x->parent;

            } else {

                if (w->right->color == BLACK) {

                    w->left->color = BLACK;

                    w->color = RED;

                    rotateRight (w);

                    w = x->parent->right;

                }

                w->color = x->parent->color;

                x->parent->color = BLACK;

                w->right->color = BLACK;

                rotateLeft (x->parent);

                x = root;

            }

        } else {

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

            if (w->color == RED) {

                w->color = BLACK;

                x->parent->color = RED;

                rotateRight (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;

                    rotateLeft (w);

                    w = x->parent->left;

                }

                w->color = x->parent->color;

                x->parent->color = BLACK;

                w->left->color = BLACK;

                rotateRight (x->parent);

                x = root;

            }

        }

    }

    x->color = BLACK;

}

void deleteNode(Node *z) {

    Node *x, *y;

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

    *  delete node z from tree  *

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

    if (!z || z == NIL) return;

    if (z->left == NIL || z->right == NIL) {

        /* y has a NIL node as a child */

        y = z;

    } else {

        /* find tree successor with a NIL node as a child */

        y = z->right;

        while (y->left != NIL) y = y->left;

    }

    /* x is y's only child */

    if (y->left != NIL)

        x = y->left;

    else

        x = y->right;

    /* remove y from the parent chain */

    x->parent = y->parent;

    if (y->parent)

        if (y == y->parent->left)

            y->parent->left = x;

        else

            y->parent->right = x;

    else

        root = x;

    if (y != z) z->data = y->data;

    if (y->color == BLACK)

        deleteFixup (x);

    free (y);

}

Node *findNode(T data) {

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

    *  find node containing data  *

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

    Node *current = root;

    while(current != NIL)

        if(compEQ(data, current->data))

            return (current);

        else

            current = compLT (data, current->data) ?

                current->left : current->right;

    return(0);

}

typedef int T;                        /* type of item to be sorted */

#define compLT(a,b) (a < b)

#define compEQ(a,b) (a == b)

/*

 * levels range from (0 .. MAXLEVEL)

 */

#define MAXLEVEL 15

typedef struct Node_ {

    T data;                     /* user's data */

    struct Node_ *forward[1];   /* skip list forward pointer */

} Node;

typedef struct {

    Node *hdr;                  /* list Header */

    int listLevel;              /* current level of list */

} SkipList;

SkipList list;                  /* skip list information */

#define NIL list.hdr

Node *insertNode(T data) {

    int i, newLevel;

    Node *update[MAXLEVEL+1];

    Node *x;

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

    *  allocate node for data and insert in list  *

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

    /* find where data belongs */

    x = list.hdr;

    for (i = list.listLevel; i >= 0; i--) {

        while (x->forward[i] != NIL

          && compLT(x->forward[i]->data, data))

            x = x->forward[i];

        update[i] = x;

    }