re:re:actable
Урок 013 минуты чтения

Что такое tree?

На этой странице
Кратко

Tree - иерархическая структура данных из узлов и связей parent-child. У дерева есть root, листья, высота, глубина и поддеревья. На собеседованиях чаще всего встречаются binary tree, BST и обходы DFS/BFS.

Вопрос

Что такое tree и какие термины деревьев нужно знать?

Как выглядит дерево

Пример - структура папок или DOM-дерево:

              A          <- root, depth 0
            /   \
           B     C       <- depth 1; B и C - дети A, A - их parent
          / \     \
         D   E     F     <- depth 2; D, E, F - листья (leaf)
  • Поддерево с корнем B - это B, D, E.
  • Высота дерева - 2: самый длинный путь от корня до листа проходит 2 ребра (A -> B -> D).
  • Глубина E - 2, глубина C - 1.
  • В дереве нет циклов, и до каждого узла ведет ровно один путь от корня.

Базовые термины

  • Root - корневой узел.
  • Parent - родитель.
  • Child - потомок.
  • Leaf - узел без детей.
  • Edge - связь между узлами.
  • Depth - расстояние от root.
  • Height - максимальное расстояние до листа.
  • Subtree - поддерево.

Binary tree

type TreeNode<T> = {
  value: T
  left: TreeNode<T> | null
  right: TreeNode<T> | null
}

У каждого узла максимум два ребенка.

Пример обхода

function sum(root: TreeNode<number> | null): number {
  if (!root) return 0
  return root.value + sum(root.left) + sum(root.right)
}

Time O(n), потому что посещаем каждый узел.

Space O(h), где h - высота дерева: одновременно в call stack лежат вызовы только для одного пути от корня вниз.

Как разворачивается рекурсия для маленького дерева 1 с детьми 2 и 3:

sum(1) = 1 + sum(2) + sum(3)
sum(2) = 2 + sum(null) + sum(null) = 2 + 0 + 0 = 2
sum(3) = 3 + 0 + 0 = 3
sum(1) = 1 + 2 + 3 = 6

Узел не знает сумму всего дерева - он просит детей посчитать свои поддеревья и складывает ответы. Так устроены почти все рекурсивные задачи на деревьях.

Что отвечать на собеседовании?

Tree - связная ациклическая иерархическая структура. В отличие от массива, данные организованы не линейно, а через parent-child отношения. Для binary tree каждый узел имеет максимум двух детей. Основные операции на интервью - обход, поиск глубины, проверка баланса, lowest common ancestor, работа с BST.

Что важно помнить: частые ошибки

  • Путать depth и height.
  • Забывать root = null.
  • Не учитывать recursion stack.
  • Считать все деревья balanced.
  • Путать tree и graph.

Мини-шпаргалка

  • Root - начало.
  • Leaf - нет детей.
  • Binary tree - left/right.
  • Height важна для complexity.
  • DFS часто рекурсивный.
  • BFS идет по уровням.

Документация

Wikipedia: Tree (data structure).

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам