<
  • Главная
Статьи

Робота зі структурами даних в мовах Сі та Python: Частина 9. Червоно-чорні дерева

  1. Серія контенту:
  2. Цей контент є частиною серії: Робота зі структурами даних в мовах Сі та Python
  3. Червоно-чорні дерева
  4. Лістинг 1. Вихідний код вузлів, що використовуються в різних типах BST-дерев
  5. Лістинг 2. Структура, що описує червоно-чорне дерево
  6. Вставка вузла в червоно-чорне дерево
  7. Лістинг 3. Функція для визначення кольору вузла
  8. Лістинг 4. Функції для ротації вузлів в червоно-чорному дереві
  9. Лістинг 5. Функція для створення нового вузла
  10. Малюнок 1. Вставка вузла в червоно-чорне дерево.
  11. Лістинг 6. Функція для вставки вузла в червоно-чорне дерево
  12. Видалення вузла з червоно-чорного дерева
  13. Малюнок 2. Видалення вузла з червоно-чорного дерева
  14. Лістинг 7. Функція для видалення вузла з червоно-чорного дерева
  15. Порівняння AVL і червоно-чорних дерев
  16. Порівняння продуктивності AVL і червоно-чорних дерев
  17. Лістинг 8. Тестування продуктивності AVL-дерева
  18. Лістинг 9. Тестування продуктивності червоно-чорного дерева
  19. висновок
  20. Ресурси для скачування

Робота зі структурами даних в мовах Сі та Python

Серія контенту:

Цей контент є частиною # з серії # статей: Робота зі структурами даних в мовах Сі та Python

https://www.ibm.com/developerworks/ru/library/?series_title_by=**auto**

Слідкуйте за виходом нових статей цієї серії.

Цей контент є частиною серії: Робота зі структурами даних в мовах Сі та Python

Слідкуйте за виходом нових статей цієї серії.

У даній статті розглядається різновид бінарних пошукових дерев - червоно-чорні дерева, які також відносяться до збалансованим деревам. Такі дерева використовуються для вирішення найрізноманітніших завдань, наприклад, в одній з реалізацій планувальника ядра ОС Linux (completely fair scheduler) або для створення асоціативних масивів. У статті, як зазвичай, будуть розбиратися особливості реалізації червоно-чорних дерев і алгоритмів для роботи з ними.

Червоно-чорні дерева

Червоно-чорне дерево (англ. Red-black tree) - це ще одна форма збалансованого бінарного пошукового дерева. Вперше воно було представлено в 1972 році як ще один різновид збалансованого бінарного дерева. Час пошуку, вставки або видалення вузла для червоно-чорного дерева є логарифмічною функцією від числа вузлів.

Даний тип дерев відрізняється від інших реалізацій наступними властивостями:

  • кожен вузол асоціюється з певним кольором - червоним або чорним;
  • кореневої вузол може бути будь-якого кольору;
  • червоні вузли можуть мати тільки чорні дочірні вузли;
  • всі шляхи від вузла до будь-якого листа, розташованого нижче в дереві, містять одне і те ж кількість чорних вузлів.

Висота червоно-чорного дерева, що складається з N вузлів, лежить в діапазоні від довічного логарифма log (N + 1) до 2 * log (N + 1).

У лістингу 1 наведені структури на мові Сі, що описують вузли червоно-чорного і AVL-дерев.

Лістинг 1. Вихідний код вузлів, що використовуються в різних типах BST-дерев

/ * Структура, що описує вузол червоно-чорного дерева * / struct rb_node {int red; int data; struct rb_node * link [2]; }; / * Структура, що описує вузол AVL-дерева * / struct avl_node {struct avl_node * link [2]; int data; short bal; };

Як можна помітити, структура вузла AVL-дерева дуже схожа на структуру, що використовується для зберігання інформації про вузол червоно-чорного дерева. Тільки коефіцієнт збалансованості bal в червоно-чорному дереві замінений на змінну red, визначальну колір вузла (червоний або чорний). Але функції вставки / видалення вузлів для червоно-чорного дерева значно відрізняються від аналогічних операцій для AVL-дерева і повинні бути розглянуті окремо.

Також для роботи з червоно-чорним деревом потрібно допоміжна структура з лістингу 2.

Лістинг 2. Структура, що описує червоно-чорне дерево

