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) {
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.