Бінарні дерева пошуку і рекурсія – це просто

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

Бінарне дерево — це ієрархічна структура даних, в якій кожен вузол має значення (воно ж є в даному випадку ключем) і посилання на лівого і правого нащадка. Вузол, що знаходиться на самому верхньому рівні (не є чиїм або нащадком) називається коренем. Вузли, які не мають нащадків (обидва нащадка яких дорівнюють NULL) називаються листям.

image
Рис. 1 Бінарне дерево

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

image
Рис. 2 Бінарне дерево пошуку
Збалансоване бінарне дерево пошуку — це бінарне дерево пошуку з логарифмічною заввишки. Дане визначення швидше ідейне, ніж суворе. Суворе визначення оперує різницею глибини самого глибокого і самого неглибокого аркуша (AVL-дерева) чи відношенням глибини самого глибокого і самого неглибокого листа (у червоно-чорних деревах). У збалансованому бінарному дереві пошуку операції пошуку, вставки і видалення виконуються за логарифмічний час (так як шлях до будь-якого листа від кореня не більше логарифма). В виродженому випадку незбалансованого бінарного дерева пошуку, наприклад, коли в порожнє дерево вставлялася відсортована послідовність, дерево перетвориться в лінійний список, і операції пошуку, вставки і видалення будуть виконуватися за лінійний час. Тому балансування дерева вкрай важлива. Технічно балансування здійснюється поворотами частин дерева при вставці нового елемента, якщо вставка елемента порушила умова збалансованості.

image
Рис. 3 Збалансоване бінарне дерево пошуку

Збалансоване бінарне дерево пошуку застосовується, коли необхідно здійснювати швидкий пошук елементів, що чергується зі вставками нових елементів і вилученнями існуючих. У разі, якщо набір елементів, що зберігається в структурі даних фіксований і немає нових вставок і вилучень, то масив краще. Тому що пошук можна здійснювати алгоритм бінарного пошуку за логарифмічний час, але відсутні додаткові витрати по зберіганню і використанню покажчиків. Наприклад, в С++ асоціативні контейнери set і map являють собою збалансоване бінарне дерево пошуку.

image
Рис. 4 Екстремально збалансоване бінарне дерево пошуку

Тепер коротко обговоримо рекурсію. Рекурсія у програмуванні – це виклик функцією самої себе з іншими аргументами. В принципі, рекурсивна функція може викликати сама себе і з тими ж самими аргументами, але в цьому випадку буде нескінченний цикл рекурсії, який закінчиться переповненням стека. Усередині будь-рекурсивної функції повинен бути базовий випадок, при якому відбувається вихід з функції, а також виклик або виклики самої себе з іншими аргументами. Аргументи не повинні бути іншими, а повинні наближати виклик функції до базового нагоди. Наприклад, виклик всередині рекурсивну функцію обчислення факторіала повинен йти з меншим значенням аргументом, а виклики всередині рекурсивної функції обходу дерева повинні йти з вузлами, що знаходяться далі від кореня, ближче до листя. Рекурсія може бути не тільки прямий (виклик безпосередньо себе), але і непрямою. Наприклад А викликає Б, а Б викликає А. За допомогою рекурсії можна емулювати ітеративний цикл, а також роботу структури даних стек (LIFO).

int factorial(int n)
{
if(n < = 1) // Базовий випадок
{
return 1;
}
return n * factorial(n - 1); //рекурсивеый виклик з іншим аргументом
}
// factorial(1): return 1
// factorial(2): return 2 * factorial(1) (return 2 * 1)
// factorial(3): return 3 * factorial(2) (return 3 * 2 * 1)
// factorial(4): return 4 * factorial(3) (return 4 * 3 * 2 * 1)
// Обчислює факторіал числа n (n повинно бути невеликим за типу int
// значення, що повертається. На практиці можна зробити long long і взагалі
// замінити рекурсію циклом. Якщо важлива швидкість розрахунків і не шкода пам'ять, то
// можна зовсім позбутися функції і використовувати масив з попередньо
// посчитанными факториалами).

void reverseBinary(int n)
{
if (n == 0) // Базовий випадок
{
return;
}
cout << n%2;
reverseBinary(n/2); //рекурсивеый виклик з іншим аргументом
}
// Друкує бінарне представлення числа у зворотному порядку

