Tree (Дерево)

Иерархическая структура данных из узлов, где каждый узел имеет родителя и потомков.

Зачем нужно

• Моделирование иерархий (DOM, файловая система, меню)
• Быстрый поиск и сортировка (BST: O(log n))
• Основа для алгоритмов парсинга (AST)

Где используется

• DOM-дерево в браузере, файловые системы, базы данных (B-tree), JSON/XML парсинг

Терминология

Термин	Значение
Root	Корень -- верхний узел
Node	Узел с данными
Leaf	Лист -- узел без потомков
Depth	Глубина -- расстояние от корня
Height	Высота -- макс. глубина дерева

Бинарное дерево поиска (BST)

class TreeNode<T> {
  value: T;
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  constructor(value: T) { this.value = value; }
}

class BST {
  root: TreeNode<number> | null = null;

  insert(val: number) {
    const node = new TreeNode(val);
    if (!this.root) { this.root = node; return; }
    let curr = this.root;
    while (true) {
      if (val < curr.value) {
        if (!curr.left) { curr.left = node; return; }
        curr = curr.left;
      } else {
        if (!curr.right) { curr.right = node; return; }
        curr = curr.right;
      }
    }
  }

  search(val: number): boolean {
    let curr = this.root;
    while (curr) {
      if (val === curr.value) return true;
      curr = val < curr.value ? curr.left : curr.right;
    }
    return false;
  }
}

Обходы дерева

// In-order (левый → корень → правый) — сортированный порядок
function inOrder(node: TreeNode<number> | null): number {
  if (!node) return ;
  return [...inOrder(node.left), node.value, ...inOrder(node.right)];
}

// Pre-order (корень → левый → правый)
// Post-order (левый → правый → корень)
// BFS — обход в ширину (через очередь)

Сложность BST

Операция	Среднее	Худшее
Поиск	O(log n)	O(n)
Вставка	O(log n)	O(n)
Удаление	O(log n)	O(n)

Связанные темы

• Graph
• Рекурсия

Ресурсы

• Visualgo - BST