Алгоритмы с нуля ALG · 07 · 01

Двоичное дерево

Дерево - иерархия узлов: один корень вверху, каждый указывает на дочерние узлы ниже. Двоичное дерево ограничивает каждый узел максимум 2 детьми (слева и справа). Деревья подходят для рекурсии - обработайте узел, затем рекурсивно его левое и правое поддеревья.

ALG ◷ 22 min

Уже знаешь этот юнит? Пройди быструю проверку за минуту →

Вы знаете, что связный список — это цепь узлов, каждый указывает на следующий. Теперь представьте структуру, где каждый узел указывает не на один следующий узел, а на два: левого и правого ребёнка. Это дерево. Вместо линейной цепи вы получаете ветвящуюся структуру — один корневой узел вверху, разветвляющийся вниз в листья. Деревья позволяют организовать иерархии (как файловая система), и они так естественно подходят рекурсии, что обработка дерева кажется дыханием. За десять минут вы узнаете терминологию, научитесь представлять дерево в коде и поймёте, почему деревья и рекурсия неразделимы — чтобы при первой же задаче на дерево сразу узнать форму и знать, куда двигаться.

Goal

После этого урока вы сможете объяснить, что такое дерево, отличить двоичное дерево от других деревьев, использовать терминологию (корень, лист, родитель, ребёнок, глубина, высота, поддерево, уровень), реализовать узел с левым и правым указателями, навигировать по двоичному дереву, следуя указателям на детей, и распознать, когда дерево — правильная структура данных.

The idea

Что такое дерево?

Зачем нам вообще нужны деревья? Массивы и связные списки плоские — каждый элемент равнозначен. Но реальные задачи имеют иерархию: файловая система содержит папки внутри папок, компания — менеджеров с подчинёнными, арифметическое выражение — операторы с под-выражениями. Дерево напрямую отражает эту структуру, и как только вы увидите форму однажды, вы начнёте замечать её везде.

Дерево — это иерархия узлов, соединённых рёбрами. Один узел особенный: корень, вверху. Каждый другой узел имеет ровно одного родителя (узел, который на него указывает). Узел может иметь ноль, одного или несколько детей (узлы, на которые он указывает).

Визуально:

      1 (корень)
     / \
    2   3
   / \
  4   5

Здесь узел 1 — корень. Узел 2 — родитель узлов 4 и 5. Узел 4 — дитя узла 2. Узлы 4 и 5 — братья (они имеют одного и того же родителя).

Что такое двоичное дерево?

Двоичное дерево — это дерево, где каждый узел имеет максимум 2 детей. Мы называем их левым ребёнком и правым ребёнком. Узел может иметь:

Нет детей (лист)
Одного ребёнка (только левого или только правого)
Двух детей (и левого, и правого)

Двоичное дерево выше:

Узел 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 (одно ребро вниз к своему самому дальнему листу).

Поддеревья и рекурсия

Поддерево — это узел плюс все его потомки. Левое поддерево узла — это поддерево, укоренённое в его левом ребёнке. Правое поддерево укоренено в его правом ребёнке.

Двоичное дерево определяется рекурсивно:

Пустое дерево — это двоичное дерево.
Дерево с корнем и левым поддеревом (которое является двоичным деревом) и правым поддеревом (которое является двоичным деревом) — это двоичное дерево.

Это рекурсивное определение — ключевой момент: чтобы обработать любое дерево, вы обрабатываете корень, затем рекурсивно обрабатываете левое поддерево, затем правое поддерево. Эта структура — почему рекурсия и деревья созданы друг для друга.

Каноническое двоичное дерево: один корень вверху, каждый узел имеет максимум два ребёнка (левого и правого), рёбра соединяют родителя с ребёнком, а листья внизу не имеют собственных детей.

The code

Представление узла в коде

В связном списке каждый узел хранил значение и указатель на следующий узел. В двоичном дереве каждый узел хранит значение и указатели на левого и правого ребёнка:

1 class Node {

2 constructor(value, left = null, right = null) {

3 this.value = value;

4 this.left = left;

5 this.right = right;

6 }

7 }

9 // Построим дерево:

10 // 1

11 // / \

12 // 2 3

13 // / \

14 // 4 5

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));

4 // Навигирование к левому ребёнку корня

5 let leftChild = root.left; // Узел 2

7 // Навигирование к левому ребёнку узла 2

8 let leftGrandchild = root.left.left; // Узел 4

10 // Навигирование к правому ребёнку узла 2

11 let rightGrandchild = root.left.right; // Узел 5

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 }

5 let root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));

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.

Output

Step-by-step trace

Complexity

Сложность по времени

Построение дерева с нуля (создание 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) дополнительного пространства.

Практика 0 / 5

Что такое глубина узла?

Что такое высота узла?

Какова высота листового узла?

Как в коде вы представляете узел двоичного дерева?

Какова худшая высота двоичного дерева с 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. Двоичные деревья — это основание для куч, двоичных деревьев поиска и многих других алгоритмов. Теперь, когда вы встретите узел с указателями left и right, вы мгновенно прочитаете всю структуру поддерева и поймёте: нырять ли глубже или комбинировать результаты на обратном пути вверх.

Практика

Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.

вспомнитьприменитьуглубить0 из 4 завершено

Что-то непонятно?

Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.