 |
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк
[13]
/* 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;
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;
} else {
Node *w = x->parent->left; if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotateRight (x->parent);
w = x->parent->left;
(w->right->color == BLACK && w->left->color == BLACK) { w->color = RED; x = x->parent;
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;
w->color = x->parent->color; x->parent->color = BLACK; w->right->color = BLACK; rotateLeft (x->parent); x = root;