Ъюфћ фыџ ъ№рёэю-їх№эћѕ фх№хтќхт

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;

џџџ }

 

џџџ insertFixup(x);

џџџ return(x);

}

 

void deleteFixup(Node *x) {

 

џџ /*************************************

џџџ *џ maintain Red-Black tree balanceџ *

џџџ *џ after deleting node xџџџџџџџџџџџ *

џџџ *************************************/

 

џџџ while (x != root && x->color == BLACK) {

џџџџџџџ if (x == x->parent->left) {

џџџџџџџџџџџ Node *w = x->parent->right;

џџџџџџџџџџџ if (w->color == RED) {

џџџџџџџџџџџџџџџ w->color = BLACK;

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

џџџџџџџџџџџџџџџ rotateLeft (x->parent);

џ џџџџџџџџџџџџџџw = x->parent->right;

џџџџџџџџџџџ }

џџџџџџџџџџџ if (w->left->color == BLACK && w->right->color == BLACK) {

џџџџџџџџџџџџџџџ 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);

}


бюфх№црэшх №рчфхыр

---