У цьому підручнику ви дізнаєтесь про структуру деревних даних. Крім того, ви дізнаєтесь про різні типи дерев та термінологію, що використовується в дереві.
Дерево - це нелінійна ієрархічна структура даних, що складається з вузлів, з'єднаних ребрами.
Дерево
Чому деревоподібна структура даних?
Інші структури даних, такі як масиви, зв’язаний список, стек та черга, є лінійними структурами даних, які зберігають дані послідовно. Для того, щоб виконати будь-яку операцію в лінійній структурі даних, складність часу збільшується зі збільшенням обсягу даних. Але це неприйнятно в сучасному обчислювальному світі.
Різні деревоподібні структури даних забезпечують швидший та простіший доступ до даних, оскільки це нелінійна структура даних.
Деревознавчі термінології
Вузол
Вузол - це сутність, що містить ключ або значення та вказівники на його дочірні вузли.
Останні вузли кожного шляху називаються листовими вузлами або зовнішніми вузлами , які не містять посилання / вказівника на дочірні вузли.
Вузол, що має принаймні дочірній вузол, називається внутрішнім вузлом .
Край
Це зв'язок між будь-якими двома вузлами.
Вузли та краї дерева
Корінь
Це найвищий вузол дерева.
Висота вузла
Висота вузла - це кількість ребер від вузла до найглибшого листка (тобто. Найдовший шлях від вузла до листового вузла).
Глибина вузла
Глибина вузла - це кількість ребер від кореня до вузла.
Висота дерева
Висота дерева - це висота кореневого вузла або глибина найглибшого вузла.
Висота і глибина кожного вузла в дереві
Ступінь Вузла
Ступінь вузла - це загальна кількість гілок цього вузла.
Ліс
Колекція непересічних дерев називається лісом.
Створення лісу з дерева
Ви можете створити ліс, обрізавши корінь дерева.
Типи дерев
- Бінарне дерево
- Бінарне дерево пошуку
- Дерево AVL
- B-Tree
Обхід дерева
Для того, щоб виконати будь-яку операцію на дереві, вам потрібно дістатися до конкретного вузла. Алгоритм обходу дерева допомагає відвідати необхідний вузол у дереві.
Щоб дізнатись більше, відвідайте обхід дерева.
Застосування дерев
- Бінарні дерева пошуку (BST) використовуються для швидкої перевірки наявності елемента в наборі чи ні.
- Купи - це різновид дерева, яке використовується для сортування купи.
- Модифікована версія дерева під назвою Tries використовується в сучасних маршрутизаторах для зберігання інформації про маршрутизацію.
- У більшості популярних баз даних використовуються B-Trees і T-Trees, які є варіантами деревної структури, про яку ми дізналися вище, для зберігання їх даних
- Компілятори використовують дерево синтаксису для перевірки синтаксису кожної написаної вами програми.
