1. Конструктори і деструктори
2. Пошук
3. симетричний обхід
4. включення елементів
5. видалення елементів

Двійкові дерева представляють ефективний спосіб пошуку. Двійкове дерево являє собою структуровану колекцію вузлів. Колекція може бути порожньою і в цьому випадку ми маємо порожній двоичное дерево. Якщо колекція непорожньої, то вона поділяється на три роздільних колекція сайтів: кореневий вузол n (або просто корінь), двійкове дерево, зване лівим піддерево для n, і бінарне дерево, зване правим піддерево для n. На рис. 1а вузол, позначений буквою А, є кореневим, вузол В називається лівим нащадком А і є коренем лівого піддерева А, вузол З називається правим нащадком А і є коренем правого піддерева А.

Мал. 1: Двійкове дерево з показаними зовнішніми узлламі (а) і без них (б)

Двійкове дерево на рис. 1а складається з чотирьох внутрішніх вузлів (позначених на рис. Кружками) і п'яти зовнішніх (кінцевих) вузлів (позначені квадратами). Розмір двійкового дерева визначається числом містяться в ньому внутрішніх вузлів. Зовнішні вузли відповідають порожнім двійковим деревам. Наприклад, лівий нащадок вузла В - непорожній (містить вузол D), тоді як правий нащадок вузла В - пусте дерево. У деяких випадках зовнішні вузли позначаються будь-яким чином, в інших - на них зовсім не посилаються і вони вважаються порожніми двійковими деревами (на рис. 16 зовнішні вузли не показані).

Заснована на генеалогії метафора дає зручний спосіб позначення вузлів всередині двійкового дерева. Вузол р є батьком (або предком) вузла n, якщо n - нащадок вузла р. Два вузла є братами, якщо вони належать одній і тій же батьків. Для двох заданих вузлів n1 і nk таких, що вузол nk належить Піддерево з коренем у вузлі n1, кажуть, що вузол nk є нащадком вузла n1, а вузол n1 - предком вузла nk. Існує унікальний шлях від вузла n1 вниз до кожного з нащадків nk, a саме: послідовність вузлів n1 і n2, ... nk така, що вузол ni є батьком вузла ni + 1 для i = 1, 2, ..., k- 1. Довжина шляху дорівнює числу ребер (k-1), що містяться в ньому. Наприклад, на рис. 1а унікальний шлях від вузла А до вузла D складається з послідовності А, В, D і має довжину 2.

Глибина вузла n визначається рекурсивно:

Глибина вузла дорівнює довжині унікального шляху від кореня до вузла. На рис. 1а вузол А має глибину 0, а вузол D має глибину, рівну 2.

Висота вузла n також визначається рекурсивно:

де через лев (n) позначений лівий нащадок вузла n і через прав (n) - правий нащадок вузла n. Висота вузла n дорівнює довжині найдовшого шляху від вузла n вниз до зовнішнього вузла поддерева n. Висота двійкового дерева визначається як висота його кореневого вузла. Наприклад, двійкове дерево на рис. 1а має висоту 3, а вузол D має висоту 1.

При реалізації довічних дерев, заснованої на точковому представленні, вузли є об'єктами класу TreeNode.

Елементи даних _lchild і _rchild позначають зв'язку поточного вузла з лівим і правим нащадками відповідно, а елемент даних val містить сам елемент.

Конструктор класу формує бінарне дерево одиничного розміру - єдиний внутрішній вузол має два порожніх нащадка, кожне з яких представлено нулем NULL:

Деструкція ~ TreeNode рекурсивно видаляє обидва нащадка поточного вузла (якщо вони існують) перед знищенням самого поточного вузла:

