Ми читаємо лінійні структури даних, такі як масив, зв’язаний список, стек і черга, у яких усі елементи розташовані послідовним чином. Для різних типів даних використовуються різні структури даних.

Для вибору структури даних враховуються деякі фактори:

Який тип даних потрібно зберігати?: Можливо, певна структура даних найкраще підходить для певного типу даних.Вартість операцій:Якщо ми хочемо мінімізувати витрати на операції для найбільш часто виконуваних операцій. Наприклад, у нас є простий список, у якому ми повинні виконати операцію пошуку; тоді ми можемо створити масив, у якому елементи зберігаються в відсортованому порядку для виконання двійковий пошук . Двійковий пошук працює дуже швидко для простого списку, оскільки він ділить простір пошуку навпіл.Використання пам'яті:Іноді нам потрібна структура даних, яка використовує менше пам’яті.

Дерево також є однією зі структур даних, що представляють ієрархічні дані. Припустімо, що ми хочемо показати співробітників і їхні посади в ієрархічній формі, тоді її можна представити, як показано нижче:

Дерево вище показує ієрархія організації якоїсь компанії. У наведеній вище структурі Джон є генеральний директор компанії, і Джон має двох прямих підлеглих, названих як Стів і Рохан . Стів має трьох прямих підлеглих Лі, Боб, Елла де Стів є менеджером. Боб має двох прямих підлеглих повинен і Емма . Емма має двох прямих підпорядкованих ім Том і Радж . У Тома є один прямий підпорядкований Білл . Ця конкретна логічна структура відома як a дерево . Його будова схоже на справжнє дерево, тому його назвали a дерево . У цій структурі корінь знаходиться вгорі, а її гілки рухаються вниз. Тому можна сказати, що структура даних Tree є ефективним способом зберігання даних в ієрархічній формі.

Давайте розберемося з деякими ключовими моментами структури даних дерева.

рядок внутр

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

Деякі основні терміни, що використовуються в структурі даних дерева.

Розглянемо структуру дерева, яка показана нижче:

У наведеній вище структурі кожен вузол позначено деяким номером. Кожна стрілка, показана на малюнку вище, відома як a посилання між двома вузлами.

Корінь:Кореневий вузол є найвищим вузлом в ієрархії дерева. Іншими словами, кореневий вузол — це вузол, який не має батьківського вузла. У наведеній вище структурі вузол під номером 1 є кореневий вузол дерева. Якщо вузол безпосередньо пов’язаний з якимось іншим вузлом, це буде називатися зв’язком «батько-нащадок».Дочірній вузол:Якщо вузол є нащадком будь-якого вузла, то цей вузол називається дочірнім.Батько:Якщо вузол містить будь-який підвузол, тоді цей вузол вважається батьківським для цього підвузла.рідний брат:Вузли, які мають того самого батька, називаються рідними.Листовий вузол: -Вузол дерева, який не має жодного дочірнього вузла, називається листовим вузлом. Листковий вузол — це самий нижній вузол дерева. У загальному дереві може бути будь-яка кількість листкових вузлів. Листові вузли також можна назвати зовнішніми вузлами.Внутрішні вузли:Вузол має принаймні один дочірній вузол, відомий як an внутрішній Вузол предка: -Попередником вузла є будь-який вузол-попередник на шляху від кореня до цього вузла. Кореневий вузол не має предків. У дереві, показаному на зображенні вище, вузли 1, 2 і 5 є предками вузла 10.Нащадок:Безпосередній наступник даного вузла відомий як нащадок вузла. На наведеному вище малюнку 10 є нащадком вузла 5.

Властивості структури даних Tree

Рекурсивна структура даних:Дерево також відоме як a рекурсивна структура даних . Дерево можна визначити як рекурсивне, оскільки виділений вузол у структурі даних дерева відомий як a кореневий вузол . Кореневий вузол дерева містить посилання на всі корені його піддерев. На малюнку нижче ліве піддерево показано жовтим кольором, а праве піддерево — червоним. Ліве піддерево можна далі розділити на піддерева, показані трьома різними кольорами. Рекурсія означає зменшення чогось самоподібним чином. Отже, ця рекурсивна властивість деревовидної структури даних реалізована в різних програмах.
Кількість ребер:Якщо є n вузлів, тоді буде n-1 ребер. Кожна стрілка в структурі представляє посилання або шлях. Кожен вузол, крім кореневого вузла, матиме принаймні одне вхідне посилання, відоме як край. Для стосунків «батьки-дитина» буде одна ланка.Глибина вузла x:Глибина вузла x може бути визначена як довжина шляху від кореня до вузла x. Одне ребро додає одну одиницю довжини шляху. Отже, глибину вузла x також можна визначити як кількість ребер між кореневим вузлом і вузлом x. Кореневий вузол має 0 глибини.Висота вузла x:Висоту вузла x можна визначити як найдовший шлях від вузла x до листового вузла.

