✅ Типи дерев у структурі даних - Що таке дерева з перевагами

Вступ до дерев у структурі даних

Вступ до дерев у структурі даних

Перш ніж зрозуміти типи дерев у структурі даних, спочатку ми вивчимо дерева в структурі даних. Дерево в комп’ютерному полі також називають деревом реального світу, однак різниця між реальним світом і деревом обчислювальних полів полягає в тому, що воно візуалізується як догори дном, так і корінь зверху, а гілка від кореня до листя дерева. Серед різних додатків у реальному світі використовується структура даних дерева, оскільки вона може демонструвати зв’язки між різними вузлами з ієрархією батько-дитина. Через це її називають ієрархічною структурою даних. Він найпопулярніший для спрощення та прискорення пошуку та сортування. Він розглядається як одна з найсильніших і найсучасніших структур даних. Дерево - це представлення нелінійної структури даних. Дерево можна показати, використовуючи різні визначені користувачем або примітивні типи даних. Ми можемо використовувати масиви, списки, пов’язані з класами, або інші види структур даних для реалізації дерева. Це група вузлів, які взаємопов'язані. Вузли прикріплені до країв, щоб продемонструвати взаємозв'язок.

Відносини на дереві: На наведеній діаграмі Р - корінь дерева, також P - Батько Q, R і S. Q - дитина П. Звідси Q, R і S - побратими. В той час, як P є батьківським вихователем A, B, C, D та E.

Що таке дерева?

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

Властивості дерева: Кожне дерево має певний кореневий вузол. Кожен вузол дерева може перетинатися кореневим вузлом. Його називають корінцем, так як дерево було єдиним коренем. У кожної дитини є лише один батько, але батько може мати багато дітей.

Типи дерев у структурі даних

Нижче наведено типи дерев у структурі даних:

1. Загальне дерево

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

2. Бінарне дерево

Бінарне дерево - це дерево, в якому можна знайти більшість двох дітей для кожного з батьків. Діти відомі як ліва дитина і права дитина. Це популярніше, ніж більшість інших дерев. Коли певні обмеження та характеристики застосовуються у бінарному дереві, також застосовується ряд інших, таких як дерево AVL, BST (дерево бінарного пошуку), дерево RBT тощо. Коли ми рухаємось вперед, ми детально пояснимо всі ці стилі.

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

Бінарне дерево пошуку (BST) - це бінарне розширення дерева з кількома необов'язковими обмеженнями. Ліве дочірнє значення вузла повинно бути в BST менше або рівне батьківському значенню, а праве дочірнє значення завжди повинно бути більше або рівне батьківському значенню. Ця властивість Binary Search Tree робить його ідеальним для пошукових операцій, оскільки ми можемо точно визначити на кожному вузлі, чи є значення в лівому або правому під дереві. Ось чому названо Дерево пошуку.

4. AVL дерево

Дерево AVL - це самоврівноважене бінарне дерево пошуку. Від імені винахідників Адельсона-Велші та Ландіса названа назва AVL. Це було перше дерево, яке динамічно балансувало. Коефіцієнт врівноваження розподіляється для кожного вузла дерева AVL, виходячи з того, чи дерево врівноважене чи ні. Висота діток у вузла становить не більше 1. Виноградна лоза AVL. У дереві AVL правильний коефіцієнт балансу - 1, 0 і -1. Якщо у дерева є новий вузол, він буде повернутий для забезпечення збалансованості дерева. Потім він буде обертатися. Поширені операції, такі як перегляд, вставка та видалення, займають O (log n) час у дереві AVL. Він здебільшого застосовується під час роботи з операціями пошуку.

5. Червоно-чорне дерево

Ще один різновид дерева з автоматичним балансуванням - червоно-чорний. Червоно-чорна назва дається тому, що червоно-чорне дерево має червоний або чорний колір, пофарбований на кожному вузлі відповідно до властивостей червоно-чорного дерева. Він підтримує рівновагу лісу. Незважаючи на те, що це дерево не є повністю збалансованим деревом, операція пошуку займає лише час O (log n). Коли нові вузли будуть додані до Червоно-Чорного дерева, то вузли знову повертатимуться для підтримки властивостей Червоно-Чорного дерева.

6. Н-арве дерево

Максимальна кількість дітей цього дерева, які можуть мати вузол, - N. Бінарне дерево - це дворічне дерево, як мінімум 2 дитини у кожному двійковому вузлі дерева. Повне дерево N-арі - це дерево, де діти вузла або 0, або N.

Переваги Дерева

Тепер ми розберемося з Перевагами дерева:

Дерево відображається в даних структурних зв'язків.
Дерево використовується для ієрархії.
Він пропонує ефективну процедуру пошуку та вставки.
Дерева гнучкі. Це дозволяє перемежовувати підрядчики з мінімальними зусиллями.

Висновок - Типи дерев у структурі даних

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

Типи дерев у структурі даних - Що таке дерева з перевагами