Skip to main content

Що таке дерево як структура даних?

Структури данихJunior~1 хв читання
Запропонувати правку

Дерево - це ієрархічна структура даних, у якій кожен елемент (який називають вузлом) може мати дочірні вузли, але лише одного батька (крім кореня).

Основні поняття

  • Корінь (root) - верхній вузол, який не має батька.
  • Нащадки (children) - вузли, що виходять із батьківського вузла.
  • Листки (leaves) - вузли без нащадків.
  • Ребро (edge) - зв'язок між батьківським і дочірнім вузлом.
  • Висота дерева - довжина найдовшого шляху від кореня до листка.

Суть ідеї

Дерево зберігає дані у вигляді ієрархії, а не в лінійному порядку (як список чи черга).

Приклад

javascript
A ← корінь / \ B C ← нащадки A / \ D E ← листки

Типові види дерев

  • Двійкове дерево - у кожного вузла не більше двох нащадків.
  • Дерево пошуку (BST) - лівий нащадок < батька < правого нащадка.
  • Префіксне (Trie) - використовується для зберігання рядків і автодоповнення.
  • AVL, червоно-чорне дерево - збалансовані варіанти для прискорення пошуку.

Підсумок

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

Коротка відповідь

Для співбесіди
Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

Запропонувати правку