З чого складається дерево?

АлгоритмиJunior~2 хв читання

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

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

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

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

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

Обходи дерев

DFS (глибина):

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

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) за пам'яттю стека/черги.
Вибір представлення (покажчики/масив) впливає на константи, але не на асимптотику.

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

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

Premium

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