На основі властивостей структури даних дерева дерева класифікуються за різними категоріями.

Реалізація дерева

Структуру даних дерева можна створити шляхом динамічного створення вузлів за допомогою покажчиків. Дерево в пам'яті можна представити, як показано нижче:

Наведений вище малюнок показує представлення структури даних дерева в пам'яті. У наведеній вище структурі вузол містить три поля. Друге поле зберігає дані; перше поле зберігає адресу лівого дочірнього елемента, а третє поле зберігає адресу правого дочірнього елемента.

У програмуванні структуру вузла можна визначити як:

 struct node { int data; struct node *left; struct node *right; } 

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

Аплікації з дерев

Ось приклади застосування дерев:

python друкує до 2 знаків після коми

Зберігання природних ієрархічних даних:Дерева використовуються для зберігання даних в ієрархічній структурі. Наприклад, файлова система. Файлова система, що зберігається на дисководі, файл і папка мають форму природних ієрархічних даних і зберігаються у формі дерев.Упорядкувати дані:Він використовується для організації даних для ефективного вставлення, видалення та пошуку. Наприклад, бінарне дерево має час logN для пошуку елемента.Спробуйте:Це особливий вид дерева, який використовується для зберігання словника. Це швидкий і ефективний спосіб динамічної перевірки орфографії.Купа:Це також деревоподібна структура даних, реалізована за допомогою масивів. Використовується для реалізації пріоритетних черг.B-Tree і B+Tree:B-Tree і B+Tree — це структури даних дерева, які використовуються для реалізації індексування в базах даних.Таблиця маршрутизації:Деревоподібна структура даних також використовується для зберігання даних у таблицях маршрутизації в маршрутизаторах.

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

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

Загальне дерево:Загальне дерево — один із типів деревовидної структури даних. У загальному дереві вузол може мати або 0, або максимум n кількість вузлів. Немає обмежень на ступінь вузла (кількість вузлів, які може містити вузол). Найвищий вузол у загальному дереві відомий як кореневий вузол. Дочірні елементи батьківського вузла називаються піддерева .

Може бути п кількість піддерев у загальному дереві. У загальному дереві піддерева не впорядковані, оскільки вузли піддерева не можна впорядкувати.
Кожне непорожнє дерево має низхідне ребро, і ці ребра з’єднані з вузлами, відомими як дочірні вузли . Кореневий вузол позначено рівнем 0. Вузли, які мають одного батька, називаються брати і сестри . Бінарне дерево :Тут саме двійкове ім’я пропонує два числа, тобто 0 і 1. У двійковому дереві кожен вузол у дереві може мати щонайбільше два дочірніх вузла. Тут максимальний означає, чи має вузол 0 вузлів, 1 вузол або 2 вузли.

Щоб дізнатися більше про бінарне дерево, натисніть посилання нижче:
https://www.javatpoint.com/binary-tree Двійкове дерево пошуку :Двійкове дерево пошуку — це нелінійна структура даних, у якій з’єднаний один вузол п кількість вузлів. Це структура даних на основі вузлів. Вузол може бути представлений у двійковому дереві пошуку за допомогою трьох полів, тобто частини даних, лівого дочірнього та правого дочірнього. Вузол можна з’єднати з двома крайніми дочірніми вузлами в бінарному дереві пошуку, тому вузол містить два покажчики (лівий дочірній і правий дочірній покажчики).
Кожен вузол у лівому піддереві має містити значення, менше значення кореневого вузла, а значення кожного вузла правого піддерева має бути більшим за значення кореневого вузла.

Вузол можна створити за допомогою визначеного користувачем типу даних, відомого як структура, як показано нижче:

 struct node { int data; struct node *left; struct node *right; } 

Вище наведено структуру вузла з трьома полями: поле даних, друге поле — лівий покажчик типу вузла, а третє поле — правий покажчик типу вузла.

