Двійкові дерева пошуку » Українські реферати

ПЕРЕЛІК ДИСЦИПЛІН:

Бесплатные рефераты

Двійкові дерева пошуку

Інформатика, програмування

Двійкові дерева пошуку
Роман Акопов

Визначення Двійкові дерева Пошуку (Binary Search Tree, BST)
Бінарне дерево пошуку (ДДП) називають дерево, все вершини якого впорядковані, кожна вершина має не більше двох нащадків (назвемо їх лівим і правим), і всі вершини, окрім кореня, мають батьків. Вершини, які не мають нащадків, називаються листами. Мається на увазі, що кожній вершині відповідає елемент або декілька елементів, що мають певні ключові значення, що далі іменуються просто ключами. Зазвичай одній вершині відповідає один елемент, тому дані терміни можна без втрати сенсу вважати синонімами, хоч і треба пам'ятати, що в деяких реалізаціях це не так. У наведених алгоритмах вважається, що однією вершині відповідає тільки один елемент. Тому ми будемо використовувати поняття ключа вершини і даних вершини, маючи на увазі ключ і дані відповідного вершині елементу. Ми так ж будемо розуміти під вставкою вершини додавання вершини з вказаним значенням елемента і присвоєння вказівниками на батька та нащадків коректних значень. Саме ключ використовується в усіх операціях порівняння елементів. Елемент може також містити асоційовані з ключем дані. На практиці як ключ може використовуватися частина даних елемента. Ключ також може зберігатися як окреме значення. ДДП дозволяє виконувати наступні основні операції:

Пошук вершини по ключу.
Визначення вершин з мінімальним і максимальним значенням ключа.
Перехід до попередньої або наступної вершини, у порядку, який визначається ключами.
Вставка вершини.
Видалення вершини.
Двійкове дерево може бути логічно розбито на рівні. Корінь дерева є нульовим рівнем, нащадки кореня - першим рівнем, їх нащадки - другий, і т.д. Глибина дерева це його максимальний рівень. Поняття глибини також може бути описане в термінах шляху, тобто глибина дерева є довжина найдовшого шляху від кореня до листа, якщо слідувати від батьківської вершини до нащадка. Кожну вершину дерева можна розглядати як корінь піддереві, яке визначається даною вершиною і всіма нащадками цієї вершини, як прямими, так і непрямими. Тому про дерево можна говорити як про рекурсивної структурі. Ефективність пошуку по дереву безпосередньо пов'язана з його збалансованістю, тобто з максимальною різницею між глибиною лівого і правого піддереві серед всіх вершин. Є два крайніх випадки -- збалансоване бінарне дерево (де кожен рівень має повний набір вершин) і виродження дерево, де на кожен рівень припадає по одній вершині. Вироджені дерево еквівалентно пов'язаному списку. Час виконання всіх основних операцій по глибині дерева. Таким чином, швидкісні характеристики пошуку в ДДП можуть варіюватися від O (log2N) у разі закінченого дерева до O (N) - у разі виродженого.
ДДП може бути використане для реалізації таких абстракцій, як сортувати список, словник (набір відповідностей "ключ-значення"), черга з пріоритетами і так далі.
При реалізації дерева крім значення ключа (key) і даних також зберігаються три покажчика: на батька (net), лівого (left) і правого (right) нащадків. Якщо з батьків або нащадка немає, то покажчик зберігає нульове (NULL, NIL) значення.
Властивість впорядкованості двійкового дерева пошуку
Якщо x - це довільна вершина в ДДП, а вершина y знаходиться в лівому піддереві вершини x, то y.key <= x.key. Якщо x - це довільна вершина ДДП, а вершина y знаходиться в правому піддереві вершини x, то y.key> = x.key. З властивості випливає, що якщо y.key == x.key, то вершина y може знаходитися як в лівому, так і в правому піддереві щодо вершини x.
Необхідно пам'ятати, що за наявності декількох вершин з однаковими значеннями ключа деякі алгоритми не будуть працювати правильно. Наприклад, алгоритм пошуку буде завжди повертати покажчик тільки на одну вершину. Цю проблему можна вирішити, зберігаючи елементи з однаковими ключами в одній і тій самій вершині у вигляді списку. У такому випадку ми будемо зберігати в одній вершині кілька елементів, але даний випадок у статті не розглядається.
Це двійкове дерево пошуку:

Малюнок 1.
А це немає:

Малюнок 2.