struct rb_tree {struct rb_node * root; // покажчик на кореневий вузол int count; // кількість вузлів в дереві};

Вставка вузла в червоно-чорне дерево

При вставці нового вузла в кольорове дерево (інша назва червоно-чорного дерева) для нього спочатку встановлюється червоний колір. Потім для додається елемента виконується пошук батьківського вузла і перевірка його кольору. Якщо колір батька - чорний, то основний критерій кольорового дерева зберігається. Якщо ж батько - червоного кольору, то виконується ітеративна (нерекурсівние) балансування дерева. У гіршому випадку час вставки може досягти значення логарифма від числа вузлів в червоному дереві.

Для спрощення алгоритму передбачається, що листя (вузли, які не мають нащадків) мають чорний колір. У лістингу 3 наведено вихідний код функції для визначення кольору вузла.

Лістинг 3. Функція для визначення кольору вузла

int is_red (struct rb_node * node) {return node! = NULL && node-> red == 1; }

Для ротації вузлів в дереві будуть використовуватися функції, представлені в лістингу 4. Перша функція міняє місцями два вузла, друга функція виконує два таких обміну:

Лістинг 4. Функції для ротації вузлів в червоно-чорному дереві

/ * Функція для одноразового повороту вузла * / struct rb_node * rb_single (struct rb_node * root, int dir) {struct rb_node * save = root-> link [! Dir]; root-> link [! dir] = save-> link [dir]; save-> link [dir] = root; root-> red = 1; save-> red = 0; return save; } / * Функція для дворазового повороту вузла * / struct rb_node * rb_double (struct rb_node * root, int dir) {root-> link [! Dir] = rb_single (root-> link [! Dir],! Dir); return rb_single (root, dir); }

У лістингу 5 наведено вихідний код функції для створення нового вузла.

Лістинг 5. Функція для створення нового вузла

struct rb_node * make_node (int data) {struct rb_node * rn = malloc (sizeof * rn); if (rn! = NULL) {rn-> data = data; rn-> red = 1; / * -Ініціалізація червоним кольором * / rn-> link [0] = NULL; rn-> link [1] = NULL; } Return rn; }

При вставці вузла в кольорове дерево не потрібно вдаватися до рекурсії, так як це можна зробити за один прохід. У загальному випадку при вставці нового вузла можливі три варіанти.