void forvardBinary(int n)
{
if (n == 0) // Базовий випадок
{
return;
}
forvardBinary(n/2); //рекурсивеый виклик з іншим аргументом
cout << n%2;
}
// Поміняли місцями дві останні інструкції
// Друкує бінарне представлення числа в прямому порядку
// Функція є прикладом емуляції стека

void ReverseForvardBinary(int n)
{
if (n == 0) // Базовий випадок
{
return;
}
cout << n%2; // друкує в зворотному порядку
ReverseForvardBinary(n/2); //рекурсивеый виклик з іншим аргументом
cout << n%2; // друкує в прямому порядку
}
// Функція друкує спочатку бінарне представлення в зворотному порядку,
// а потім у прямому порядку


int product(int x, int y)
{
if (y == 0) // Базовий випадок
{
return 0;
}
return (x + product(x, y-1)); //рекурсивеый виклик з іншим аргументом
}
// Функція обчислює добуток x * y ( x складає y раз)
// Функція є абсурдною з точки зору практики,
// наведена для кращого розуміння рекурсії

Коротко обговоримо дерева з точки зору теорії графів. Граф – це множина вершин і ребер. Ребро – це зв'язок між двома вершинами. Кількість можливих ребер у графі квадратично залежить від кількості вершин (для розуміння можна уявити турнірну таблицю зіграних матчів). Дерево – це зв'язний граф без циклів. Зв'язність означає, що з будь-якої вершини в будь-яку іншу існує шлях по ребрах. Відсутність циклів означає, що цей шлях – єдиний. Обхід графа – це систематичне відвідування всіх його вершин по одному разу кожного. Існує два види обходу графа: 1) пошук у глибину; 2) пошук у ширину.

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

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

З формальної точки зору можна зробити як рекурсивні, так і итеративную версію як пошуку в ширину, так і пошуку в глибину. Для обходу в ширину в обох випадках необхідна чергу. Рекурсія в рекурсивну реалізації обходу завширшки всього лише емулює цикл. Для обходу в глибину існує рекурсивна реалізація без стека, рекурсивна реалізація зі стеком і итеративная реалізація зі стеком. Итеративная реалізація обхід в глибину без стека неможлива.

Асимптотична складність обходу і в ширину і в глибину O(V + E), де V – кількість вершин, E – кількість ребер. Тобто є лінійною за кількістю вершин і ребер. Записи O(V + E) з змістовної точки зору еквівалентна запис O(max(V,E)), але остання не прийнята. Тобто, складність буде визначаться максимальним з двох значень. Незважаючи на те, що кількість ребер квадратично залежить від кількості вершин, ми не можемо записати складність як O(E), так як якщо граф сильно розріджений, то це буде помилкою.

DFS застосовується в алгоритмі знаходження компонентів сильної зв'язності в орієнтованому графі. BFS застосовується для знаходження найкоротшого шляху в графі, в алгоритмах розсилки повідомлень по мережі, збирачів сміття, в програмі індексування – павука пошукового движка. І DFS і BFS застосовуються в алгоритмі пошуку мінімального покриваючого дерева, при перевірці циклів в графі, для перевірки двудольности.
Обходу в ширину у графі відповідає обхід за рівнями бінарного дерева. При цьому обході йде відвідування вузлів за принципом зверху вниз і зліва направо. Обходу в глибину в графі відповідають три види обходів бінарного дерева: прямий (pre-order), симетричний (in-order) і зворотний (post-order).

Прямий обхід йде в наступному порядку: корінь, лівий нащадок, правий нащадок. Симетричний — лівий нащадок, корінь, правий нащадок. Зворотний – лівий нащадок, правий нащадок, корінь. У коді рекурсивної функції відповідного обходу зберігається відповідний порядок викликів (порядок рядків коду), де замість кореня йде виклик даної рекурсивної функції.

