Що таке висота дерева?

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

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

Висота дерева - це довжина (у ребрах) найдовшого шляху від кореня до листа.

Дерево з одного вузла: висота 0 (якщо рахуємо в ребрах).
Порожнє дерево: висота -1 (якщо рахуємо в ребрах).
Іноді висоту рахують у вузлах: тоді в одного вузла - 1, у порожнього - 0.

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

Визначення і домовленості

Є дві поширені домовленості про те, як рахувати висоту:

У ребрах (на практиці зустрічається дуже часто): висота - це кількість ребер у найдовшому шляху від кореня до листа. Тоді: порожнє дерево -1; лист 0; дерево з одного вузла 0.
У вузлах: висота - це кількість вузлів у цьому шляху. Тоді: порожнє дерево 0; лист 1; дерево з одного вузла 1.

Переклад між домовленостями: h_вузли = h_ребра + 1; h_ребра = h_вузли - 1. Далі за замовчуванням використовуємо визначення в ребрах.

Пов'язані терміни, щоб не плутати

Глибина вузла: кількість ребер від кореня до цього вузла.
Рівень вузла: іноді те саме, що глибина (але можуть рахувати у вузлах). Уточнюйте на співбесіді.
Висота вузла: висота піддерева з коренем у цьому вузлі (аналогічно висоті дерева). Висота дерева = висота кореневого вузла.

Приклади дерев

text

Приклад 1 (у ребрах):

A
├─ B
│  └─ D
└─ C

Найдовший шлях: A → B → D (2 ребра), отже висота = 2.

Якщо рахувати у вузлах, висота була б 3.

text

Приклад 2 (ланцюжок із 4 вузлів):

1
└─ 2
   └─ 3
      └─ 4

Найдовший шлях містить 3 ребра, отже висота = 3.

Формула і властивості

Рекурентне визначення (у ребрах): h(∅) = -1; h(лист) = 0; h(v) = 1 + max(h(дітей v)). Якщо дітей немає - лист.
Межі для дерева з n вузлів: 0 ≤ h ≤ n - 1 (у ребрах). Мінімальна висота досягається у «майже повного» дерева, максимальна - у ланцюжка.
Для майже повного бінарного дерева: h ≈ ⌊log2 n⌋ (у ребрах). Для ланцюжка: h = n - 1.
Переклад домовленостей: h_вузли = h_ребра + 1; h_ребра = h_вузли - 1.

Як порахувати на практиці

Рекурсивний DFS (бінарне дерево, JS)

javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// Висота в ребрах: порожнє дерево -1, лист 0
function heightBinary(root) {
  if (root === null) return -1;
  return 1 + Math.max(heightBinary(root.left), heightBinary(root.right));
}

// Приклад
const root = new TreeNode('A',
  new TreeNode('B', new TreeNode('D'), null),
  new TreeNode('C')
);
console.log(heightBinary(root)); // 2

Рекурсивний DFS (загальне N-арне дерево, JS)

javascript

class NNode {
  constructor(val, children = []) {
    this.val = val;
    this.children = children;
  }
}

function heightN(root) {
  if (!root) return -1;
  let maxChild = -1;
  for (const c of root.children) {
    maxChild = Math.max(maxChild, heightN(c));
  }
  return maxChild + 1;
}

// Приклад
const tree = new NNode('A', [
  new NNode('B', [new NNode('D')]),
  new NNode('C')
]);
console.log(heightN(tree)); // 2

Ітеративний BFS по рівнях (бінарне дерево, JS)

javascript

function heightBFS(root) {
  if (!root) return -1;
  let h = -1;
  const queue = [root];
  for (let i = 0; i < queue.length; ) {
    const levelSize = queue.length - i;
    for (let k = 0; k < levelSize; k++) {
      const node = queue[i++];
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    h++;
  }
  return h;
}

// Для N-арного дерева додайте: if (node.children) for (const c of node.children) queue.push(c);

Складність: час O(n) для будь-якого коректного обходу (кожен вузол відвідується один раз). Пам'ять: O(h) для рекурсивного DFS (глибина стека), O(w) для BFS (максимум вузлів на рівні), де h - висота, w - ширина дерева.

Де використовується і навіщо знати

Самобалансувальні дерева пошуку (AVL, червоно-чорні): підтримують висоту O(log n) для швидкого пошуку/вставки/видалення.
Купи/піраміди: висота ≈ ⌊log2 n⌋, що дає операції за O(log n).
B-дерева та їхні варіації (індекси в БД): висота O(log_t n), де t - мінімальна степінь.
Tries/префіксні дерева: висота приблизно дорівнює довжині максимального ключа.

Типові питання на співбесіді

Чим відрізняється висота від глибини? Висота - довжина максимального шляху вниз від вузла; глибина - відстань від кореня до вузла.
Яка висота у порожнього дерева? Залежить від домовленості: -1 (у ребрах) або 0 (у вузлах). Уточнюйте і дотримуйтесь однієї.
Яка висота у дерева з одного вузла? 0 у ребрах, 1 у вузлах.
Як швидко порахувати висоту? Будь-який обхід (DFS або BFS) за O(n), де n - кількість вузлів.
Як пов'язані висота і збалансованість? Чим менша висота при фіксованому n, тим дерево «збалансованіше»; ідеальна мета - O(log n).

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

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

Premium

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