Способи обходу ДДП
Є три способи обходу: Прямий (preorder), Поперечний (inorder), Зворотний (postorder).
Прямий обхід: спочатку обходиться ця вершина, ліве піддерево даної вершини, потім праве піддерево даної вершини.
Поперечний обхід: спочатку обходиться ліве піддерево даної вершини, потім ця вершина, потім праве піддерево даної вершини. Вершини при цьому будуть слідувати в неубивающем (по ключах key) порядку.
Зворотній обхід: спочатку обходиться ліве піддерево даної вершини, потім праве, потім ця вершина.
На малюнку 3 порядок обходу вершин вказаний номерами, при цьому передбачається, що самі вершини розташовані так, що утворюють ДДП.

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

Пошук вершини в ДДП
Ідея пошуку проста. Алгоритм пошуку в ДДП за своєю природі рекурсівен. При його описі простіше за все використовувати поняття піддереві. Пошук починається з кореня дерева, який приймається за корінь поточного піддереві, і його ключ порівнюється з шуканим. Якщо вони рівні, то, очевидно, пошук закінчений. Якщо ключ, який ми шукаємо, виявився більшим від поточного, то, очевидно, що потрібна вершина знаходиться в правому піддереві, інакше - у лівому. Далі ця операція повторюється для правого або лівого піддереві. В умовному коді це можна описати так:
Як розширення:
TreeSearch (node, key)
Begin
// Якщо вершина дорівнює NIL, то нічого в ній   шукати. Так само і повертаємо.
// Це потрібно для пошуку по не існуючим   нащадкам
If (node == NIL) Then
Return node;
// Якщо знайшли, то повертаємо вказівник на знайдену вершину.
If (node.key == key) Then
Return node;
// Якщо ключ знайденої вершини більше того, який ми шукаємо
If (node.key> key) Then
// То шукати в лівому піддереві
Return TreeSearch (node.left, key);
Else
// Інакше в правому піддереві
Return   TreeSearch (node.right, key);
End
ПРИМІТКА
У доданому вихідному   коді, написаному на Паскаль-подібному мовою, всі параметри передаються за значенням.   nodeParent, nodeTemp і node - це покажчики на вершини, а Tree - саме дерево,   що має поле root, покажчик на корінь дерева.
Ітеративний:
TreeSearch (node, key)
Begin
// Поки ще є вершини серед яких   можна шукати
// (ми переглядаємо не всі, але декілька) і   поки ми не знайшли
While (node! = NIL) and (node.key! = key) Do
Begin
// Якщо ключ найденногй вершини більше   того який ми шукаємо
If (node.key> key) Then
node = node.left;// То шукати в лівому   піддереві
Else
node = node.right;// А інакше в правому   піддереві
End
Return node;// Повернути знайдене
End
Пошук вершини з мінімальним і максимальним значенням ключа
Вершини з мінімальним і максимальним значенням ключа можна знайти, якщо пройтися лівим (правим) вказівниками від кореня (поки не досягнемо NIL). Повертає значення - це вказівник на вершину з мінімальним (максимальним) значенням ключа.
TreeMinimum (node)
Begin
While (node.left! = NIL) Do// Поки є лівий нащадок
Node = node.left;// Перейти до нього
Return node;
End
TreeMaximum (node)
Begin
While (node.right! = NIL) Do   //Поки є правий нащадок
node = node.right;// Перейти до нього
Return node;
End
Знаходження наступної і попередньої вершини в ДДП
Щоб знайти попередню і наступну вершину, треба знову згадати властивість впорядкованості. Розглянемо це на прикладі функції TreeNext. Вона враховує два випадки. Якщо праве піддерево не порожньо, то вершина з правого піддереві з мінімальним значенням ключа і буде наступною. Якщо ж праве піддерево пусто, тоді ми йдемо вгору, поки не знайдемо вершину, що є лівим нащадком свого батька. Цей батько (якщо він є) і буде наступною вершиною. Повертає значення - це вказівник на вершину з наступним (попереднім) значення ключа або NIL, якщо такої вершини немає.
TreeNext (node)
Begin
// Якщо праве піддерево не порожньо, то   повернути
// вершину з мінімальним значенням ключа із   правого піддереві
If (node.right! = NIL) Then
Return   TreeMinimum (node.right);
nodeParent = node.nodeParent;
// перебирати батьків, поки не знайдена   вершина,
// що є лівим нащадком свого   батьків
// або поки не закінчаться батьки.
While (nodeParent! = NIL) and (node ==   nodeParent.right) Do
Begin
node = nodeParent;
nodeParent =   nodeParent.nodeParent;
End
// Повернути батька вершини, що є   лівим нащадком свого батька
Return nodeParent;
End
TreePrevious (node)
Begin
If (node.left! = NIL) Then
// Якщо ліве піддерево не порожньо, то повернути
// вершину з лівого піддереві з   максимальним значенням ключа
Return   TreeMaximum (node.left);
nodeParent = node.nodeParent;
// перебирати батьків, поки не знайдемо вершину, що є
// правим нащадком свого батька або поки   не закінчаться батьки
While (nodeParent! = NIL) and (node ==   nodeParent.left) Do
Begin
node = nodeParent;
nodeParent =   nodeParent.nodeParent;
End
// Повернути батька вершини є   його правим нащадком
Return nodeParent;
End
Додавання вершини
Додавання вершини в ДДП пов'язане з деякими проблемами. Після додавання ДДП повинен зберегти властивість впорядкованості, а це означає, що вершину, куди потрапило додавати не можна. Тому, перш ніж вставляти вершину, необхідно підібрати для неї відповідне місце, то є таке місце, після вставки в яке, дерево збереже свою властивість впорядкованості. Кажучи іншими словами, нам потрібно місце після вершини з найбільшим ключем з всіх менших даного.
TreeInsert (Tree, node)
Begin
nodeParent = NIL;
nodeTemp = T.root;
// Поки ще є вершини які треба   переглянути, то
// є поки ми не дісталися до "листочків"   дерева
While (nodeTemp! = NIL) Do
Begin
nodeParent = nodeTemp;
// Якщо ключ вершини, яку ми хочемо вставити,
// менше ключа поточної вершини
If (node.key
nodeTemp = nodeTemp.left;// То він   повинен бути в його лівому піддереві
Else
nodeTemp = nodeTemp.right;// А інакше в   правом
End
node.nodeParent = nodeParent;
If (nodeParent == NIL) Then//   Якщо у лісі ще немає вершин
Tree.root = node;// То додати перше
Else
Begin
// Якщо ключ вершини, яку ми хочемо   вставити,
// менше ключа вершини, нащадком якої   повинна стати
// вставляється вершина
If (node.key <   nodeParent.key) Then
nodeParent.left = node;// То додати в дерево як   лівого нащадка
Else
nodeParent.right = node;// Інакше   додати в дерево як правого нащадка
End
End

Видалення вершини
Проблеми виникають і при видаленні. Нам необхідно зберегти властивість впорядкованості ДДП. При видаленні можливі три випадки: у видаляється вершини немає нащадків, у що видаляється вершини є один нащадок і у видаляється вершини два нащадка. Якщо нащадків немає, то вершину можна просто видалити. Якщо нащадок один, то віддаляється вершину можна "вирізати", вказавши її батькові як нащадка єдиного наявного нащадка видаляється вершини. Якщо ж нащадків два, потрібні додаткові дії. Потрібно знайти наступну за що видаляється (по порядку ключів) вершину, скопіювати її вміст (ключ і дані) у видаляємо вершину (вона тепер нікуди не віддаляється фізично, хоча логічно зникає) і видалити знайдену вершину (у неї не буде лівого нащадка). Спочатку функція TreeDelete шукає вершину, яку треба видалити, потім змінної nodeTemp присвоюється покажчик на існуючого нащадка видаляється вершини (або NIL, якщо нащадків немає). Далі вершина видаляється з дерева, при це окремо розглядаються випадки: коли нащадків немає і коли видаляється вершина - це корінь дерева. Повертає значення - це покажчик на віддалену вершину. На неї вже немає ніяких посилань на самому дереві, але вона все ще займає пам'ять. Момент її реального видалення залежить від використовуваних методів розподілу пам'яті.
TreeDelete (Tree, node)
Begin
// Якщо нащадків не більше одного (випадки 1   і 2)
If (node.left == NIL) or (node.right == NIL)   Then
del = node;// фізично видаляємо поточну вершину
Else
del = TreeNext (node);// Інакше наступну
If (del.left! = NIL) Then// Намагаємося знайти хоч одного нащадка
nodeTemp = del.left;
Else
nodeTemp = del.right;
// Якщо є, батьком нащадка робимо з батьків
// видаляється вершини (випадок 2)
If (nodeTemp! = NIL) Then
nodeTemp.nodeParent =   del.nodeParent;
// Якщо видаляємо корінь дерева, треба вказати новий корінь дерева
If (del.nodeParent == NIL) Then
Tree.root = nodeTemp;
Else
Begin
// Вказуємо батькові видаляється вершини   як нащадка
// нащадок видаляється вершини
If (del.nodeParent.left ==   del) Then
del.nodeParent.left =   nodeTemp;
Else
del.nodeParent.right =   nodeTemp;
End
If (del! = node) Then// Якщо випадок 3
Begin
node.key = del.key;// Копіювати ключ
(копіювання додаткових даних)
End
Return del;
End

NIL, NULL і маленькі хитрощі
Нерідко алгоритми, просто виглядають на папері, стають нагромадженням суцільних конструкцій if в реальній програмі. Чому? Відповідь очевидна: багато алгоритми для роботи з деревами припускають, що (NIL). Parent == (NIL). Left == (NIL). Right == NIL. Ніби все ясно і навіть логічно, але ж у багатьох мовах програмування NIL/NULL - це нуль. А звернення за нульовим адреси пам'яті загрожує нехорошими речами. Що ж робити? Адже мало того, що всі ці if гальмують програму, в них легко заплутатися! Рішення просто: ми не будемо використовувати NIL! Дійсно, алгоритмами абсолютно все одно, яке чисельне значення має NIL, головне, щоб адреса будь-якої реальної вершини в дереві не був йому рівний. Тому замість NIL ми будемо скористатись адресою змінної, проініціалізувати особливим чином. Я покажу це на мові С + +, але думаю, цей приклад можна буде перевести і на інші мови, хоча там, швидше за все, немає шаблонів, і доведеться пожертвувати тіпобезопасностью.
template class CTreeBase
(
protected:
CTree * lpCParent;
CTree * lpCLeft;
CTree * lpCRight;
public:
CTreeBase (CTreeBase *   lpCParentInit, CTreeBase * lpCLeftInit,
CTreeBase * lpCRightInit)
(
lpCParent = (CTree   ) lpCParentInit;
lpCLeft = (CTree ) lpCLeftInit;
lpCRight = (CTree ) lpCRightInit;
)
);
/////////////////////////////////////
class CTree: public CTreeBase
(
private:
int data;
protected:
static CTreeBase   treeNil;
);
/////////////////////////////////////////////// /////////////
CTreeBase CTree:: treeNil (& treeNil, & treeNil,   & treeNil);
Тепер скрізь у класі CTree можна використовувати змінну treeNil. Переваги очевидні. Витративши якихось дванадцять (3 sizeof (CTree *)) байт пам'яті, ми спростили розробку і прискорили виконання програми.

Основна проблема використання ДДП
Основною проблемою використання ДДП є те, що методи вставки та видалення вершин, гарантуючи збереження властивості впорядкованості, абсолютно не сприяють оптимізації основних операцій над ДДП. Наприклад, якщо вставити в ДДП послідовність зростаючих або відбувають чисел, воно перетвориться, по суті, в двусвязний список, а основні операції будуть займати час, пропорційний кількості вершин, а не його логарифму.
Таким чином, для отримання продуктивності порядку O (log2N) потрібно, щоб дерево мало як можна більш високу збалансованість (тобто мало можливо меншу висоту). Зазвичай виділяються кілька типів збалансованості. Повна збалансованість, це коли для кожної вершини дерева кількості вершин у лівому та правому піддерев розрізняються не більше ніж на 1. На жаль, такої збалансованості важко досягти на практиці. Тому на практиці використовуються менш жорсткі види збалансованості. Наприклад, російськими математиками Г. М. Адельсон-Бєльським і Е. М. Ландіс були розроблені принципи АВЛ дерев. У АВЛ деревах для кожної вершини дерева глибини обох п?? ддеревьев розрізняються не більше ніж на 1. Ще одним "просунутим" видом дерев є так звані червоно-чорні дерева. АВЛ дерева забезпечують більш високу збалансованість дерева, але витрати на їх підтримку вище. Оскільки на практиці різниця в збалансованості між цими двома видами дерев не висока, найчастіше використовуються червоно-чорні дерева.
Красно - чорні дерева (Red-Black Tree , RB-Tree)
Отже, одним зі способів вирішення основної проблеми використання ДДП є червоно-чорні дерева. Червоно-чорні (назва історично пов'язано з гральними картами, оскільки з них легко робити прості моделі) дерева (КЧД) - це ДДП, кожна вершина яких зберігає ще одне додаткове логічне поле (color), що позначає колір: червоний або чорний. Фактично, в КЧД гарантується, що рівні будь-яких двох листів відрізняються не більше, ніж в два рази. Цього умови було достатньо, щоб забезпечити швидкісні характеристики пошуку, близькі до O (log2N). При вставці/заміни проводяться додаткові дії з балансування дерева, які не можуть не баритися роботу з деревом. При описі алгоритмів ми будемо вважати, що NIL - це покажчик на фіктивну вершину, і операції (NIL). Left, (NIL). Right, (NIL). Color мають сенс. Ми також будемо вважати, що кожна вершина має двох нащадків, і лише NIL не має нащадків. Таким чином, кожна вершина стає внутрішньою (що має нащадків, нехай і вигаданих), а листям будуть лише фіктивні вершини NIL.

Властивості КЧД
Кожна вершина може бути або червоною, або чорною. Безбарвних вершин, або вершин іншого кольору бути не може.
Кожен лист (NIL) має чорний колір.
Якщо вершина червона, то обидва її нащадка - чорні.
Всі шляхи від кореня до листів містять однакове число чорних вершин.
Приклад КЧД з урахуванням наших положень наведено на малюнку 4. Врахуйте, що вершина 9 могла бути й червона, але надалі ми будемо розглядати тільки ті дерева, у яких корінь чорний. Ми це зробимо для того, щоб нащадки кореня могли мати будь-який колір.

Малюнок 4.
Обертання
Операції вставки та видалення вершин у КЧД можуть порушувати властивості КЧД. Щоб відновити ці властивості, треба буде перефарбовувати деякі вершини і міняти структуру дерева. Для зміни структури використовуються операції, називані обертанням. Повертаючи КЧД його властивості, обертання так само відновлюють збалансованість дерева. Обертання бувають ліві і праві, їх суть показана на малюнку 5.

Малюнок 5.
Як видно, обертання, переміщаючи вершини, не порушують властивості впорядкованості.
У процедурі RBTLeftRotate передбачається, що node.right! = NIL. У процедурі RBTRightRotate передбачається, що node.left! = NIL.
RBTLeftRotate (Tree, node)
Begin
nodeTemp = node.right;
node.right = nodeTemp.left;
If (nodeTemp.left! = NIL) Then
nodeTemp.left.nodeParent =   node;
nodeTemp.nodeParent =   node.nodeParent;
If (node.nodeParent == NIL)   Then
Tree.root = nodeTemp;
Else
Begin
If (node ==   node.nodeParent.left) Then
node.nodeParent.left =   nodeTemp;
Else
node.nodeParent.right =   nodeTemp;
End
nodeTemp.left = node;
node.nodeParent = nodeTemp;
End
RBTRightRotate (Tree, node)
Begin
nodeTemp = node.left;
node.left = nodeTemp.right;
If (nodeTemp.right! = NIL)   Then
nodeTemp.right.nodeParent =   node;
nodeTemp.nodeParent =   node.nodeParent;
If (node.nodeParent == NIL)   Then
Tree.root = nodeTemp;
Else
Begin
If (node ==   node.nodeParent.right) Then
node.nodeParent.right =   nodeTemp;
Else
node.nodeParent.left =   nodeTemp;
End
nodeTemp.right = node;
node.nodeParent = nodeTemp;
End
Додавання вершини в КЧД
Щоб додати вершину в КЧД, ми застосовуємо процедуру TreeInsert для ДДП, фарбуємо вершину в червоний колір, а потім відновлюємо властивості КЧД. Для цього ми перефарбовувати деякі вершини і виробляємо обертання.
1 RBTInsert (Tree, node)
2 Begin
3 TreeInsert (Tree, node);
4 node.color = RED;
5 While (node! = Tree.root) and   (node.nodeParent.color == RED) Do
6 Begin
7 If (node.nodeParent == node.nodeParent.nodeParent.left)   Then
8 Begin
9 nodeTemp =   node.nodeParent.nodeParent.right;
10 If (nodeTemp.color ==   RED) Then
11 Begin
12 node.nodeParent.color   = BLACK;
13 nodeTemp.color =   BLACK;
14   node.nodeParent.nodeParent.color = RED;
15 node =   node.nodeParent.nodeParent;
16 End
17 Else
18 Begin
19 If (node ==   node.nodeParent.right) Then
20 Begin
21 node =   node.nodeParent;
22 RBTLeftRorate (Tree, node);
23 End
24 node.nodeParent.color   = BLACK;
25   node.nodeParent.nodeParent.color = RED;
26   RBTRightRotate (Tree, node.nodeParent.nodeParent);
27 End
28 End
29 Else
30 Begin
31 nodeTemp =   node.nodeParent.nodeParent.left;
32 If (nodeTemp.color ==   RED) Then
33 Begin
34 node.nodeParent.color   = BLACK;
35 nodeTemp.color =   BLACK;
36   node.nodeParent.nodeParent.color = RED;
37 node =   node.nodeParent.nodeParent;
38 End
39 Else
40 Begin
41 If (node ==   node.nodeParent.left) Then
42 Begin
43 node =   node.nodeParent;
44   RBTRightRorate (Tree, node);
45 End
46 node.nodeParent.color = BLACK;
47   node.nodeParent.nodeParent.color = RED;
48   RBTLeftRotate (Tree, node.nodeParent.nodeParent);
49 End
50 End
51 End
52 Tree.root.color = BLACK;
53 End
Функція RBTInsert не так складне, як здається на перший погляд. Розглянемо її докладніше. Після строк 3-4 виконуються всі властивості КЧД, крім, можливо, одного: у нової червоної вершини може бути червоний батько. Така ситуація (червона вершина має червоного батька) може зберегтися після будь-якого числа ітерацій циклу. Всередині циклу розглядаються 6 різних випадків, але три з них (рядки 8-28) симетричні трьом іншим (рядки 30-50), розходження лише в тому, чи є батько вершини node правим або лівим нащадком свого батька (випадки розділяються в рядку 7). Тому ми розглянемо докладно тільки перші три випадки (рядки 8-28). Припустимо, що у всіх розглянутих КЧД корінь чорний, і будемо підтримувати це властивість (рядок 52). Тому в рядку 5 node.nodeParent (червоного кольору) не може бути коренем, і node.nodeParent.nodeParent! = NIL. Операції всередині циклу починаються з знаходження nodeTemp, "дядька" node, то є вершини, що має того ж батька, що і node.nodeParent. Якщо nodeTemp - червона вершина, то має місце випадок 1, якщо чорна, то 2 або 3. У всіх випадках вершина node.nodeParent.nodeParent - Чорна, так як пара node, node.nodeParent була єдиним порушенням властивостей КЧД.
Випадок 1 (рядки 12-15 та 34-37) показаний на малюнку 6. Чи є вершина node правим або лівим нащадком свого батька, значення не має.

Малюнок 6.
Обидві вершини (node і nodeTemp) - червоні, а вершина node.nodeParent.nodeParent - чорна. Перефарбуємо node.nodeParent і nodeTemp в чорний колір, а node.nodeParent.nodeParent - в червоний. При цьому число чорних вершин на будь-якому шляху від кореня до листів залишається тим самим. Порушення властивостей КЧД можливо лише в одному місці: вершина node.nodeParent.nodeParent може мати червоного батька, тому треба продовжити виконання циклу, присвоївши node значення node.nodeParent.nodeParent.
У випадках 2 і 3 вершина nodeTemp - чорна. Розрізняються випадки, коли вершина node є правим або лівим нащадком свого батька. Якщо правим, то це випадок 2 (рядки 20-23 та 41-45). У цьому випадку здійснюється ліве обертання, яке зводить випадок 2 до випадку 3, коли node є лівим нащадком свого батька. Так як node і node.nodeParent - червоні, після обертання кількість чорних вершин на шляхах від кореня до листів залишається тим самим.

Малюнок 7.
Залишилося розглянути випадок 3: червона вершина node є лівим нащадком червоної вершини node.nodeParent, яка, в свою чергу, є лівим нащадком node.nodeParent.nodeParent, правим нащадком якої є nodeTemp. У цьому випадку досить провести праве обертання і перефарбувати дві вершини. Цикл скінчиться, так як вершина node.nodeParent буде після цього чорною.
Видалення вершини з КЧД
Видалення вершини трохи складніше додавання. Ми будемо вважати, що (NIL). color == BLACK, і будемо вважати операцію взяття кольору у покажчика, рівного NIL, допустимої операцією. Також ми будемо вважати допустимим присвоювання (NIL). nodeParent, і будемо вважати дане присвоювання має результат. Тобто при взятті значення (NIL). NodeParent ми отримаємо раніше записане значення. Функція RBTDelete подібна TreeDelete, але, видаливши вершину, вона викликає процедуру RTBDeleteFixUp для відновлення властивостей КЧД.
RBTDelete (Tree, node)
Begin
If (node.left == NIL) or   (node.right == NIL) Then
nodeParent = node;
Else
nodeParent = TreeNext (node);
If (nodeParent.left! = NIL)   Then
nodeTemp = nodeParent.left;
Else
nodeTemp = nodeParent.right;
nodeTemp.nodeParent =   nodeParent.nodeParent;
If (nodeTemp.nodeParent ==   NIL) Then
Tree.root = nodeTemp;
Else
Begin
If   (nodeParent.nodeParent.left == nodeParent) Then
nodeParent.nodeParent.left   = NodeTemp;
Else
  nodeParent.nodeParent.right = nodeTemp;
End
If (nodeParent! = node) Then
Begin
node.key = nodeParent.key;
node.color = nodeParent.color;
(копіювання додаткових даних)
End
If (nodeParent.color == BLACK)   Then
  RBTDeleteFixUp (Tree, nodeTemp);
Return nodeParent;
End
Розглянемо, як процедура RBTDeleteFixUp відновлює властивості КЧД. Очевидно, що якщо видалили червону вершину, то, оскільки обидва її нащадка чорні, червона вершина не стане батьком червоного нащадка. Якщо ж видалили чорну вершину, то як мінімум на одному зі шляхів від кореня до листів кількість чорних вершин зменшилася. До того ж червона вершина могла стати нащадком червоного з батьків.
1 RTBDeleteFixUp (Tree, node)
2 Begin
3 While (node! = Tree.root) and (node.color   == BLACK) Do
4 Begin
5 If (node == node.nodeParent.left)
6 Begin
7 nodeTemp = node.nodeParent.right;
8 If (nodeTemp.color == RED) Then
9 Begin
10 nodeTemp.color =   BLACK;
11   nodeTemp.nodeParent.color = RED;
12   RBTLeftRotate (Tree, node.nodeParent);
13 nodeTemp =   node.nodeParent.right;
14 End
15 If (nodeTemp.left.color   == BLACK) and (nodeTemp.right.color == BLACK) Then
16 Begin
17 nodeTemp.color = RED;
18 nodeTemp =   nodeTemp.nodeParent;
19 End
20 Else
21 Begin
22 If   (nodeTemp.right.color == BLACK) Then
23 Begin
24 nodeTemp.left.color   = BLACK;
25 nodeTemp.color =   RED;
26   RBTRightRotate (Tree, nodeTemp)
27 nodeTemp =   node.nodeParent.right;
28 End
29 nodeTemp.color =   node.nodeParent.color;
30 node.color.nodeParent   = BLACK;
31 nodeTemp.right.color   = BLACK;
32   RBTLeftRotate (Tree, node.nodeParent);
33 node = Tree.root;
34 End
35 End
36 Else
37 Begin
38 nodeTemp =   node.nodeParent.left;
39 If (nodeTemp.color == RED) Then
40 Begin
41 nodeTemp.color =   BLACK;
42   nodeTemp.nodeParent.color = RED;
43   RBTRightRotate (Tree, node.nodeParent);
44 nodeTemp =   node.nodeParent.left;
45 End
46 If (nodeTemp.right.color   == BLACK) and (nodeTemp.left.color == BLACK) Then
47 Begin
48 nodeTemp.color = RED;
49 nodeTemp =   nodeTemp.nodeParent;
50 End
51 Else
52 Begin
53 If   (nodeTemp.left.color == BLACK) Then
54 Begin
55   nodeTemp.right.color = BLACK;
56 nodeTemp.color =   RED;
57   RBTLeftRotate (Tree, nodeTemp)
58 nodeTemp =   node.nodeParent.left;
59 End
60 nodeTemp.color =   node.nodeParent.color;
61 node.color.nodeParent   = BLACK;
62 nodeTemp.left.color =   BLACK;
63   RBTRightRotate (Tree, node.nodeParent);
64 node = Tree.root;
65 End
66 End
67 End
68 node.color = BLACK;
69 End
Процедура RBTDeleteFixUp застосовується до дерева, яке має властивості КЧД, якщо врахувати додаткову одиницю чорноти у вершині node (вона тепер двічі чорна, це чисто логічне поняття, і воно ніде фактично не зберігається і логічного типу для зберігання кольору вам завжди буде достатньо) і перетворює його в даний КЧД.
Що таке двічі чорна вершина? Це визначення може заплутати. Формально вершина називається двічі чорною, щоб відбити той факт, що при підрахунку чорних вершин на шляху від кореня до листа ця вершина вважається за два чорних. Якщо чорна вершина була вилучена, її чорноту так просто викидати не можна. Вона на рахунку. Тому тимчасово чорноту віддаленої вершини передали вершині node. У завдання процедури RBTDeleteFixUp входить розподіл цієї зайвої чорноти. Вони або буде передана червоною вершині (і та стане чорною) або після перестановок інших чорних вершин (щоб змінити їх кількість на шляху від кореня до листів) буде просто викинути.
У циклі (рядки 3-67) дерево змінюється, і значення змінної node теж змінюється, але сформульоване властивість залишається вірним. Цикл завершується, якщо:
node вказує на червону вершину, тоді ми фарбуємо її в чорний колір (рядок 68).
node вказує на корінь дерева, тоді зайва чорнота може бути просто відсутній.
могло виявитися, що всередині тіла циклу вдається виконати кілька обертань і перефарбувати кілька вершин, так що двічі чорна вершина зникає. У цьому випадку присвоювання node = Tree.root (рядки 33 і 64) дозволяє вийти з циклу.
Всередині циклу node вказує на двічі чорну вершину, а nodeTemp - на її брата (іншу вершину з тим же батьком). Оскільки вершина node двічі чорна, nodeTemp не може бути NIL, оскільки в цьому випадку уздовж одного шляху від node.nodeParent було б більше чорних вершин, ніж уздовж іншого. Чотири можливих випадку показані на малюнку нижче. Зеленим і синім, помічені вершини, колір яких не грає ролі, тобто може бути як чорним, так і червоним, але зберігається в процесі перетворень.

Малюнок 8
Переконайтеся, що перетворення не порушують властивість 4 КЧД (пам'ятайте, що вершина node вважається за дві чорні, і що в піддереві a -- f з самого початку не рівну кількість чорних вершин).
Випадок 1 (рядки 9-14 та 40-45) має місце, коли вершина nodeTemp червона (в цьому випадку node.nodeParent чорна). Так як обидва нащадка вершини nodeTemp чорні ми можемо поміняти кольори nodeTemp і node.nodeParent і провести ліве обертання навколо node.nodeParent не порушуючи властивостей КЧД. Вершина node залишається двічі чорною, а її новий брат - чорним, так що ми звели справу до одного з випадків 2-4.
Випадок 2 (рядки 16-19 та 47-50). Вершина nodeTemp -- чорна, і обидва її нащадка теж чорні. У цьому випадку ми можемо зняти зайву чорноту з node (тепер вона одного разу чорна), перефарбувати nodeTemp, зробивши її червоною (обидва її нащадка чорні, так що це припустимо) і додати чорноту батькові node. Зауважимо, що якщо ми потрапили у випадок 2 з випадку 1, то вершина node.nodeParent - червона. Зробивши її чорної (додавання чорного до червоної вершині робить її чорною), ми завершимо цикл.
Випадок 3 (рядки 23 - 28 і 53 - 59) Вершина nodeTemp чорна, її лівий нащадок червоний, а правий чорний. Ми можемо поміняти кольори nodeTemp і її лівого нащадка і потім застосувати праве обертання так, що властивості КЧД будуть збережені. Новим братом node буде тепер чорна вершина з червоним правим нащадком, і випадок 3 зводиться до випадку чотири.
Випадок 4 (рядки 29 - 33 і 60 - 64) Вершина nodeTemp чорна, правий нащадок червоний. Змінюючи деякі кольору (не всі з них нам відомі, але це нам не заважає) і, виробляючи ліве обертання навколо node.nodeParent, ми можемо видалити зайву чорноту у node, не порушуючи властивостей КЧД. присвоювання node = Tree.root виводить нас з циклу.
Порівняльні характеристики швидкості роботи різних структур даних
Щоб усе сказане до цього не здавалося порожній базіканням, я як укладення наведу порівняльні характеристики швидкості роботи різних структур даних (дерев і масивів). Для вимірювання часу була використана функція WinAPI QueryPerfomanceCounter. Час перераховано в мікросекунди. У дужках наведено кінцева глибина дерева. Тестування проводилося на процесорі Intel Celeron Tualatin 1000MHz з 384Мб оперативної пам'яті. Як ключ використовувалося число типу int (32-х бітне ціле зі знаком), а в якості даних число типу float (4-х байтного речовий).
Кількість елементів
ДДП
КЧД
Постійно сортованого   масив
несортоване масив
Масив з постсортіровкой
1000
4943
(1000)
535
(17)
193
32
73
2000
20571
(2000)
1127
(19)
402
89
152
3000
65819
(3000)
1856
(20)
621
98
305
4000
82321
(4000)
2601
(21)
862
189
327
5000
126941
(5000)
3328
(22)
1153
192
461
6000
183554
(6000)
4184
(22)
1391
363
652
7000
255561
(7000)
4880
(23)
1641
452
789
8000
501360
(8000)
5479
(23)
1905
567
874
9000
1113230
(9000)
6253
(24)
2154
590
1059
10000
1871090
(10000)
7174
(24)
2419
662
1180
Таблиця 1. Додавання елементу (зростаючі ключі)
Кількість елементів
ДДП
КЧД
Постійно
сортованого масив
несортоване масив
Масив з постсортіровкой
1000
4243
108
136
1354
134
2000
19295
250
289
5401
286
3000
71271
391
448
25373
441
4000
79819
560
615
23861
607
5000
124468
759
787
38862
776
6000
180029
956
954
55303
941
7000
246745
1199
1165
75570
1111
8000
487187
1412
1307
98729
1330
9000
1062128
1906
1494
134470
1474
10000
1807235
2068
1719
154774
1688
Таблиця 2. Пошук елементу (зростаючі ключі).
Кількість елементів
ДДП
КЧД
Постійно сортованого   масив
несортоване масив
Масив з постсортіровкой
1000
308
419
2077
2047
2080
2000
639
876
13422
8046
8179
3000
1001
1372
25092
30902
18407
4000
1380
1831
32572
32473
32651
5000
1680
2286
50846
51001
50962
6000
2105
2891
73321
73114
73202
7000
2569
3514
99578
100059
99801
8000
3025
4384
129833
129897
130054
9000
3484
5033

Реферат Банк

Рефераты

Бесплатные рефераты

Все права защищены. Reff.net.ua - українські реферати !

DMCA.com Protection Status