
Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.
Дотепер ми розглядали структури даних, у яких дані розташовуються лінійно. У зв’язному списку – від першого вузла до єдиного останнього. У динамічному масиві – у вигляді безперервного блоку.
У цій частині ми розглянемо абсолютно нову структуру даних – дерево, точніше, двійкове (бінарне) дерево пошуку (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) у гіршому разі.
Додавання вузла не становить складності. Воно стає ще простіше, якщо розв’язувати цю задачу рекурсивно. Є всього два випадки, які потрібно врахувати:
- Дерево порожнє.
- Дерево не порожнє.
Якщо дерево порожнє, ми просто створюємо новий вузол і додаємо його в дерево. У другому випадку ми порівнюємо передане значення зі значенням у вузлі, починаючи від кореня. Якщо значення, що додається, менше значення даного вузла, повторюємо ту саму процедуру для лівого піддерева, ящо ні, то для правого.
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
, який проходить деревом, виконуючи в кожному вузлі наступні кроки:
- Якщо поточний вузол
null
, повернутиnull
. - Якщо значення поточного вузла дорівнює шуканому, повернути поточний вузол.
- Якщо шукане значення менше значення поточного вузла, встановити ліву дитину поточним вузлом і перейти до кроку 1.
- Якщо ні, то встановити праву дитину поточним вузлом і перейти до кроку 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”
Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?