Що таке вузол (node)?

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

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

Вузол (node) - це елемент структури даних, найчастіше дерева, який зберігає значення і посилання на інші вузли. У веброзробці найчастіше йдеться про DOM-вузол (інтерфейс Node) - базовий будівельний блок HTML-документа (елементи, текст, коментарі тощо). Також вузлами називають елементи графів і AST. Не плутайте з платформою Node.js - це середовище виконання JavaScript, а не «вузол» як елемент структури.

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

1) Базова модель вузла

Дані (value/payload).
Зв'язки (references/edges) з іншими вузлами: parent, children, next/prev sibling (у деревах), сусіди (у графах).
Поняття: корінь, нащадок, лист (немає дітей), степінь, глибина, висота, шлях.

2) Вузли в DOM

Node - базовий інтерфейс. Окремі випадки: Element (HTMLElement, SVGElement), Text, Comment, Document, DocumentFragment.
Ключові властивості: nodeType, nodeName, parentNode/parentElement, childNodes (NodeList), firstChild/lastChild, nextSibling/previousSibling.
Маніпуляції: append/appendChild, prepend, before/after, replaceWith, remove, cloneNode, insertBefore (застарілий стиль API, але потрібен для сумісності).
NodeList відрізняється від HTMLCollection: NodeList може включати текст/коментарі, буває live або static залежно від методу.

// Приклад: створення і робота з DOM-вузлами
const div = document.createElement('div'); // Element (вузол-елемент)
const text = document.createTextNode('Hello'); // Text (текстовий вузол)
const comment = document.createComment('note'); // Comment (коментар)

// Побудуємо невелике дерево
div.append(text);
div.before(comment);

document.body.append(div);

console.log(div.nodeType); // 1 (ELEMENT_NODE)
console.log(text.nodeType); // 3 (TEXT_NODE)
console.log(comment.nodeType); // 8 (COMMENT_NODE)

// Навігація по вузлах
console.log(div.parentNode === document.body); // true
console.log(div.firstChild === text); // true
console.log(comment.nextSibling === div); // true

// Заміна і видалення
const span = document.createElement('span');
span.textContent = 'World';
div.replaceWith(span); // замінили div цілком на span
span.remove();

3) Вузли в класичних структурах (дерева/графи)

Вузол зберігає значення і посилання на суміжні вузли. На основі вузлів будуються зв'язні списки, дерева (зокрема бінарні), графи.

// Вузол бінарного дерева і базові обходи
class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

// DFS (прямий обхід): O(n)
function preorder(node, visit) {
  if (!node) return;
  visit(node);
  preorder(node.left, visit);
  preorder(node.right, visit);
}

// BFS по дереву: O(n)
function bfs(root, visit) {
  const q = [];
  if (root) q.push(root);
  while (q.length) {
    const curr = q.shift();
    visit(curr);
    if (curr.left) q.push(curr.left);
    if (curr.right) q.push(curr.right);
  }
}

const tree = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3)
);

preorder(tree, n => console.log('DFS:', n.value));
bfs(tree, n => console.log('BFS:', n.value));

// Вузли графа і пошук у ширину
function bfsGraph(adj, start) {
  const visited = new Set([start]);
  const q = [start];
  while (q.length) {
    const v = q.shift();
    console.log('visit', v);
    for (const u of adj[v] || []) {
      if (!visited.has(u)) {
        visited.add(u);
        q.push(u);
      }
    }
  }
}

const adj = {
  A: ['B', 'C'],
  B: ['D'],
  C: ['D', 'E'],
  D: [],
  E: []
};

bfsGraph(adj, 'A');

4) Вузли в AST (абстрактне синтаксичне дерево)

Компілятори і лінтери представляють код як дерево вузлів (типи: Program, FunctionDeclaration, Identifier, Literal тощо). Вузол AST містить тип, діапазони/позиції і нащадків. Це база для трансформацій і аналізу коду.

// Приклад вузла AST у дусі ESTree (спрощено)
const ast = {
  type: 'BinaryExpression',
  operator: '+',
  left: { type: 'Literal', value: 2 },
  right: { type: 'Identifier', name: 'x' }
};

5) Операції та складність

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

6) Часті питання і тонкощі на співбесідах

Чим Element відрізняється від Node? Відповідь: Element - окремий випадок Node з атрибутами/класами/стилями; Node включає Text/Comment/Document та ін.
Чим NodeList відрізняється від масивів? Ітерований, але не всі методи Array; часто статичний (querySelectorAll) проти «живого» HTMLCollection (getElementsBy...).
Чому краще мінімізувати зміни великого піддерева DOM? Тому що кожен апдейт може тригерити перерахунок стилів/лейауту і перемальовування.
Не плутати «node» як елемент структури з Node.js - середовищем виконання JS на сервері.

Коротка пам'ятка

Вузол = дані + зв'язки.
У вебі «вузол» найчастіше про DOM Node (Element/Text/Comment/Document).
Обходи: DFS і BFS; складність O(n).
Не плутайте з Node.js.

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

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

Premium

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