Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що таке висота дерева?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

- Дерево з одного вузла: висота 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).

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати753 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.