Якщо нам дано зображення дерева, і потрібно знайти його обходи, то може допомогти така техніка (див. рис. 5). Обводимо дерево огинаючої замкнутої кривої (починаємо йти зліва вниз і замикаємо праворуч вгору). Прямого обходу буде відповідати порядок, в якому обвідна, рухаючись від кореня вперше проходить поруч з вузлами ліворуч. Для симетричного обходу порядок, в якому обвідна, рухаючись від кореня вперше проходить поруч з вузлами знизу. Для зворотного обходу порядок, в якому обвідна, рухаючись від кореня вперше проходить поруч з вузлами праворуч. У коді рекурсивного виклику прямого обходу йде: виклик, лівий, правий. Симетричного – лівий, виклик, правий. Зворотного – лівий правий, виклик.

image
Рис. 5 Допоміжний малюнок для обходів

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

struct TreeNode
{
double data; // ключ/дані
TreeNode *left; // вказівник на лівого нащадка
TreeNode *right; // покажчик правого нащадка
};

void levelOrderPrint(TreeNode *root) {
if (root == NULL)
{
return;
}
queue<TreeNode *> q; // Створюємо чергу
q.push(root); // Вставляємо корінь в чергу

while (!q.empty() ) // поки черга не порожня
{
TreeNode* temp = q.front(); // Беремо перший елемент черги
q.pop(); // Видаляємо перший елемент черги
cout << temp->data << " "; // Друкуємо значення першого елемента в черзі

if ( temp->left != NULL )
q.push(temp->left); // Вставляємо в чергу лівого нащадка

if ( temp->right != NULL )
q.push(temp->right); // Вставляємо в чергу правого нащадка
}
}


void preorderPrint(TreeNode *root)
{
if (root == NULL) // Базовий випадок
{
return;
}
cout << root->data << " ";
preorderPrint(root->left); //рекурсивний виклик лівого піддерева
preorderPrint(root->right); //рекурсивний виклик правого піддерева
}
// Функція друкує значення бінарного дерева пошуку в прямому порядку.
// Замість друку першої інструкцією функції може бути будь-яка дія
// з даним вузлом

void inorderPrint(TreeNode *root)
{
if (root == NULL) // Базовий випадок
{
return;
}
preorderPrint(root->left); //рекурсивний виклик лівого піддерева
cout << root->data << " ";
preorderPrint(root->right); //рекурсивний виклик правого піддерева
}
// Функція друкує значення бінарного дерева пошуку в симетричному порядку.
// Тобто у відсортованому порядку

void postorderPrint(TreeNode *root)
{
if (root == NULL) // Базовий випадок
{
return;
}
preorderPrint(root->left); //рекурсивний виклик лівого піддерева
preorderPrint(root->right); //рекурсивний виклик правого піддерева
cout << root->data << " ";
}
// Функція друкує значення бінарного дерева пошуку в зворотному порядку.
// Не плутайте зворотний і обратноотсортированный (зворотний симетричний).

void reverseInorderPrint(TreeNode *root)
{
if (root == NULL) // Базовий випадок
{
return;
}
preorderPrint(root->right); //рекурсивний виклик правого піддерева
cout << root->data << " ";
preorderPrint(root->left); //рекурсивний виклик лівого піддерева

}
// Функція друкує значення бінарного дерева пошуку в зворотному симетричному порядку.
// Тобто у зворотному відсортованому порядку

void iterativePreorder(TreeNode *root)
{
if (root == NULL)
{
return;
}
stack<TreeNode *> s; // Створюємо стек
s.push(root); // Вставляємо корінь в стек
/* Витягуємо з стека один за іншим всі елементи.
Для кожного витягнутого робимо наступне
1) друкуємо його
2) вставляємо в стек правого! нащадка
(Увага! стек змінить порядок виконання на протилежний!)
3) вставляємо в стек лівого! нащадка */
while (s.empty() == false)
{
// Отримуємо вершину стека і друкуємо
TreeNode *temp = s.top();
s.pop();
cout << temp->data << " ";

if (temp->right)
s.push(temp->right); // Вставляємо в стек правого нащадка
if (temp->left)
s.push(temp->left); // Вставляємо в стек лівого нащадка
}
}
// В симетричному і зворотному ітеративному обходах просто міняємо інструкції
// місцями за аналогією з рекурсивними функціями.

Сподіваюся Ви не заснули, і стаття була корисна. Скоро сподіваюся буде продовження банкету статті.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.