У попередньому відео ми розглянули абстрактну модель та базову імплементацію для Черги на основі нашого класу Список / List. Сьогодні ми розглянемо наступну важливу структуру даних, яка дуже поширена у діджитал системах Дерево / Tree.
Тож почнемо! До цього ми розглядали переважно тільки лінійні структури даних Список, Стек та Черга - тобто колекція даних зберігаються послідовно. Ми маємо логічний початок/ голову та кінець структури. Ці структури мають свої певні недоліки та переваги, які ми використовуємо для конкретних цілей у наших комп'ютерних системах. Все залежить від того, які дані треба зберігати та що з ними треба робити.
Це як швейцарський ніж - нам необхідно просто вибрати інструмент який вирішить нашу проблему / задачу залежно від:
- ціни операцій
- складності алгоритму
- пам'яті
Так навіщо ж нам тоді ще дерево? - Ця структура вирішує проблему ієрархічних даних.
Наприклад нам треба зберігати організаційну структуру компанії.
Якщо ми перевернем цей графік - то він буде нагадувати дерево.
Але логічна модель завжди починається з кореня:
Цю модель, для цієї структури можна визначити як:
Колекція елементів - Вузлів / Nodes , які зв'язані один з одним для організації ієрархії.
Верхній Вузол називається Корінь / Root. Кожен вузол може зберігати дані та мати посилання / ребро / гілку ( інші терміни link / edge / branch) на наступні вузли - Дочірні вузли / Child Nodes, для яких він є Батьківським вузлом / Parent Node.
Якщо вузли мають спільний Батьківський вузол - вони є Побратимами / Siblings.
Якщо вузол не має нащадків - він має назву Листовий вузол / Leaf Node або просто Лист.
Кожний вузол з нащадками можна розглядати рекурсивно як окреме Піддерево / Subtree, тому дерево є рекурсивною структурою даних. Ми можемо визначити дерево як Корінь + Піддерева.
Більш детальна теорія по всім термінам: https://uk.wikipedia.org/wiki/Дерево
Цікавий факт: Пам'ятаєте ми розглядали Зв'язаний список / LinkedList.
Виявляється це лише окремий випадок дерева. По суті як одна гілка дерева. Отаке!
Дерево такого типу нам ще наробить проблем, але про це трохи далі.
Що ще цікаво, що дерево з N - вузлів має N - 1 ребро. Це дуже легко перевірити - так як усі вузли мають одне посилання крім Кореня / Root.
Також ми можемо визначити:
Глибину дерева для X - як довжина шляху, кількість ребер, від Кореня дерева до вузла Х. Глибина Кореня дорівнює нуль. Глибина вузла D з попереднього малюнку 2.
Висоту дерева для X - як найдовша довжина шляху, кількість ребер, від вузла X до Листа.
Висота Кореня дорівнює 3. Висота вузла D дорівнює 1.
Висота дерева - це і є висота Кореня.
Види дерев:
Дерева бувають різних видів, але найпоширеніший вид - коли дерево має Вузли максимум з двома Дочірніми вузлами. Таке Дерево має назву - Бінарне дерево, надалі розмова буде йти саме про нього. Про інші дерева тут.
Цікаво що бінарне дерево може мати максимум n = 2^0 + 2^1 + 2^2 + … + 2^h = 2^(h+1) - 1 вузлів, де h - це максимальна глибина дерева / кількість рівнів(levels). Звідси виходить що 2^(h+1) = n + 1 => h+1 = log(n+1), тобто висота бінарного дерева дорівнює: log(n+1) - 1 ~ log(n) для збалансованого дерева(не для LinkedList - як у прикладі до цього, для зв'язаного списку висота буде n-1 - це і є найгірший випадок щоб дійти від Кореня до Листа).
Нарешті ми можемо перейти до нашої абстрактної моделі для Бінарного Дерева / Binary Tree, це структура, яка може:
- Зберігати ієрархічні дані у формі Вузлів та Ребер, причому кожен Вузол може мати максимум два Дочірні вузли
- Додавати нові Вузли
- Видаляти Вузли
- Змінювати дані Вузла
- Шукати Вузол по значенню (Бінарне дерево пошуку / Binary Search Tree / BST) та читати дані з нього. Для цього усі значення вузлів для лівого піддерева повинні бути менше значення вузла, а усі значення вузлів для правого піддерева - більше.
На базі цих знань ми можемо перейти до специфікації та імплементації. Але як завжди пропоную розглянути використання цієї структури Дерево у реальному житті:
Зберігання ієрархічних даних - файлова система комп'ютерів це Дерево.
Організація даних для пошуку - Бінарне дерево пошуку - Binary Search Tree. Пам'ятаєте пошук по каталогу у бібліотеці - бінарний пошук.
Спеціальне Дерево яке має назву Trie / Префіксне дерево використовується для перевірки граматики
Маршрутизація мережі
та багато багато іншого.
Перейдемо до специфікації та реалізації.
Визначимо специфікацію абстрактної моделі для структури даних Binary Search Tree / Бінарне Дерево Пошуку / BST:
Імплементація для структури даних Дерево / Tree на базі BST:
Git репозиторій https://github.com/kostrub-online/Computer-Science
Підсумуємо. Сьогодні ми познайомились з дуже важливою ієрархічною структурою даних Дерево / Tree. Розглянули деякі приклади на базі нашої абстрактної моделі та специфікації Бінарного дерева. Зробили імплементацію бінарного пошуку. Обов'язково приділіть увагу цій темі, так як це must have база на технічному інтерв'ю. Спробуйте вирішити задачі самостійно. Якщо ж будуть питання, пишіть в коментарі будемо розбиратись разом. Підписуйтесь на канал щоб не пропустити наступну крайню структуру з відеокурсу - Граф / Graph. Буде весело!
0 Коментарі