Визначимо шаблон нового класу SearchTree для подання двійкового дерева пошуку. Клас містить елемент даних root, який вказує на корінь двійкового дерева пошуку (об'єкт класу TreeNode) і елемент даних cmp, який вказує на функцію порівняння.

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

Конструктори і деструктори

Конструктор SearchTree инициализирует елементи даних cmp для функції порівняння і root для порожнього дерева пошуку:

Дерево пошуку порожньо тільки, якщо в елементі даних root міститься нуль (NULL) замість дозволеного покажчика:

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

Пошук

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

Цей алгоритм пошуку реалізується в компонентної функції find, яка повертає виявлений нею покажчик на елемент або NULL, якщо такий елемент не існує в дереві пошуку.

Цей алгоритм пошуку можна порівняти з турніром, в якому беруть участь деякі кандидати. На початку, коли ми починаємо з кореня, до складу кандидатів входять всі елементи в дереві пошуку. У загальному випадку для кожного вузла n до складу кандидатів входять всі нащадки n. На кожному етапі проводиться порівняння val з n-> val. Якщо val менше, ніж n-> val, то склад кандидатів звужується до елементів, що знаходяться в лівому поддереве, а елементи в правому поддереве n, як і сам елемент n-> val, виключаються зі змагання. Аналогічним чином, якщо val більше, ніж n-> val, то склад кандидатів звужується до правого піддерева n. Процес триває до тих пір, поки не буде виявлений елемент val або не залишиться жодного кандидата, що означає, що елемент val не існує в дереві пошуку.

Для знаходження найменшого елемента ми починаємо з кореня і простежуємо зв'язку з лівим нащадком до тих пір, поки не досягнемо вузла n, лівий нащадок якого порожній - це означає, що у вузлі n міститься найменший елемент. Цей процес також можна уподібнити турніру. Для кожного вузла n склад кандидатів визначається нащадками вузла n. На кожному кроці зі складу кандидатів видаляються ті елементи, які більше або дорівнюють n-> val і лівий нащадок n буде тепер виступати в якості нового n. Процес триває до тих пір, поки не буде досягнутий певний вузол n з порожнім лівим нащадком і, вважаючи, що не залишилося кандидатів менше, ніж n-> val, і буде повернуто значення n-> val.

Компонентна функція findMin повертає найменший елемент в даному дереві пошуку, в ній відбувається звернення до компонентної функції _findMin, яка реалізує описаний раніше алгоритм пошуку, починаючи з вузла n:

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

симетричний обхід

Обхід двійкового дерева - це процес, при якому кожен вузол відвідується точно тільки один раз. Компонентна функція inorder виконує спеціальну форму обходу, відому як симетричний обхід. Стратегія полягає спочатку в симетричному обході лівого піддерева, потім відвідування кореня і потім в симетричному обході правого піддерева. Вузол відвідується шляхом застосування функції звернення до елементу, записаному в вузлі.

Компонентна функція inorder служить в якості ведучої функції. Вона звертається до власної компонентної функції _inorder, яка виконує симетричний обхід від вузла n і застосовує функцію visit до кожного досягнутому вузлу.

При симетричному обході кожного з довічних дерев пошуку, показаних на рис. 2, вузли відвідуються в зростаючому порядку: 2, 3, 5, 7, 8. Звичайно, при симетричному обході будь-якого двійкового дерева пошуку всі його елементи відвідуються в зростаючому порядку. Щоб з'ясувати, чому це так, зауважимо, що при виконанні симетричного обходу в деякому вузлі n елементи менше, ніж n-> val відвідуються до n, оскільки вони належать до лівого піддерева n, а елементи більше, ніж n-> val відвідуються після n , оскільки вони належать праве піддерево n. Отже, вузол n відвідується в правильній послідовності. Оскільки n - довільний вузол, то це ж правило дотримується для кожного вузла.

Компонентна функція inorder забезпечує спосіб перерахування елементів двійкового дерева пошуку в відсортованому порядку. Наприклад, якщо а є деревом пошуку SearchTree для рядків, то можемо надрукувати в лексикографічному порядку однією командою а.inorder (printstring). Для цього функція звернення printstring може бути визначена як:

При симетричному обході двійкового дерева вузол, відвідуваний після деякого вузла n, називається послідовником вузла n, а вузол, який відвідують безпосередньо перед n, називається попередником вузла n. Не існує ніякого попередника для першого відвідуваного вузла і ніякого послідовника для останнього відвідуваного вузла (в двійковому дереві пошуку ці вузли містять найменший і найбільший елемент відповідно).

включення елементів

Для включення нового елемента в двійкове дерево пошуку спочатку потрібно визначити його точне положення - а саме зовнішній вузол, який повинен бути замінений шляхом відстеження шляху пошуку елемента, починаючи з кореня. Крім збереження покажчика n на поточний вузол ми будемо зберігати покажчик р на предка вузла n. Таким чином, коли n досягне деякого зовнішнього вузла, р вказуватиме на вузол, який повинен стати предком нового вузла. Для здійснення включення вузла ми створимо новий вузол, що містить новий елемент, і потім зв'яжемо предок р з цим новим вузлом (рис. 3).

Компонентна функція insert включає елемент val в це двійкове дерево пошуку:

Мал. 3: Включення елемента в двійкове дерево пошуку

видалення елементів

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

Мал. 4: Три ситуації, що виникають при видаленні елемента із двійкового дерева пошуку

Щоб видалити елемент з дерева пошуку, спочатку ми відстежуємо шлях пошуку елемента, починаючи з кореня і вниз до вузла n, що містить елемент. У цей момент можуть виникнути три ситуації, показані на рис. 4:

1. Вузол n має порожній лівий нащадок. У цьому випадку посилання на n (записана в предка n, якщо він є) замінюється на посилання на правого нащадка n.
2. У вузла n є непорожній лівий нащадок, але правий нащадок порожній. У цьому випадку посилання вниз на n замінюється посиланням на лівий нащадок вузла n.
3. Вузол n має два непустих нащадка. Знайдемо послідовника для n (назвемо його m), скопіюємо дані, що зберігаються в m, в вузол n і потім рекурсивно видалимо вузол m з дерева пошуку.

Дуже важливо простежити, як буде виглядати результуюче двійкове дерево пошуку в кожному випадку. Розглянемо випадок 1. Якщо підлягає видаленню вузол n, є лівим нащадком, то елементи, що відносяться до правого піддерева n будуть менше, ніж у вузла р, предка вузла n. При видаленні вузла n його праве піддерево зв'язується з вузлом р і елементи, що зберігаються в новому лівому поддереве вузла р звичайно залишаються менше елемента в вузлі р. Оскільки ніякі інші посилання не змінюються, то дерево залишається двійковим деревом пошуку. Аргументи залишаються подібними, якщо вузол n є правим нащадком, і вони тривіальні, якщо n - кореневий вузол. Випадок 2 пояснюється аналогічно. У разі 3 елемент v, записаний в вузлі n, перекривається наступним великим елементом, що зберігаються в вузлі m (назвемо його w), після чого елемент w видаляється з дерева. У отримувати після цього довічним дереві значення в лівому поддереве вузла n будуть менше w, оскільки вони менше v. Більш того, елементи в правому піддереві вузла n більше, ніж w, оскільки (1) вони більше, ніж v, (2) немає жодного елемента двійкового дерева пошуку, лежачого між v і w і (3) з них елемент w був видалений .

Зауважимо, що в разі 3 вузол m повинен обов'язково існувати, оскільки праве піддерево вузла n непорожнє. Більш того, рекурсивний виклик для видалення m не може привести до зриву рекурсивного виклику, оскільки якщо вузол m не мав би лівого нащадка, то був би застосований випадок 1, коли його потрібно було б видалити.

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

Компонентна функція remove є загальнодоступною компонентної функцією для видалення вузла, що містить заданий елемент. Вона звертається до власної компонентної функції _remove, яка виконує фактичну роботу:

Мал. 5: Послідовність операцій видалення елемента: (а) і (б) - Випадок 1: видалення із двійкового дерева елемента 8; (Б) і (в) - Випадок 2: видалення елемента 5; (В) і (г) - Випадок 3: видалення елемента 3

Параметр n (типу посилання) служить в якості псевдоніма для поля посилання, яке містить посилання вниз на поточний вузол. При досягненні вузла, що підлягає видаленню (old), n позначає поле посилання (в предка вузла old), що містить посилання вниз на old. Отже команда n = old -> _ rchild замінює посилання на old посиланням на правого нащадка вузла old.

Компонентна функція removeMin видаляє з дерева пошуку найменший елемент і повертає його:

також доступна реалізація двійкового дерева на Сі з базовими функціями. Оператори typedef T і compGT слід змінити так, щоб вони відповідали даним, збереженим в дереві. Кожен вузол Node містить покажчики left, right на лівого і правого нащадків, а також покажчик parent на предка. Власне дані зберігаються в поле data. Адреса вузла, що є коренем дерева зберігається в укзателе root, значення якого на самому початку, природно, NULL. Функція insertNode запитує пам'ять під новий вузол і вставляє вузол в дерево, тобто встановлює потрібні значення потрібних покажчиків. Функція deleteNode, навпаки, видаляє вузол з дерева (тобто встановлює потрібні значення потрібних покажчиків), а потім звільняє пам'ять, яку займав вузол. Функція findNode шукає в дереві вузол, що містить задане значення.