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

            current->left : current->right;

    }

    /* setup new node */

    if ((x = malloc (sizeof(*x))) == 0) {

        fprintf (stderr, "insufficient memory (insertNode)\n");

        exit(1);

    }

    x->data = data;

    x->parent = parent;

    x->left = NULL;

    x->right = NULL;

    /* insert x in tree */

    if(parent)

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

            parent->left = x;

        else

            parent->right = x;

    else

        root = x;

    return(x);

}

void deleteNode(Node *z) {

    Node *x, *y;

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

    *  delete node z from tree  *

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

    /* y will be removed from the parent chain */

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

    /* find tree successor */

    if (z->left == NULL || z->right == NULL)

        y = z;

    else {

        y = z->right;

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

    }

    /* x is y's only child */

    if (y->left != NULL)

        x = y->left;

    else

        x = y->right;

    /* remove y from the parent chain */

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

    if (y->parent)

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

            y->parent->left = x;

        else

            y->parent->right = x;

    else

        root = x;

    /* y is the node we're removing */

    /* z is the data we're removing */

    /* if z and y are not the same, replace z with y. */

    if (y != z) {

        y->left = z->left;

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

        y->right = z->right;

        if (y->right) y->right->parent = y;

        y->parent = z->parent;

        if (z->parent)

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

                z->parent->left = y;

            else

                z->parent->right = y;

        else

            root = y;

        free (z);

    } else {

        free (y);

    }

}

Node *findNode(T data) {

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

    *  find node containing data  *

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

    Node *current = root;

    while(current != NULL)

        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)

/* 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 */