Що таке бінарне дерево?

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

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

Бінарне дерево - це структура даних, у якій кожен вузол має не більше двох дітей: лівого і правого. Воно є основою для цілого ряду структур (двійкове дерево пошуку, купа), використовується для зберігання ієрархій і ефективного виконання операцій пошуку/вставки/видалення за дотримання додаткових властивостей.

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

Визначення та інтуїція

Бінарне (двійкове) дерево - це зв'язна ациклічна ієрархічна структура з вузлів, де у кожного вузла не більше двох нащадків. Кожен вузол зберігає значення і посилання на лівого і правого нащадка. У загальному випадку бінарне дерево не накладає обмежень на порядок значень - порядок задається лише у спеціалізованих варіантах (наприклад, у двійковому дереві пошуку).

Терміни і властивості

Вузол, корінь, ребро, лист: базові частини дерева. Лист - вузол без дітей.
Глибина вузла - відстань (кількість ребер) від кореня; висота вузла - довжина максимального шляху до листа; висота дерева - висота кореня; розмір - кількість вузлів.
Класифікації: ідеальне (perfect) - усі рівні повністю заповнені; повне (complete) - усі рівні, крім останнього, повні, останній заповнюється зліва направо; строге (full) - у кожного вузла або 0, або 2 дитини; збалансоване - висота O(log n).
Спеціалізації: двійкове дерево пошуку (BST) - усі ключі в лівому піддереві < ключ вузла < усі ключі в правому піддереві; купа (heap) - у батька значення не менше/не більше (max/min) значень дітей, але відносний порядок лівого/правого не визначений.
Представлення в пам'яті: покажчикове (вузли з посиланнями) - універсальне; масивне - ефективне для повних/майже повних дерев: для індексу i: left = 2i + 1, right = 2i + 2, parent = ⌊(i - 1) / 2⌋.

Операції і обходи

Preorder (N-L-R): спочатку вузол, потім ліве і праве піддерево. Корисно для копіювання/серіалізації.
Inorder (L-N-R): ліве, вузол, праве. У BST дає відсортовану послідовність.
Postorder (L-R-N): ліве, праве, вузол. Корисно для видалення/обчислення виразів (дерева виразів).
Level-order (BFS): по рівнях зліва направо. Підходить для задач, де важлива «ширина» (наприклад, пошук найкоротшого шляху по ребрах однакової вартості).

Приклад: побудова дерева і обходи (JavaScript)

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

// Приклад дерева (також коректне BST):
//         8
//       /   \
//      3     10
//     / \      \
//    1   6      14
//       / \    /
//      4   7  13
const root = new Node(
  8,
  new Node(3, new Node(1), new Node(6, new Node(4), new Node(7))),
  new Node(10, null, new Node(14, new Node(13), null))
);

function preorder(node, res = []) {
  if (!node) return res;
  res.push(node.val);
  preorder(node.left, res);
  preorder(node.right, res);
  return res;
}

function inorder(node, res = []) {
  if (!node) return res;
  inorder(node.left, res);
  res.push(node.val);
  inorder(node.right, res);
  return res;
}

function postorder(node, res = []) {
  if (!node) return res;
  postorder(node.left, res);
  postorder(node.right, res);
  res.push(node.val);
  return res;
}

function levelOrder(root) {
  if (!root) return [];
  const res = [], q = [root];
  while (q.length) {
    const n = q.shift();
    res.push(n.val);
    if (n.left) q.push(n.left);
    if (n.right) q.push(n.right);
  }
  return res;
}

console.log('Preorder:', preorder(root).join(' '));
console.log('Inorder:', inorder(root).join(' '));
console.log('Postorder:', postorder(root).join(' '));
console.log('Level-order:', levelOrder(root).join(' '));

BST: вставка і пошук (JavaScript)

function insert(root, val) {
  if (!root) return new Node(val);
  if (val < root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

function search(root, val) {
  let cur = root;
  while (cur) {
    if (val === cur.val) return true;
    cur = val < cur.val ? cur.left : cur.right;
  }
  return false;
}

let bst = null;
bst = insert(bst, 8);
[3, 10, 1, 6, 14, 4, 7, 13].forEach(v => (bst = insert(bst, v)));
console.log('Search 7:', search(bst, 7)); // true
console.log('Search 2:', search(bst, 2)); // false

Перевірка властивостей: валідність BST і баланс

function isValidBST(node, min = -Infinity, max = Infinity) {
  if (!node) return true;
  if (node.val <= min || node.val >= max) return false;
  return (
    isValidBST(node.left, min, node.val) &&
    isValidBST(node.right, node.val, max)
  );
}

function isBalanced(root) {
  function height(node) {
    if (!node) return 0;
    const lh = height(node.left);
    if (lh === -1) return -1;
    const rh = height(node.right);
    if (rh === -1) return -1;
    if (Math.abs(lh - rh) > 1) return -1;
    return Math.max(lh, rh) + 1;
  }
  return height(root) !== -1;
}

console.log('Valid BST:', isValidBST(bst));
console.log('Balanced:', isBalanced(bst));

Діаграма і результати обходів

Дерево:
         8
       /   \
      3     10
     / \      \
    1   6      14
       / \    /
      4   7  13

Preorder (N-L-R):   8 3 1 6 4 7 10 14 13
Inorder (L-N-R):    1 3 4 6 7 8 10 13 14
Postorder (L-R-N):  1 4 7 6 3 13 14 10 8
Level-order (BFS):  8 3 10 1 6 14 4 7 13

Складність

Операція	Загальний випадок	BST (середній)	BST (гірший)	Пам'ять
Обходи (DFS/BFS)	O(n)	-	-	O(h) стек або O(n) черга
Пошук (BST)	-	O(log n)	O(n)	O(1)
Вставка (BST)	-	O(log n)	O(n)	O(1)
Видалення (BST)	-	O(log n)	O(n)	O(1)
Доступ до дітей/батька (масив)	O(1)	O(1)	O(1)	O(1)

Коли використовувати

Парсери і дерева розбору (AST), дерева виразів.
Черги з пріоритетами (бінарна купа).
Швидкий пошук/вставка/видалення в упорядкованій колекції (BST, самобалансувальні дерева).
Дерева рішень, маршрутизація, індекси в базах даних (варіації B-дерев, хоча вони не бінарні).

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

Чим бінарне дерево відрізняється від BST? У BST значення впорядковані за властивістю ліво < вузол < право; у загальному бінарному дереві порядку може не бути.
Чому inorder-обхід BST видає відсортовану послідовність? Він відвідує ліве піддерево (усі менші), потім вузол, потім праве (усі більші).
Різниця між висотою і глибиною? Глибина - від кореня до вузла; висота - від вузла до найглибшого листа.
Збалансоване vs повне vs ідеальне? Збалансоване - висота O(log n); повне - останній рівень зліва направо; ідеальне - усі рівні заповнені повністю.
Як представити дерево в масиві? Для індексу i: left = 2i + 1, right = 2i + 2, parent = ⌊(i - 1) / 2⌋ (підходить для повних дерев).

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

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

Premium

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