  1. відбувається зміна кольору;
  2. потрібно зробити один поворот;
  3. потрібно зробити подвійний поворот.

Для цього в пам'яті крім поточного вузла потрібно зберігати ще три рівня дерева: «батька», «діда» і «прадіда» поточного вузла.

Малюнок 1. Вставка вузла в червоно-чорне дерево.
Робота зі структурами даних в мовах Сі та Python   Серія контенту:   Цей контент є частиною # з серії # статей: Робота зі структурами даних в мовах Сі та Python   https://www

На малюнку 1 в першому варіанті у який додається вузла (q) перевіряються дочірні вузли. Якщо дочірні вузли - червоного кольору, а додається вузол - чорного, то виконується зміна кольорів. Необхідно також перевірити на збіг кольору 2 вузла (другий і третій варіанти) - додається вузол (q) і його батька (p). Якщо вони обоє червоного кольору, то виконується одиночна або подвійна ротація.

Лістинг 6. Функція для вставки вузла в червоно-чорне дерево

int rb_insert (struct rb_tree * tree, int data) {/ * якщо елемент, виявляється першим - то нічого робити не потрібно * / if (tree-> root == NULL) {tree-> root = make_node (data); if (tree-> root == NULL) return 0; } Else {struct rb_node head = {0}; / * Тимчасовий корінь дерева * / struct rb_node * g, * t; / * Дідусь і батько * / struct rb_node * p, * q; / * Батько і итератор * / int dir = 0, last; / * Допоміжні змінні * / t = & head; g = p = NULL; q = t-> link [1] = tree-> root; / * Основний цикл проходу по дереву * / for (;;) {if (q == NULL) {/ * вставка Ноди * / p-> link [dir] = q = make_node (data); tree-> count ++; if (q == NULL) return 0; } Else if (is_red (q-> link [0]) && is_red (q-> link [1])) {/ * зміна кольору * / q-> red = 1; q-> link [0] -> red = 0; q-> link [1] -> red = 0; } / * Збіг 2-х червоних квітів * / if (is_red (q) && is_red (p)) {int dir2 = t-> link [1] == g; if (q == p-> link [last]) t-> link [dir2] = rb_single (g,! last); else t-> link [dir2] = rb_double (g,! last); } / * Такий вузол в дереві вже є - вихід з функції * / if (q-> data == data) {break; } Last = dir; dir = q-> data <data; if (g! = NULL) t = g; g = p, p = q; q = q-> link [dir]; } / * Оновити покажчик на корінь дерева * / tree-> root = head.link [1]; } / * Зробити корінь дерева чорним * / tree-> root-> red = 0; return 1; }

Видалення вузла з червоно-чорного дерева

При видаленні вузла з кольорового дерева колір батьківського вузла не змінюється. Видалення червоного вузла не тягне жодних наслідків, колізію може викликати тільки видалення вузла чорного кольору. Тому при видаленні чорного вузла для забезпечення цілісності дерева необхідно використовувати різні операції: просту зміну кольору (якщо це можливо) або одну або кілька ротацій. На малюнку 2 представлені 4 ситуації, можливих при видаленні чорного вузла.

Малюнок 2. Видалення вузла з червоно-чорного дерева

Якщо при видаленні чорного вузла, його «брат» (вузол, що знаходиться на тому ж рівні, що і видаляється) і всі їхні чотири нащадка мають чорний колір (це варіант I на малюнку 2), то виконується зміна кольору. Якщо «брат» видаляється вузла забарвлений в червоний колір, то проводиться ротація, зображена на варіанті II. Якщо видаляється вузол і його «брат» чорного кольору, а правий нащадок «брата» - червоного, то виконується подвійна ротація, зображена на варіанті 4. Якщо лівий нащадок «брата» червоного, то виконується одиночна ротація, як в п'ятому варіанті.

Лістинг 7. Функція для видалення вузла з червоно-чорного дерева

int br_remove (struct rb_tree * tree, int data) {if (tree-> root! = NULL) {struct rb_node head = {0}; / * Тимчасовий покажчик на корінь дерева * / struct rb_node * q, * p, * g; / * Допоміжні змінні * / struct rb_node * f = NULL; / * Вузол, що підлягає видаленню * / int dir = 1; / * Ініціалізація допоміжних змінних * / q = & head; g = p = NULL; q-> link [1] = tree-> root; / * Пошук і видалення * / while (q-> link [dir]! = NULL) {int last = dir; / * Збереження ієрархії вузлів в тимчасові змінні * / g = p, p = q; q = q-> link [dir]; dir = q-> data <data; / * Збереження знайденого вузла * / if (q-> data == data) f = q; if (! is_red (q) &&! is_red (q-> link [dir])) {if (is_red (q-> link [! dir])) p = p-> link [last] = rb_single (q, dir ); else if (! is_red (q-> link [! dir])) {struct rb_node * s = p-> link [! last]; if (s! = NULL) {if (! is_red (s-> link [! last]) &&! is_red (s-> link [last])) {/ * зміна кольору вузлів * / p-> red = 0; s-> red = 1; q-> red = 1; } Else {int dir2 = g-> link [1] == p; if (is_red (s-> link [last])) g-> link [dir2] = rb_double (p, last); else if (is_red (s-> link [! last])) g-> link [dir2] = rb_single (p, last); / * Коригування кольору вузлів * / q-> red = g-> link [dir2] -> red = 1; g-> link [dir2] -> link [0] -> red = 0; g-> link [dir2] -> link [1] -> red = 0; }}}}} / * Видалення знайденого вузла * / if (f! = NULL) {f-> data = q-> data; p-> link [p-> link [1] == q] = q-> link [q-> link [0] == NULL]; free (q); } / * Оновлення покажчика на корінь дерева * / tree-> root = head.link [1]; if (tree-> root! = NULL) tree-> root-> red = 0; } Return 1; }

Порівняння AVL і червоно-чорних дерев

У AVL і кольорових дерев є як загальні риси, так і відмінності. Наприклад, збігається час, потрібний для вставки видалення / вузлів в обидва типи дерев, яке в загальному випадку дорівнює бінарного логарифму від загального числа вузлів в дереві.

Для модифікації обох типів дерев слід дотримуватися додаткових ротацій. Але вставка в AVL-дерево вимагає не більше однієї ротації, а видалення вузла вже може зажадати великої кількості ротацій, в загальному випадку, двійковий логарифм від числа вузлів в дереві. Модифікація червоно-чорних дерев виконується легше, так як вставка вимагає не більше 2-х ротацій, а видалення - не більше трьох.

Також в разі, коли загальна кількість вузлів дерева] однаково, максимальна висота AVL- дерева завжди буде менше, ніж максимальна висота червоно-чорного дерева. Висота червоно-чорного дерева може перевищувати висоту AVL-дерева в 1.38 раз, тому для виконання пошуку по червоно-чорному дереву потрібно більше часу.

AVL-дерево має зберігати висоту в кожному вузлі, в той час як в вузлі червоно-чорного дерева зберігається тільки додатковий біт, який визначає колір вузла. Тому для зберігання червоно-чорного дерева потрібно менше пам'яті, ніж для AVL-дерева такого ж розміру.

Порівняння продуктивності AVL і червоно-чорних дерев

