Алгоритми і структури даних для початківців двоичное дерево пошуку

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

У цій частині ми розглянемо абсолютно нову структуру даних - дерево. А точніше, двійкове (бінарне) дерево пошуку (binary search tree). Бінарне дерево пошуку має структуру дерева, але елементи в ньому розташовані за певними правилами.

Для початку ми розглянемо звичайне дерево.

Дерево - це структура, в якій у кожного вузла може бути нуль або більше подсистемами - «дітей». Наприклад, дерево може виглядати так:

Це дерево показує структуру компанії. Вузли представляють людей або підрозділи, лінії - зв'язки і відносини. Дерево - це найефективніший спосіб представлення та зберігання такої інформації.

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

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

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

Давайте подивимося на дерево, побудоване за цими правилами:

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

Зверніть увагу, як зазначені обмеження впливають на структуру дерева. Кожне значення зліва від кореня (8) менше восьми, кожне значення праворуч - більше або дорівнює кореню. Це правило застосовується до будь-якого вузла дерева.

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

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

Розглянемо докладніше перші кроки.

В першу чергу додається 8. Це значення стає коренем дерева. Потім ми додаємо 4. Оскільки 4 менше 8, ми кладемо її в лівого дитини, згідно з правилом 2. Оскільки у вузла з вісімкою немає дітей зліва, 4 стає єдиним лівим дитиною.

Після цього ми додаємо 2. 2 менше 8, тому йдемо наліво. Так як зліва вже є значення, порівнюємо його з вставляються. 2 менше 4, а у четвірки немає дітей зліва, тому 2 стає лівим дитиною 4.

Потім ми додаємо трійку. Вона йде лівіше 8 і 4. Але так як 3 більше, ніж 2, вона стає правим дитиною 2, відповідно до третього правилом.

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

клас BinaryTreeNode

метод Remove

• Поведінка: Видаляє перший вузол з заданим значенням.
• Складність: O (log n) в середньому; O (n) в гіршому випадку.

Видалення вузла з дерева - одна з тих операцій, які здаються простими, але насправді таять в собі чимало підводних каменів.

В цілому, алгоритм видалення елемента виглядає так:

• Знайти вузол, який треба видалити.
• Видалити його.

Перший крок досить простий. Ми розглянемо пошук вузла в методі Contains нижче. Після того, як ми знайшли вузол, який необхідно видалити, у нас можливі три випадки.

Випадок 1: У видаляється вузла немає правого дитини.

В цьому випадку ми просто переміщаємо лівого дитини (при його наявності) на місце видаленого вузла. В результаті дерево буде виглядати так:

Випадок 2: У видаляється вузла є тільки правий дитина, у якого, в свою чергу немає лівого дитини.

У цьому випадку нам треба перемістити правого дитини видаляється вузла (6) на його місце. Після видалення дерево буде виглядати так:

Випадок 3: У видаляється вузла є перша дитина, у якого є лівий дитина.

У цьому випадку місце видаляється вузла займає крайній лівий дитина правого дитини видаляється вузла.

Давайте подивимося, чому це так. Ми знаємо про поддереве, що починається з видаляється вузла наступне:

• Всі значення праворуч від нього більше або дорівнюють значенню самого вузла.
• Найменше значення правого піддерева - крайнє ліве.

Ми обіцяли помістити на місце видаленого вузол із значенням, меншим або рівним будь-якого вузла праворуч від нього. Для цього нам необхідно знайти найменше значення в правому піддереві. Тому ми беремо крайній лівий вузол правого піддерева.

Після видалення вузла дерево буде виглядати так:

Тепер, коли ми знаємо, як видаляти вузли, подивимося на код, який реалізує цей алгоритм.

Відзначимо, що метод FindWithParent (див. Метод Contains) повертає знайдений вузол і його батька, оскільки ми повинні замінити лівого або правого дитини батька видаляється вузла.

// Якщо значення батька більше поточного,

// правий дитина поточного вузла стає лівим дитиною батька.

parent. Left = current. Right;

else if (result <0 ) >> // Випадок 3: Якщо у правого дитини є діти зліва, крайній лівий дитина // з правого піддерева замінює видаляється вузол. else // Ліве піддерево батька стає правим піддерево крайнього лівого вузла. leftmostParent.Left = leftmost.Right; // Лівий і правий дитина поточного вузла стає лівим і правим дитиною крайнього лівого. leftmost.Left = current.Left; leftmost.Right = current.Right; if (parent == null) <_head = leftmost;> else 0)

// Якщо значення батька більше поточного,

// крайній лівий вузол стає лівим дитиною батька.

parent. Left = leftmost;

обхід дерев

Обходи дерева - це сімейство алгоритмів, які дозволяють обробити кожен вузол в певному порядку. Для всіх алгоритмів обходу нижче в якості прикладу візьмемо наступне дерево:

Приклад дерева для обходу

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

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

Метод Preorder (або префіксний обхід)

• Поведінка: Обходить дерево в префіксному порядку, виконуючи вказану дію над кожним вузлом.
• Складність: O (n)
• Порядок обходу: 4, 2, 1, 3, 5, 7, 6, 8

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

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