Найпростішою та найбільш зрозумілою структурою даних є звичайний масив. Про те, яким чином влаштовано масиви, питання виникають рідко — чого не можна сказати про такий тип структури даних, як дерева. Пропонуємо розібратися з деревами — нелінійною структурою, де дані впорядковано за ієрархією.
Кілька слів про ієрархію
Мабуть, одним з прикладів ієрархій, з яким багато людей стикаються щодня, є каталоги в операційній системі. У вашому комп’ютері завжди є кореневий каталог, наприклад, кореневий каталог на Linux або локальний диск на Windows. У кожному з цих кореневих каталогів знаходяться папки, всередині яких також є папки, всередині яких теж можуть бути папки; і такий ланцюжок може продовжуватися нескінченно. Хоча так було не завжди і довжина шляху у Windows за замовчуванням обмежена 260 символами. Приклад каталогу можна побачити на малюнку нижче.
Застосувавши трішечки уяви, на цій картинці справді можна побачити перевернуте дерево.
Приклад каталогу
Яким чином влаштовані дерева?
Розглянемо основні елементи дерева на прикладі з малюнка вище.
Дерево являє собою набір об’єктів, які називають вузлами. Кожен вузол містить значення або дані, і може мати (або не мати) дочірні вузли. Вузли, у яких немає дочірніх вузлів, називають листям.
На малюнку вузлами є всі представлені папки, при цьому листям є тільки ті ланки, всередині яких немає папок, наприклад «lib», «disc», «mail», «X11» і т. п.
Всі вузли дерев з’єднані ребрами; ребра показують зв’язки між вузлами.
На прикладі з малюнку, за допомогою ребер ми можемо переміщуватися каталогом і розуміти, що знаходиться всередині кожної папки. Також від кожної папки по ребрах можна повернутися в корінь.
На верхівці дерева знаходиться корінь — такий вузол, у якого немає батьківських вузлів, але при цьому є один чи більше дочірніх вузлів.
В нашому випадку коренем є каталог «/».
Основні елементи дерева
Може виникнути питання: чому саме корінь знаходить на верхівці? Відповідь проста: ми — програмісти, ми так бачимо.
Характеристики дерева
Є дві важливі характеристики дерева, які потрібно знати при роботі з ним:
- Висота дерева.
- Глибина вузла.
Висота дерева — це довжина найдовшого шляху до листя. Глибина вузла — це відстань від вузла до його кореня.
Для дерева, наведеного вище, висота дерева буде дорівнювати трьом. Глибина вузла, наприклад «local», дорівнюватиме двом.
У чому перевага дерев?
Перевага дерев полягає в тому, що, не дивлячись на складність їх формування, всі операції з ними є дуже простими. Так, скажімо, операції вставки, видалення та пошуку елементів виконуються в тисячі, або навіть у десятки тисяч разів швидше ніж аналогічні операції з невпорядкованим масивом. Більш точними цифрами для кожного виду дерев поділимося в наступних матеріалах.
А що взагалі робити з деревами?
Галузі застосування дерев дуже широкі й різноманітні, до того ж не обмежуються тільки програмуванням. У більшості випадків, саме завдяки використанню деревоподібних структур вдається значно прискорити роботу з даними, і, в багатьох базах даних, рішення, засновані на застососувані дерев, працюють більш ніж успішно.
Більше корисного про дерева ми розповімо у наступних статтях!