Щоб дізнатися більше про бінарне дерево пошуку, натисніть посилання нижче:

https://www.javatpoint.com/binary-search-tree

Дерево AVL

Це один із типів бінарного дерева, або можна сказати, що це варіант бінарного дерева пошуку. Дерево AVL задовольняє властивість бінарне дерево а також з двійкове дерево пошуку . Це самобалансуюче бінарне дерево пошуку, винайдене Адельсон Вельскі Ліндас . Тут самобалансування означає балансування висот лівого піддерева та правого піддерева. Це балансування вимірюється в термінах балансуючий фактор .

Ми можемо розглядати дерево як дерево AVL, якщо дерево підкоряється бінарному дереву пошуку, а також фактору балансу. Коефіцієнт балансування можна визначити як різниця між висотою лівого піддерева і висотою правого піддерева . Значення балансуючого коефіцієнта має бути 0, -1 або 1; отже, кожен вузол у дереві AVL повинен мати значення коефіцієнта балансування 0, -1 або 1.

Щоб дізнатися більше про дерево AVL, натисніть посилання нижче:

https://www.javatpoint.com/avl-tree

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

Червоно-чорне дерево це бінарне дерево пошуку. Обов’язкова умова червоно-чорного дерева полягає в тому, що ми повинні знати про бінарне дерево пошуку. У бінарному дереві пошуку значення лівого піддерева має бути меншим за значення цього вузла, а значення правого піддерева має бути більшим за значення цього вузла. Як відомо, часова складність бінарного пошуку в середньому становить log₂n, найкращий випадок – O(1), а найгірший – O(n).

обробка винятків у java

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

Червоно-чорне дерево це самобалансуюче бінарне дерево пошуку. Дерево AVL також є бінарним деревом пошуку з балансуванням висоти чому нам потрібне червоно-чорне дерево . У дереві AVL ми не знаємо, скільки обертів знадобиться для збалансування дерева, але в червоно-чорному дереві для збалансування дерева потрібно максимум 2 оберти. Він містить один додатковий біт, який представляє або червоний, або чорний колір вузла, щоб забезпечити балансування дерева.

Розкошене дерево

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

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

Дерево Splay є збалансованим деревом, але його не можна вважати деревом із збалансованою висотою, оскільки після кожної операції виконується обертання, що призводить до збалансованого дерева.

Треап

Структура даних Treap походить від структури даних Tree і Heap. Таким чином, він включає в себе властивості обох структур даних Tree і Heap. У бінарному дереві пошуку кожен вузол лівого піддерева має бути рівним або меншим за значення кореневого вузла, а кожен вузол правого піддерева має бути рівним або більшим за значення кореневого вузла. У структурі даних купи і праве, і ліве піддерева містять більші ключі, ніж кореневі; отже, можна сказати, що кореневий вузол містить найменше значення.

У структурі даних treap кожен вузол має обидва ключ і пріоритет де ключ виводиться з бінарного дерева пошуку, а пріоритет – зі структури даних купи.

The Треап Структура даних має дві властивості, наведені нижче:

• Правий дочірній елемент вузла>= поточний вузол і лівий дочірній елемент вузла<=current node (binary tree)< li>
• Діти будь-якого піддерева мають бути більшими за вузол (купу)

B-дерево

В-дерево є збалансованим м-шлях дерево де м визначає порядок дерева. Досі ми читали, що вузол містить лише один ключ, але b-дерево може мати більше одного ключа та більше 2 дочірніх елементів. Він завжди підтримує відсортовані дані. У бінарному дереві можливо, що листові вузли можуть бути на різних рівнях, але в b-дереві всі листові вузли мають бути на одному рівні.

Якщо порядок m, то вузол має такі властивості:

• Кожен вузол b-дерева може мати максимум м дітей
• Для мінімальних дочірніх вузлів листовий вузол має 0 дочірніх елементів, кореневий вузол має мінімум 2 дочірніх вузла, а внутрішній вузол має мінімальну межу m/2 дочірніх елементів. Наприклад, значення m дорівнює 5, що означає, що вузол може мати 5 дітей, а внутрішні вузли можуть містити максимум 3 дітей.
• Кожен вузол має максимум (m-1) ключів.

Кореневий вузол має містити принаймні 1 ключ, а всі інші вузли мають містити щонайменше стеля м/2 мінус 1 ключі.