Алгоритмы с нуля
Двоичное дерево
Вы знаете, что связный список — это цепь узлов, каждый указывает на следующий. Теперь представьте структуру, где каждый узел указывает не на один следующий узел, а на два: левого и правого ребёнка. Это дерево. Вместо линейной цепи вы получаете ветвящуюся структуру — один корневой узел вверху, разветвляющийся вниз в листья. Деревья позволяют организовать иерархии (как файловая система), и они так естественно подходят рекурсии, что обработка дерева кажется дыханием.
После этого урока вы сможете объяснить, что такое дерево, отличить двоичное дерево от других деревьев, использовать терминологию (корень, лист, родитель, ребёнок, глубина, высота, поддерево, уровень), реализовать узел с левым и правым указателями, навигировать по двоичному дереву, следуя указателям на детей, и распознать, когда дерево — правильная структура данных.
Что такое дерево?
Дерево — это иерархия узлов, соединённых рёбрами. Один узел особенный: корень, вверху. Каждый другой узел имеет ровно одного родителя (узел, который на него указывает). Узел может иметь ноль, одного или несколько детей (узлы, на которые он указывает).
Визуально:
1 (корень)
/ \
2 3
/ \
4 5Здесь узел 1 — корень. Узел 2 — родитель узлов 4 и 5. Узел 4 — дитя узла 2. Узлы 4 и 5 — братья (они имеют одного и того же родителя).
Что такое двоичное дерево?
Двоичное дерево — это дерево, где каждый узел имеет максимум 2 детей. Мы называем их левым ребёнком и правым ребёнком. Узел может иметь:
- Нет детей (лист)
- Одного ребёнка (только левого или только правого)
- Двух детей (и левого, и правого)
Двоичное дерево выше:
1
/ \
2 3
/ \
4 5Узел 1 имеет левого ребёнка (2) и правого ребёнка (3). Узел 2 имеет двух детей. Узел 3 не имеет никого. Узлы 4 и 5 — листья.
Терминология дерева
- Корень: Самый верхний узел (нет родителя).
- Лист: Узел без детей.
- Внутренний узел: Узел, имеющий хотя бы одного ребёнка.
- Родитель / Дитя: Если узел A указывает на узел B, A — родитель и B — дитя.
- Брат: Два узла с одним и тем же родителем.
- Предок / Потомок: Узел A — предок B, если A находится на пути от B вверх к корню. B — потомок A.
- Уровень: Все узлы на одном расстоянии от корня находятся на одном уровне. Корень находится на уровне 0.
Глубина vs. Высота (это сбивает с толку всех)
- Глубина узла = количество рёбер от корня вниз к этому узлу. Корень имеет глубину 0.
- Высота узла = количество рёбер от этого узла вниз к его самому дальнему листовому потомку. Лист имеет высоту 0.
- Высота дерева = высота корня.
Подсказка памяти: Глубина — это как глубоко вы спустились вниз от корня. Высота — это насколько высоко поддерево поднимается ниже вас.
Пример:
1 (глубина=0, высота=2)
/ \
2 3 (глубина=1, высота=1 для узла 2; высота=0 для узла 3)
/ \
4 5 (глубина=2, высота=0 для обоих)Узел 4 имеет глубину 2 (два ребра от корня: 1→2→4) и высоту 0 (нет детей). Узел 2 имеет глубину 1 и высоту 1 (одно ребро вниз к своему самому дальнему листу).
Поддеревья и рекурсия
Поддерево — это узел плюс все его потомки. Левое поддерево узла — это поддерево, укоренённое в его левом ребёнке. Правое поддерево укоренено в его правом ребёнке.
Двоичное дерево определяется рекурсивно:
- Пустое дерево — это двоичное дерево.
- Дерево с корнем и левым поддеревом (которое является двоичным деревом) и правым поддеревом (которое является двоичным деревом) — это двоичное дерево.
Это рекурсивное определение — ключевой момент: чтобы обработать любое дерево, вы обрабатываете корень, затем рекурсивно обрабатываете левое поддерево, затем правое поддерево. Эта структура — почему рекурсия и деревья созданы друг для друга.
Представление узла в коде
В связном списке каждый узел хранил значение и указатель на следующий узел. В двоичном дереве каждый узел хранит значение и указатели на левого и правого ребёнка:
1
class Node {
2
constructor(value, left = null, right = null) {
3
this.value = value;
4
this.left = left;
5
this.right = right;
6
}
7
}
8
9
// Построим дерево:
10
// 1
11
// / \
12
// 2 3
13
// / \
14
// 4 5
15
16
let node4 = new Node(4);
17
let node5 = new Node(5);
18
let node2 = new Node(2, node4, node5);
19
let node3 = new Node(3);
20
let root = new Node(1, node2, node3);
- L1 Конструктор Node хранит value, left и right.
- L7 Строим снизу вверх: листья в первую очередь.
- L13 Корень — точка входа в целое дерево.
Навигирование по дереву, следуя указателям
Чтобы прочитать дерево, вы следуете связям родитель→ребёнок. Каждый узел — это один шаг вниз:
1
// Доступ к узлам, следуя указателям left/right
2
let root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
3
4
// Навигирование к левому ребёнку корня
5
let leftChild = root.left; // Узел 2
6
7
// Навигирование к левому ребёнку узла 2
8
let leftGrandchild = root.left.left; // Узел 4
9
10
// Навигирование к правому ребёнку узла 2
11
let rightGrandchild = root.left.right; // Узел 5
12
13
// Каждая связь — это один прыжок указателя
14
console.log(leftChild.value); // 2
15
console.log(leftGrandchild.value); // 4
- L5 root.left следует указателю left от корня.
- L8 root.left.left — это прыжок через два указателя.
- L11 root.left.right прыгает влево, затем вправо.
- L14 Каждая навигация обращается к свойству value.
Простой помощник: проверка, является ли узел листом
Лист не имеет детей (и left, и right равны null). Вот небольшая вспомогательная функция:
1
function isLeaf(node) {
2
return node.left === null && node.right === null;
3
}
4
5
let root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
6
7
console.log(isLeaf(root.left.left)); // true (узел 4 — лист)
8
console.log(isLeaf(root.left)); // false (узел 2 имеет детей)
9
console.log(isLeaf(root)); // false (корень имеет детей)
- L1 Лист — это узел без детей.
- L2 Проверьте, оба ли указателя равны null.
- L6 Построим дерево.
- L8 Узел 4 не имеет детей, поэтому isLeaf вернёт true.
1
let root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
2
let target = root.left.right; // Навигирование к узлу 5
3
console.log(target.value);
Сложность по времени
Построение дерева с нуля (создание n узлов) занимает O(n) времени. Навигирование по дереву, следуя прыжкам указателей (например, root.left.right), занимает O(1) за один прыжок. Следование по пути длины d занимает O(d). Вспомогательная функция isLeaf — O(1).
Время = O(1) за один прыжок указателя; O(n) для построения всего дерева.
Сложность по памяти
Память используется для хранения структуры дерева: каждый из n узлов занимает O(1) пространства. Само дерево использует O(n) памяти.
Память = O(n) для самой структуры дерева. Отдельные операции типа isLeaf используют O(1) дополнительного пространства.
Что такое глубина узла?
Что такое высота узла?
Какова высота листового узла?
Как в коде вы представляете узел двоичного дерева?
Какова худшая высота двоичного дерева с 7 узлами?
lesson.inset.undefined
Глубина ≠ Высота. Глубина измеряет расстояние от корня вниз к вам. Высота измеряет расстояние от вас вниз к самому дальнему листу. Они указывают в противоположные направления.
lesson.inset.undefined
Пустое дерево. Дерево может быть пустым (нет узлов). Высота пустого дерева иногда определяется как -1, иногда как 0, в зависимости от соглашения. Всегда проверяйте определение в вашей задаче.
lesson.inset.undefined
Нарисуйте дерево. Нарисуйте двоичное дерево с 5 узлами. Обозначьте корень, листья и один внутренний узел. Затем вычислите глубину и высоту каждого узла. Это самый быстрый способ закрепить терминологию.
Почему дерево естественно подходит для рекурсивных алгоритмов?
Дерево: иерархия узлов с одним корнем вверху. Двоичное дерево ограничивает каждый узел максимум 2 детьми (слева и справа). Деревья используют терминологию: корень, лист, родитель, ребёнок, брат, предок, потомок, уровень. Глубина — это количество рёбер от корня вниз к узлу; высота — это количество рёбер от узла вниз к его самому дальнему листу. Поддерево — это узел плюс все его потомки. В коде представьте узел как { value, left, right }, где left и right равны null, если у узла нет этого ребёнка. Навигируйте по дереву, следуя указателям left и right от корня. Лист — это любой узел, где и left, и right равны null. Двоичные деревья — это основание для куч, двоичных деревьев поиска и многих других алгоритмов. Далее вы научитесь обходам: как посетить все узлы в определённом порядке.