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

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

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

Дерева

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

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

Дерево на рисунку, поданому вище, дуже просте. Воно відбиває тільки відношення спорідненості категорій, але не накладає жодних обмежень на свою структуру. У генерального директора може бути як один безпосередній підлеглий, так і декілька або жодного. На рисунку відділ продажів розташований ліворуч від відділу маркетингу, але порядок насправді не має значення. Єдине обмеження дерева – кожен вузол може мати не більше за одного батька. Самий верхній вузол (рада директорів, у нашому прикладі) батька не має. Цей вузол називається “кореневим”, або ” коренем”.

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

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

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

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

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

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

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

BinaryTree tree = new BinaryTree ();tree.Add (8);tree.Add (4);tree.Add (2);tree.Add (3);tree.Add (10);tree.Add (6);tree.Add (7);

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

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

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

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

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

Клас BinaryTreeNode

Клас BinaryTreeNode представляє один вузол двійкового дерева. Він утримує посилання на лівому і правому піддереві (якщо піддерева немає, посилання має значення null), дані вузла і метод IComparable.CompareTo для порівняння вузлів. Він згодиться для визначення, в яке поддерево повинен йти цей вузол. Як бачите, клас BinaryTreeNode дуже простий:

class BinaryTreeNode: IComparable where TNode: IComparable{ public BinaryTreeNode (TNode value) { Value = value; } public BinaryTreeNode Left { get; set; } public BinaryTreeNode Right { get; set; } public TNode Value { get; private set; } /// /// Порівнює поточний вузол з даним. /// /// Порівняння робиться за полем Value. /// Метод повертає 1, якщо значення поточного вузла більше
/// ніж переданого методу, - 1, якщо менше і 0, якщо вони дорівнюють public int CompareTo (TNode other) { return Value.CompareTo (other); }}

Клас BinaryTree

Клас BinaryTree надає основні методи для маніпуляцій з даними: вставка елемента (Add), видалення (Remove), метод Contains для перевірки, чи є таке значення в дереві, декілька методів для обходу дерева різними способами, метод Count і Clear.

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

public class BinaryTree: IEnumerable where T: IComparable{ private BinaryTreeNode_head; private int_count; public void Add (T value) { throw new NotImplementedException (); } public bool Contains (T value) {
throw new NotImplementedException (); } public bool Remove (T value) { throw new NotImplementedException (); } public void PreOrderTraversal (Action action) { throw new NotImplementedException (); } public void PostOrderTraversal (Action action) { throw new NotImplementedException (); } public void InOrderTraversal (Action action) { throw new NotImplementedException (); } public IEnumerator GetEnumerator (){ throw new NotImplementedException (); } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator (){ throw new NotImplementedException (); } public void Clear (){ throw new NotImplementedException (); } public int Count { get; }}

Метод Add

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

Додавання вузла не становить складності. Воно стає ще простіше, якщо розв’язувати цю задачу рекурсивно. Є всього два випадки, які потрібно врахувати:

1. Дерево порожнє.
2. Дерево не порожнє.

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

public void Add (T value){ // Випадок 1: Якщо дерево порожнє, просто створюємо кореневий вузол. if (_ head == null) {_head = new BinaryTreeNode (value);
} // Випадок 2: Дерево не порожнє => // шукаємо правильне місце для вставки. else { AddTo (_ head, value); }_count++;} // Рекурсивна ставка.private void AddTo (BinaryTreeNode node, T value){ // Випадок 1: значення, що вставляється, менше значення вузла if (value.CompareTo (node.Value)  < 0) { // Якщо немає лівого піддерева, додаємо значення в ліву дитину, if (node.Left == null) { node.Left = new BinaryTreeNode (value); } else { // якщо ні, то повторюємо для лівого піддерева. AddTo (node.Left, value); } } // Випадок 2: значення, що вставляється, більше або дорівнює значенню вузла. else { // Якщо немає правого піддерева, додаємо значення в праву дитину, if (node.Right == null) { node.Right = new BinaryTreeNode (value); }
else { // якщо ні, то повторюємо для правого піддерева. AddTo (node.Right, value); } }}

Метод Remove

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

public bool Remove (T value){ BinaryTreeNode current, parent; // Знаходимо вузол, що видаляється. current = FindWithParent (value, out parent); if (current == null) { return false; }_count--; // Випадок 1: Якщо немає дітей праворуч, ліва дитина стає на місце того, що видаляється.
if (current.Right == null) { if (parent == null) {_head = current.Left; } else { int result = parent.CompareTo (current.Value); if (result > 0) { // Якщо значення батька більше за поточне, // ліва дитина поточного вузла стає лівою дитиною батька. parent.Left = current.Left; } else if (result < 0) { // Якщо значення батька менше за поточне, // ліва дитина поточного вузла стає правою дитиною батька. parent.Right = current.Left; } } } // Випадок 2: Якщо у правої дитини немає дітей ліворуч // те він займає місце вузла, що видаляється. else if (current.Right.Left == null) { current.Right.Left = current.Left; if (parent == null) {_head = current.Right; } else { int result = parent.CompareTo (current.Value); if (result > 0)
{ // Якщо значення батька більше за поточне, // права дитина поточного вузла стає лівою дитиною батька. parent.Left = current.Right; } { // Якщо значення батька більше за поточне, // крайній лівий вузол стає лівою дитиною батька. parent.Left = leftmost; } else if (result < 0) { // Якщо значення батька менше за поточне, // крайній лівий вузол стає правою дитиною батька. parent.Right = leftmost; } } } return true;}

Метод Contains

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

Метод Contains виконується за допомогою методу FindWithParent, який проходить деревом, виконуючи в кожному вузлі наступні кроки:

1. Якщо поточний вузол null, повернути null.
2. Якщо значення поточного вузла дорівнює шуканому, повернути поточний вузол.
3. Якщо шукане значення менше значення поточного вузла, встановити ліву дитину поточним вузлом і перейти до кроку 1.
4. Якщо ні, то встановити праву дитину поточним вузлом і перейти до кроку 1.

Оскільки Contains повертає нульове значення, воно визначається порівнянням результату виконання FindWithParent з null. Якщо FindWithParent повернув непорожній вузол, Contains повертає true.

Метод FindWithParent також використовується в методі Remove.

public bool Contains (T value){ // Пошук вузла здійснюється іншим методом. BinaryTreeNode parent; return FindWithParent (value, out parent) != null;} /// /// Знаходить і повертає перший вузол із заданим значенням. Якщо значення/// не знайдене, повертає null. Також повертає батька знайденого вузла (чи null) /// для використання в методі Remove./// private BinaryTreeNode FindWithParent (T value, out BinaryTreeNode parent){ // Спробуємо знайти значення в дереві. BinaryTreeNode current =_head; parent = null; // До тих пір, поки не знайшли... while (current != null) { int result = current.CompareTo (value); if (result > 0) { // Якщо шукане значення менше, рухаємось ліворуч.
parent = current; current = current.Left; } else if (result < 0) { // Якщо шукане значення більше, рухаємось праворуч. parent = current; current = current.Right; } else { // Якщо рівні, то зупиняємося break; } } return current;}

Метод Count

• Поведінка: повертає кількість вузлів дерева або 0, якщо дерево порожнє.
• Складність: O (1)

Це поле інкрементується методом Add і декрементується методом Remove.

public int Count{ get { return_count; }}

Метод Clear

• Поведінка: видаляє всі вузли дерева.
• Складність: O (1)

public void Clear (){
_ head = null;_count = 0;}

Обхід дерев

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

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

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

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

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

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

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

public void PreOrderTraversal (Action action){ PreOrderTraversal (action,_head);} private void PreOrderTraversal (Action action, BinaryTreeNode node){ if (node != null) { action (node.Value); PreOrderTraversal (action, node.Left); PreOrderTraversal (action, node.Right); }
}

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

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

За постфіксного обходу ми відвідуємо ліве піддерево, праве піддерево, а потім, після обходу всіх дітей, переходимо до самого вузла.

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

public void PostOrderTraversal (Action action){ PostOrderTraversal (action,_head);} private void PostOrderTraversal (Action action, BinaryTreeNode node){
if (node != null) { PostOrderTraversal (action, node.Left); PostOrderTraversal (action, node.Right); action (node.Value); }}

Метод Inorder (інфіксний обхід)

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

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

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

Public void InOrderTraversal (Action action){ InOrderTraversal (action,_head);} private void InOrderTraversal (Action action, BinaryTreeNode node){ if (node != null) { InOrderTraversal (action, node.Left); action (node.Value); InOrderTraversal (action, node.Right); }} public IEnumerator InOrderTraversal (){ // Це нерекурсивний алгоритм. // Він використовує стек для того, щоб уникнути рекурсії. if (_ head != null) { // Стік для збереження пропущених вузлів. Stack stack = new Stack (); BinaryTreeNode current =_head; // Коли ми позбавляємося від рекурсії, нам необхідно
// запам'ятовувати, в якийй бік ми повинні рухатися. bool goLeftNext = true; // Кладемо в стек корінь. stack.Push (current); while (stack.Count > 0) { // Якщо ми йдемо ліворуч... if (goLeftNext) { // Кладемо все, крім найлівішого вузла, на стек. // Крайній лівий вузол ми повернемо за допомогою yield. while (current.Left != null) { stack.Push (current); current = current.Left; } } // Префіксний порядок: left ->yield ->right. yield return current.Value; // Якщо ми можемо піти праворуч, то йдемо. if (current.Right != null) { current = current.Right; // Після того, як ми пішли праворуч один раз
// ми повинні знову піти ліворуч. goLeftNext = true; } else { // Якщо ми не можемо піти праворуч, то ми повинні дістати батьківський вузол // зі стека, обробити його і йти в його праву дитину. current = stack.Pop (); goLeftNext = false; } } }}

Метод GetEnumerator

• Поведінка: повертає ітератор для обходу дерева інфіксним способом.
• Складність: отримання ітератора – O (1). Обхід дерева – O (n).

public IEnumerator GetEnumerator (){ return InOrderTraversal ();} System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator (){ return GetEnumerator ();}

Далі буде

На цьому ми закінчуємо п’яту частину керівництва по алгоритмах і структурах даних. У наступній статті ми розглянемо множини (Set).

_{Переклад статті “The Binary Search Tree”}