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

Покращити цю статтю

Допрацюйте відповідь до «З чого складається дерево?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

## Розгорнута відповідь

### Базові елементи дерева

- Вузол (вершина): зберігає значення/дані і посилання на дочірні вузли.
- Ребра (зв'язки): з'єднують вузли; спрямовані від батька до дитини.
- Корінь: єдиний вузол без батька.
- Батько і дитина: відношення між вузлом і його безпосереднім нащадком.
- Брати/сестри: діти одного й того самого батька.
- Лист: вузол без дітей. Внутрішній вузол: вузол щонайменше з однією дитиною.
- Піддерево: дерево, коренем якого є деякий вузол і всі його нащадки.
- Шлях: послідовність вузлів, з'єднаних ребрами. Довжина шляху - кількість ребер.
- Рівень/глибина: відстань (у ребрах) від кореня до вузла. Рівень кореня = 0.
- Висота вузла/дерева: максимальна довжина шляху від вузла до листа; висота дерева - висота кореня.
- Степінь вузла: кількість його дітей (фактор розгалуження). Розмір дерева: кількість вузлів.

### Види дерев (часті для співбесід)

- Загальне (N-арне) дерево: у вузла довільна кількість дітей.
- Бінарне дерево: у кожного вузла не більше двох дітей (left/right).
- BST (бінарне дерево пошуку): left < node < right за ключем, операції в середньому O(log n).
- Збалансовані дерева: AVL, червоно-чорні - підтримують висоту O(log n).
- Купи (Heap): мін-/макс-, підтримують вилучення екстремуму за O(log n), представляються масивом.
- Префіксне дерево (Trie): зберігає рядки за символами, ефективне для автодоповнення/пошуку за префіксом.
- B-/B+-дерева: оптимізовані для дискової пам'яті; основа індексів у СУБД.

### Представлення в пам'яті

- Вузли зі списком дітей: кожен вузол зберігає масив/список посилань на нащадків (підходить для N-арних дерев).
- Через масив (для повних бінарних дерев/куп): індекси i → діти 2i+1 і 2i+2, батько ⌊(i-1)/2⌋.
- Списки суміжності/таблиці: коли дерево зберігається як окремий випадок графа.

### Обходи дерев

1. DFS (глибина):
  - Preorder (NLR): спочатку вузол, потім ліве/діти, потім праве.
  - Inorder (LNR): для BST дає відсортований порядок.
  - Postorder (LRN): спочатку діти, потім вузол (зручно для видалення/підрахунку).
2. BFS (у ширину, по рівнях): відвідування вузлів по рівнях згори вниз.

### Приклади коду

N-арне дерево: побудова, обхід DFS (preorder) і BFS.

```
class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
}

// Побудуємо дерево:
//        A
//      /   \
//     B     C
//    / \     \
//   D   E     F
const root = new TreeNode("A");
const b = new TreeNode("B");
const c = new TreeNode("C");
root.children.push(b, c);
b.children.push(new TreeNode("D"), new TreeNode("E"));
c.children.push(new TreeNode("F"));

function dfsPre(node, visit = console.log) {
  if (!node) return;
  visit(node.value);
  for (const child of node.children) dfsPre(child, visit);
}

function bfs(root, visit = console.log) {
  if (!root) return;
  const q = [root];
  while (q.length) {
    const n = q.shift();
    visit(n.value);
    for (const child of n.children) q.push(child);
  }
}

dfsPre(root); // A B D E C F
bfs(root);    // A B C D E F
```

Бінарне дерево пошуку: вставка і inorder-обхід, що дає відсортований вивід.

```
class BNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function insertBST(node, val) {
  if (!node) return new BNode(val);
  if (val < node.val) node.left = insertBST(node.left, val);
  else node.right = insertBST(node.right, val);
  return node;
}

function inorder(node, visit = console.log) {
  if (!node) return;
  inorder(node.left, visit);
  visit(node.val);
  inorder(node.right, visit);
}

let tree = null;
[7, 3, 9, 1, 5, 8, 10].forEach(v => (tree = insertBST(tree, v)));

inorder(tree); // 1 3 5 7 8 9 10
```

### Застосування у веброзробці

- DOM - дерево вузлів документа, рендер і події поширюються по дереву (capturing/bubbling).
- AST - абстрактне синтаксичне дерево в компіляторах/бандлерах (Babel, TypeScript), трансформації по дереву.
- Virtual DOM/дерева компонентів (React, Vue) - діфф і реконсиляція по дереву.
- Роутинг і пошук: префіксні дерева, tries для маршрутів і автодоповнення.
- Індекси БД (B-/B+-дерева), файлові системи - прискорюють доступ до даних.

### Ключові властивості і складності

- Пошук/вставка/видалення в дереві зазвичай залежать від висоти h: O(h). У збалансованих - O(log n), у вироджених (ланцюжок) - O(n).
- Обхід дерева відвідує кожен вузол один раз: O(n) за часом, O(h) за пам'яттю стека/черги.
- Вибір представлення (покажчики/масив) впливає на константи, але не на асимптотику.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати689 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.