На этом шаге мы приведем несколько примеров создания и использования красно-черных деревьев.
Начиная с этого шага, приведем несколько демонстрационных примеров.
Пример 1. Демонстрация моделирования красно-черных деревьев. Автор программы: Niemann Thomas (1998).
Раскрыть/скрыть текст примера.
/* Демонстрация моделирования красно-черных деревьев. */ /* */ /* Автор программы: Niemann Thomas (1998) */ /* -------------------------------------------------- */ #include<stdio.h> #include<stdlib.h> #include<string.h> #include<stdarg.h> #define NIL &sentinel /* Описание листьев */ #define compLT(a,b) (a < b) #define compEQ(a,b) (a == b) /* -------------------------------------------------------- */ typedef int T; /* Тип значения, хранимого в узле дерева */ /* ----------------------------------------------------- */ /* Описание красно-чёрного дерева */ /* ----------------------------------------------------- */ typedef enum {BLACK,RED} nodeColor; typedef struct Node_ { struct Node_ *left; /* Левый сын */ struct Node_ *right; /* Правый сын */ struct Node_ *parent; /* Родитель */ nodeColor color; /* Цвет узла (BLACK,RED) */ T data; /* Значение, хранимое в узле */ } Node; Node sentinel={NIL,NIL,0,BLACK,0}; Node *root=NIL; /* Корень красно-чёрного дерева */ /* ----------------------------------------------------- */ void rotateLeft(Node *); void rotateRight(Node *); void insertFixup(Node *); Node *insertNode(T); void deleteFixup(Node *); void deleteNode (Node *); Node *findNode(T); void Vyvod(Node *,int); /* ---------------------- */ int main() { int a; struct Node_ *t; printf("Вводите ключ добавляемого узла: "); scanf("%d",&a); while (a) { insertNode(a); printf("\n"); Vyvod(root,0); printf("\n"); printf("Вводите ключ добавляемого узла: "); scanf("%d",&a); } printf("\n"); /* --------------------------------------------------- */ printf("Вводите ключ удаляемого узла: "); scanf("%d",&a); while (a) { if ((t=findNode(a))!=NULL) deleteNode(t); printf("\n"); Vyvod(root,0); printf("\n"); printf("Вводите ключ удаляемого узла: "); scanf("%d",&a); } return 0; } /* --------------------- */ void rotateLeft (Node *x) /* Левая ротация узла x */ /* --------------------- */ /* x y */ /* / \ / \ */ /* a y --> x c */ /* / \ / \ */ /* b c a b */ /* --------------------- */ { Node *y=x->right; /* ----------- */ x->right=y->left; if (y->left!=NIL) y->left->parent=x; 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; y->left=x; if (x!=NIL) x->parent=y; } /* ---------------------- */ void rotateRight (Node *x) /* Правая ротация узла x */ /* ---------------------- */ /* x y */ /* / \ / \ */ /* y c --> a x */ /* / \ / \ */ /* a b b c */ /* ---------------------- */ { Node *y=x->left; /* ----------- */ x->left=y->right; if (y->right!=NIL) y->right->parent=x; 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; y->right=x; if (x!=NIL) x->parent=y; } /* ---------------------- */ void insertFixup (Node *x) /* Поддержание баланса красно-чёрного дерева */ /* после включения узла x */ /* ----------------------------------------- */ { /* Проверка выполнения свойств красно-чёрного дерева */ while (x!=root&&x->parent->color==RED) { if (x->parent==x->parent->parent->left) { Node *y=x->parent->parent->right; if (y->color==RED) { /* "Дядя" окрашен в цвет RED */ x->parent->color=BLACK; y->color=BLACK; x->parent->parent->color=RED; x=x->parent->parent; } else { /* "Дядя" окрашен в цвет BLACK */ if (x==x->parent->right) { /* Сделаем x левым сыном */ x=x->parent; rotateLeft(x); } /* Перекраска и ротация */ x->parent->color=BLACK; x->parent->parent->color=RED; rotateRight(x->parent->parent); } } else { /* "Зеркальное" отражение предыдущего кода */ Node *y=x->parent->parent->left; if (y->color==RED) { /* "Дядя" окрашен в цвет RED */ x->parent->color=BLACK; y->color=BLACK; x->parent->parent->color=RED; x = x->parent->parent; } else { /* "Дядя" окрашен в цвет 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) /* Включение узла data в красно-чёрное дерево */ /* ------------------------------------------ */ { Node *current,*parent,*x; /* Поиск места прикрепления нового узла */ 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; } /* Выделение динамической памяти для нового узла */ if ((x=(Node *)malloc(sizeof(*x)))==0) { printf ("Недостаточно памяти для включения.\n"); exit(1); } x->data=data; x->parent=parent; x->left=NIL; x->right=NIL; x->color=RED; /* ------------------------------------- */ /* Включение узла в красно-чёрное дерево */ /* ------------------------------------- */ 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) /* Поддержание баланса красно-чёрного дерева */ /* после удаления узла 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) /* Удаление узла z из красно-чёрного дерева */ /* ---------------------------------------- */ { Node *x,*y; if (!z||z==NIL) return; if (z->left==NIL||z->right==NIL) { /* Узел y имеет NIL-узел в качестве сына */ y=z; } else { /* Поиск в дереве узла, имеющего NIL-узел */ /* в качестве сына */ y=z->right; while (y->left!=NIL) y=y->left; } /* Узел x является единственным сыном узла y */ if (y->left!=NIL) x=y->left; else x=y->right; /* Удаление y из родительской цепочки */ 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) /* Поиск узла, содержащего значение 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; } /* ------------------------ */ void Vyvod(Node *Tree,int l) /* Изображение красно-чёрного дерева Tree на экране */ /* дисплея (0 - узел чёрный, 1 - узел красный): */ /* ------------------------------------------------ */ { int i; if (Tree!=NIL) { Vyvod(Tree->right,l+1); for (i=1;i<=l;i++) printf(" "); printf("%d(%d)\n",Tree->data,Tree->color); Vyvod(Tree->left,l+1); } }
Пример 2. Пример реализации и использования красно-черных деревьев. Автор: Д.Е.Кадочников, ИСиТ (РГПУ им. А.И.Герцена, г.Санкт-Петербург), 2 курс (21.11.2012)
Раскрыть/скрыть текст примера.
Файл RB-Tree.h.
/* Заголовочный файл для абстрактного типа данных "Красно-чёрные деревья". ------------------------------------------------ Автор: Д.Е.Кадочников, ИСиТ, 2 курс (21.11.2012) */ #include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<conio.h> #include<time.h> #define RED 1 #define BLACK 0 #define NIL &Sentinel #define M 12 /* Построение красно-чёрного дерева, заданного указателем Tree на вершину дерева */ struct node *BuildTree(struct node *Tree); /* ---------------------------------------- */ /* Построение "случайного" красно-чёрного дерева, заданного указателем Tree на вершину дерева ---------------------------------------------- */ struct node *BuildTreeRand(struct node *Tree); /* ------------------------------------------- */ /* Поиск звена x в красно-чёрном дереве (заданном указате- лем *Tree на вершину дерева) с включением. P - указа- тель на "отца" */ void Search(int x,struct node **Tree,struct node *P); /* ---------------------------------------------------- */ /* Изображение бинарного дерева поиска (заданного указателем Tree) на экране дисплея. Параметр l при вызове равен 0 */ void PrintTree(struct node *Tree,int l); /* ------------------------------------------------------ */ /* Функция возвращает указатель на "дядю" звена, заданного указателем Tree */ struct node *Uncle(struct node *T); /* ------------------------------------------ */ /* Балансировка красно-чёрного дерева, необходимая при добавлении звена. Tree - указатель на новое звено */ void Balance(struct node *Tree); /* ------------------------------------------------ */ /* Левое вращение дерева в вершине, заданной указателем T */ void RotateLeft(struct node *T); /* -------------------------------------- */ /* Правое вращение дерева в вершине, заданной указателем T */ void RotateRight(struct node *T); /* --------------------------------------- */ /* Очистка бинарного дерева (заданного указателем *w на корень дерева), начиная с концевых вершин */ void CleanTree(struct node **w); /* -------------------------------------------- */ /* Включение звена k в красно-чёрное дерево, заданное указателем Tree */ struct node *Insert(struct node *Tree,int k); /* ----------------------------------------------- */ /* Удаление вершины k из бинарного дерева поиска, заданного указателем *Tree на корень дерева (возвращает указатель на корень) */ struct node *Delete(struct node *Tree,int k); /* ------------------------------------------- */ /* Удаление вершины k из бинарного дерева поиска, заданного указателем *Tree на корень дерева (не возвращает указатель на корень) */ void Delete_1(struct node **Tree,int k); /* ------------------------------------------- */ /* Впомогательная функция для функции Delete_1 */ void Delete_2(struct node **r,struct node **q); /* -------------------------------------------- */ /* Балансировка красно-чёрного дерева, необходимая при добавлении звена. Tree - указатель на новое звено */ void Balance1(struct node *Tree); /* ------------------------------------------------ */
Файл RB-Tree.c.
/* Файл реализации для абстрактного типа данных "Красно-чёрные деревья". ------------------------------------------------- Автор: Д.Е.Кадочников, ИСиТ, 2 курс (21.11.2012) */ struct node { int Key; /* Информационное поле */ int Count; /* Счётчик повторений элементов */ unsigned Color; /* Цвет узла (0 - чёрный, 1 - красный) */ struct node *Left; /* Указатель на левого "сына" */ struct node *Right; /* Указатель на правого "сына" */ struct node *Parent; /* Указатель на "отца" */ }; struct node Sentinel={0,0,0,NULL,NULL,NULL}; struct node *BuildTree(struct node *Tree) /* Построение красно-чёрного дерева, заданного указателем Tree на вершину дерева ------------------------------------------- */ { int el; Tree=NIL; printf("Вводите ключи вершин дерева: "); scanf("%d",&el); while (el) { Search(el,&Tree,NULL); scanf("%d",&el); while(Tree->Parent) Tree=Tree->Parent; } return Tree; } struct node *BuildTreeRand(struct node *Tree) /* Построение "случайного" красно-чёрного дерева, заданного указателем Tree на вершину дерева ---------------------------------------------- */ { int el=rand()%M; Tree=NIL; while (el) { Search(el,&Tree,NULL); el=rand()%M; while(Tree->Parent) Tree=Tree->Parent; } return Tree; } void Search(int x,struct node **Tree,struct node *P) /* Поиск звена x в красно-чёрном дереве (заданном указате- лем *Tree на вершину дерева) с включением. P - указа- тель на "отца" ------------------------------------------------------- */ { if (*Tree==NIL || !*Tree) { *Tree=(struct node *) calloc(sizeof(struct node),1); (*Tree)->Key=x; (*Tree)->Count=1; (*Tree)->Left=NIL; (*Tree)->Right=NIL; (*Tree)->Parent=P; (*Tree)->Color=RED; Balance(*Tree); } else if (x<(*Tree)->Key) Search(x,&((*Tree)->Left),*Tree); else if (x>(*Tree)->Key) Search(x,&((*Tree)->Right),*Tree); else (*Tree)->Count+=1; } struct node *Insert(struct node *Tree,int k) /* Включение звена k в красно-чёрное дерево, заданное указателем Tree -------------------------------------------------- */ { Search(k,&Tree,NULL); while(Tree->Parent) Tree=Tree->Parent; return Tree; } void PrintTree(struct node *Tree,int l) /* Изображение бинарного дерева поиска, заданного указателем Tree, на экране дисплея. Параметр l при вызове равен 0 --------------------------------------------------------- */ { int i; if (Tree!=NIL) { PrintTree(Tree->Right,l+1); for (i=1;i<=l;i++) printf(" "); printf("%d",Tree->Key); if(Tree->Color) printf("(R)\n"); else printf("(B)\n"); PrintTree(Tree->Left,l+1); } } struct node *Uncle(struct node *T) /* Функция возвращает указатель на "дядю" звена, заданного указателем T --------------------------------------------- */ { if (T->Parent && T->Parent->Parent) { if (T->Parent==T->Parent->Parent->Left) return T->Parent->Parent->Right; else return T->Parent->Parent->Left; } return NULL; } void Balance(struct node *Tree) /* Балансировка красно-чёрного дерева, необходимая при добавлении звена. Tree - указатель на новое звено --------------------------------------------------- */ { struct node *grand,*unc; if(!Tree->Parent) Tree->Color=BLACK; else { grand=Tree->Parent->Parent; unc=Uncle(Tree); if(Tree->Parent->Color) { if(unc && unc->Color && Tree->Parent->Color) { Tree->Parent->Color=BLACK; unc->Color=BLACK; grand->Color=RED; Balance(grand); } else { if((Tree==Tree->Parent->Right) &&(Tree->Parent==grand->Left)) { RotateLeft(Tree->Parent); Tree=Tree->Left; grand=Tree->Parent->Parent; unc=Uncle(Tree); } else if((Tree==Tree->Parent->Left) &&(Tree->Parent==grand->Right)) { RotateRight(Tree->Parent); Tree=Tree->Right; grand=Tree->Parent->Parent; unc=Uncle(Tree); } Tree->Parent->Color=BLACK; grand->Color=RED; if((Tree==Tree->Parent->Left)&&(Tree->Parent==grand->Left)) RotateRight(grand); else RotateLeft(grand); } } } } void RotateLeft(struct node *T) /* Левое вращение дерева в вершине, заданной указателем T ----------------------------------------- */ { if(T && T->Right!=NIL) { if(T->Parent) { if(T==T->Parent->Right) T->Parent->Right=T->Right; else T->Parent->Left=T->Right; } T->Right->Parent=T->Parent; T->Parent=T->Right; T->Right=T->Parent->Left; if(T->Right!=NIL) T->Right->Parent=T; T->Parent->Left=T; } } void RotateRight(struct node *T) /* Правое вращение дерева в вершине, заданной указателем T ----------------------------------------- */ { if(T && T->Left!=NIL) { if(T->Parent) { if(T==T->Parent->Right) T->Parent->Right=T->Left; else T->Parent->Left=T->Left; } T->Left->Parent=T->Parent; T->Parent=T->Left; T->Left=T->Parent->Right; if(T->Left!=NIL) T->Left->Parent=T; T->Parent->Right=T; } } void CleanTree(struct node **w) /* Очистка дерева (заданного указателем *w на корень дерева), начиная с концевых вершин ------------------------------------------- */ { if (*w!=NIL) { CleanTree(&((*w)->Left)); CleanTree(&((*w)->Right)); free(*w); } } struct node *Delete(struct node *Tree,int k) /* Удаление вершины k из бинарного дерева поиска, заданного указателем *Tree на корень дерева (возвращает указатель на корень) ---------------------------------------------- */ { Delete_1(&Tree,k); while(Tree->Parent) Tree=Tree->Parent; return Tree; } void Delete_1(struct node **Tree,int k) /* Удаление вершины k из бинарного дерева поиска, заданного указателем *Tree на корень дерева (не возвращает указатель на корень) ---------------------------------------------- */ { struct node *q; if (*Tree==NIL) printf("Звено не найдено.\n"); else if (k<(*Tree)->Key) Delete_1(&((*Tree)->Left),k); else if (k>(*Tree)->Key) Delete_1(&((*Tree)->Right),k); else { q=*Tree; if (q->Right==NIL) { q->Left->Parent=(*Tree)->Parent; if(!(*Tree)->Color) { *Tree=q->Left; if(q->Left->Color) q->Left->Color=BLACK; else if(!q->Left->Color) Balance1(*Tree); } else *Tree=q->Left; free(q); } else if (q->Left==NIL) { q->Right->Parent=(*Tree)->Parent; if(!(*Tree)->Color) { *Tree=q->Right; if(q->Right->Color) q->Right->Color=BLACK; else if(!q->Right->Color) Balance1(*Tree); } else *Tree=q->Right; free(q); } else Delete_2(&(q->Left),&q); } } void Delete_2(struct node **r,struct node **q) /* Впомогательная функция для функции Delete_1 ----------------------------------------------- */ { struct node *s; if ((*r)->Right==NIL) { (*q)->Key=(*r)->Key; (*q)->Count=(*r)->Count; *q=*r; s=*r; *r=(*r)->Left; Delete_1(&s,s->Key); } else Delete_2(&((*r)->Right),q); } void Balance1(struct node *Tree) /* Балансировка красно-чёрного дерева, необходимая при удалении звена. Tree - указатель на новое звено --------------------------------------------------- */ { struct node *bro; if(Tree->Parent) { if (Tree==Tree->Parent->Left) bro=Tree->Parent->Right; else bro=Tree->Parent->Left; if(bro->Color) { bro->Parent->Color=RED; bro->Color=BLACK; if(Tree==Tree->Parent->Left) { RotateLeft(Tree->Parent); bro=Tree->Parent->Right; } else { RotateRight(Tree->Parent); bro=Tree->Parent->Left; } } if(!Tree->Parent->Color && !bro->Color && !bro->Left->Color && !bro->Right->Color) { bro->Color=RED; Balance1(Tree->Parent); } else { if(Tree->Parent->Color && !bro->Color && !bro->Left->Color && !bro->Right->Color) { bro->Color=RED; Tree->Parent->Color=BLACK; } else { if(!bro->Color) { if(Tree==Tree->Parent->Left && bro->Left->Color && !bro->Right->Color) { bro->Color=RED; bro->Left->Color=BLACK; RotateRight(bro); bro=Tree->Parent->Right; } else if(Tree==Tree->Parent->Right && bro->Right->Color && !bro->Left->Color) { bro->Color=RED; bro->Right->Color=BLACK; RotateLeft(bro); bro=Tree->Parent->Left; } bro->Color=Tree->Parent->Color; Tree->Parent->Color=BLACK; if(Tree==Tree->Parent->Left) { bro->Right->Color=BLACK; RotateLeft(Tree->Parent); } else { bro->Left->Color=BLACK; RotateRight(Tree->Parent); } } } } } }
Демонстрация построения красно-чёрного дерева и очистки динамической памяти.
/* Демонстрация построение красно-чёрного дерева и очистки динамической памяти --------------------------------------------- */ #include"RB-Tree.h" #include"RB-Tree.c" int main() { struct node *Tree; int n,k,a; /* ---- */ clrscr(); printf("\nСвободное место в 'куче': %u\n",coreleft()); srand(time(NULL)); Tree=BuildTreeRand(Tree); do { PrintTree(Tree,0); printf("\n0 - выход, 1 - добавление, 2 - удаление\n"); scanf("%d",&n); switch (n) { case 1: printf("Введите ключ добавляемой вершины: "); scanf("%d",&k); Tree=Insert(Tree,k); printf("\n"); break; case 2: printf("Введите ключ удаляемой вершины: "); scanf("%d",&k); Tree=Delete(Tree,k); printf("\n"); break; } } while (n); CleanTree(&Tree); printf("\nСвободное место в 'куче': %u\n",coreleft()); getch(); return 0; }
Нахождение количества красных и чёрных вершин, учитывая фиктивные листы.
/* Нахождение количества красных и чёрных вершин, учитывая фиктивные листы ------------------------------------------------- Автор: Кадочников Д.Е., ИСиТ, 2 курс (26.12.2012) */ #include"RB-Tree.h" #include"RB-Tree.c" void RB(struct node *w,int *b,int *r); int main() { struct node *Tree; int b=0,r=0; /* ------------ */ srand(time(NULL)); Tree=BuildTreeRand(Tree); PrintTree(Tree,0); RB(Tree,&b,&r); printf("\nBlack: %d Red: %d\n",b,r); printf("--------------------------\n"); getch(); return 0; } /* --------------------------------- */ void RB(struct node *w,int *b,int *r) { if (w&&w!=NIL) { if(w->Color) (*r)++; else (*b)++; RB(w->Left,b,r); RB(w->Right,b,r); } else (*b)++; }
На следующем шаге мы продолжим приводить демонстрационные примеры.