В цьому розділі порівнюється продуктивність вставки вузлів в AVL-дерево і червоно-чорне дерево. Як вже було сказано, обидва цих типу відносяться до самобалансірующіхся бінарним пошуковим деревам. Тому, якщо при вставці порушується критерій збалансованості (висота дерева стає неоптимальною, тобто перевищує мінімально можливе значення), то виконується автоматичне коректування дерева.

В ході порівняльного тестування в дерево додаються вузли, згенеровані випадковим чином, до тих пір, поки кількість вузлів в дереві не стане дорівнює п'яти мільйонам. Таке велике значення було вибрано спеціально, щоб наочно виявити різницю в швидкості роботи двох типів дерев, але для більш слабких або навпаки більш потужних процесорів можна використовувати інші значення.

Реалізація червоно-чорного дерева на мові Сі була представлена ​​в цій статті, а реалізацію AVL-дерева можна взяти з попередньої статті. У лістингу 8 представлена ​​програма для перевірки продуктивності AVL-дерева, а в лістингу 9 - ця ж програма, але вже для червоно-чорного дерева.

Лістинг 8. Тестування продуктивності AVL-дерева

int main () {struct avl_tree * my_tree = tree_create (); int res = 0; int i = 0; int rnd = 0; int count = 10000000; time_t start, time2; volatile long unsigned t; start = time (NULL); srand (time (NULL)); for (i = 0; i <count; i ++) {rnd = (rand ()% count); res = avl_insert (my_tree, rnd); if (my_tree-> count == 5000000) break; } Time2 = time (NULL); printf ( "\ n витрачено% f секунд. \ n", difftime (time2, start)); printf ( "\ n висота =% d кількість вузлів =% d \ n", height (my_tree-> root), my_tree-> count); return 0; }

Лістинг 9. Тестування продуктивності червоно-чорного дерева

int main () {int count = 10000000; int res = 0; int i = 0; int rnd = 0; struct rb_tree * my_tree = tree_create (); time_t start, time2; volatile long unsigned t; start = time (NULL); srand (time (NULL)); for (i = 0; i <count; i ++) {rnd = (rand ()% count); res = rb_insert (my_tree, rnd); if (my_tree-> count == 5000000) break; } Time2 = time (NULL); printf ( "\ n витрачено% f секунд. \ n", difftime (time2, start)); printf ( "\ n висота =% d кількість вузлів =% d \ n", height (my_tree-> root), my_tree-> count); return 0; }

В ході тестування були отримані наступні результати: одного й того ж комп'ютера знадобилося 16 секунд на вставку 5 мільйонів вузлів в AVL-дерево і 20 секунд на вставку такого ж кількості вузлів в червоно-чорне дерево. При цьому висота AVL-дерева виявилася рівною 27, а кольорового дерева - 28.

висновок

Таким чином, теорія була підтверджена практикою: висота AVL-дерева виявилася трохи менше висоти червоно-чорного дерева, що позитивно позначилося на швидкості вставки вузлів в AVL-дерево. Використовуючи представлені матеріали, пропонується виконати «зворотне» тестування на швидкість видалення вузлів з дерева, щоб перевірити твердження, що видалення з AVL-дерева вимагає більше часу, ніж видалення з кольорового дерева.

Ресурси для скачування

Схожі теми

  • Робота зі структурами даних в мовах Сі та Python. Частина 1 .
  • Робота зі структурами даних в мовах Сі та Python. Частина 2 .
  • Робота зі структурами даних в мовах Сі та Python. частина 3 .
  • Робота зі структурами даних в мовах Сі та Python. частина 4 .
  • Робота зі структурами даних в мовах Сі та Python. частина 5 .
  • Робота зі структурами даних в мовах Сі та Python. частина 6 .
  • Робота зі структурами даних в мовах Сі та Python. частина 7 .
  • Робота зі структурами даних в мовах Сі та Python. частина 8 .
  • Робота зі структурами даних в мовах Сі та Python. частина 9 .

Підпишіть мене на повідомлення до коментарів

Com/developerworks/ru/library/?


Новости
  • Виртуальный хостинг

    Виртуальный хостинг. Возможности сервера распределяются в равной мере между всеми... 
    Читать полностью

  • Редизайн сайта

    Редизайн сайта – это полное либо частичное обновление дизайна существующего сайта.... 
    Читать полностью

  • Консалтинг, услуги контент-менеджера

    Сопровождение любых интернет ресурсов;- Знание HTML и CSS- Поиск и обновление контента;-... 
    Читать полностью

  • Трафик из соцсетей

    Сравнительно дешевый способ по сравнению с поисковым и контекстным видами раскрутки... 
    Читать полностью

  • Поисковая оптимизация

    Поисковая оптимизация (англ. search engine optimization, SEO) — поднятие позиций сайта в результатах... 
    Читать полностью