Бинарное дерево: что это, виды, листья, полное и сбалансированное дерево
Бинарное дерево простыми словами: корень, узлы и листья, высота, виды деревьев (строгое, полное, совершенное, сбалансированное, вырожденное) и построение на Python с рабочим кодом.
Коротко
| Вопрос | Ответ |
|---|---|
| Что это | Дерево, в котором у каждого узла не больше двух детей: левый и правый |
| Лист | Узел без детей |
| Высота | Число рёбер на самом длинном пути от корня до листа |
| Сколько узлов помещается | На уровне не больше узлов, во всём дереве высоты не больше |
| Главные виды | Строгое, полное (законченное), совершенное, сбалансированное, вырожденное |
| Почему важна форма | Операции идут от корня вниз и стоят . В сбалансированном дереве , в вырожденном |
| Как хранить | Узлы со ссылками left и right либо массив, где дети узла i лежат в 2i + 1 и 2i + 2 |
Бинарное дерево само по себе ничего не обещает про порядок значений. Это только форма. Дерево поиска, куча, AVL и красно-чёрное дерево получаются, когда к форме добавляют правило. О них есть отдельные статьи, ссылки будут по ходу.
Что такое бинарное дерево
Бинарное (двоичное) дерево — это структура данных из узлов, где каждый узел хранит значение и ссылки максимум на двух детей. Детей различают: один левый, другой правый. Узел с единственным правым ребёнком и узел с единственным левым — разные деревья.
Пример бинарного дерева, с которым будем работать всю статью:
1 / \ 2 3 / \ \ 4 5 6
Термины, без которых дальше никуда:
- Корень — верхний узел, у него нет родителя. Здесь это
1. - Родитель и ребёнок — соседние узлы на одном ребре. У
2родитель1, дети4и5. - Лист — узел без детей:
4,5,6. - Внутренний узел — любой узел, у которого есть хотя бы один ребёнок:
1,2,3. - Поддерево — узел вместе со всеми потомками. Левое поддерево корня: узлы
2,4,5. - Глубина узла — число рёбер от корня до него. У корня 0, у
5глубина 2. - Уровень — все узлы одной глубины. Уровень 1 здесь:
2и3. - Высота дерева — глубина самого далёкого листа. У нашего дерева высота 2.
С высотой есть разночтение: часть учебников считает её в узлах, а не в рёбрах, и тогда у того же дерева высота 3. В этой статье высота считается в рёбрах: у дерева из одного узла она 0, у пустого дерева −1. На экзамене или собеседовании уточняйте, какое определение имеется в виду.
Бинарное дерево — частный случай дерева вообще. Если хочется сначала разобраться с общей картиной (корневые деревья, произвольное число детей, связь с графами), загляните в статью про деревья как структуру данных. А место деревьев среди массивов, списков и хеш-таблиц показано в обзоре структур данных.
Определение через рекурсию
Есть второе определение, и для программиста оно полезнее первого:
Бинарное дерево — это либо пустое дерево, либо узел, у которого есть левое и правое поддеревья, и оба они тоже бинарные деревья.
Почти весь код для деревьев повторяет эту фразу дословно: «если дерево пустое, верни ответ для пустого; иначе реши задачу для левого и правого поддерева и склей результаты». Если рекурсия пока вызывает трудности, сначала прочитайте разбор рекурсии.
Узел на Python
Узлу нужны три поля: значение и две ссылки. Отсутствующий ребёнок обозначается None.
class Node: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right
Дерево из примера можно собрать по одному узлу:
root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.right = Node(6)
Или одним выражением, которое повторяет форму дерева:
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
Отдельного класса «дерево» не нужно: дерево целиком задаётся ссылкой на корень. Пустое дерево — это просто None.
Размер и высота
Обе функции — прямой перевод рекурсивного определения.
def size(node): if node is None: return 0 return 1 + size(node.left) + size(node.right) def height(node): if node is None: return -1 return 1 + max(height(node.left), height(node.right)) print(size(root)) # 6 print(height(root)) # 2
height возвращает −1 для пустого дерева не случайно: тогда у листа получается , и особый случай для листа писать не приходится.
Обе функции заходят в каждый узел один раз, поэтому работают за . Памяти нужно : столько вызовов одновременно лежит в стеке.
Листья бинарного дерева
Лист — узел, у которого оба ребёнка отсутствуют. Собрать листья слева направо и посчитать их можно так:
def is_leaf(node): return node.left is None and node.right is None def leaves(node): if node is None: return [] if is_leaf(node): return [node.val] return leaves(node.left) + leaves(node.right) def count_leaves(node): if node is None: return 0 if is_leaf(node): return 1 return count_leaves(node.left) + count_leaves(node.right) print(leaves(root)) # [4, 5, 6] print(count_leaves(root)) # 3
Про листья полезно помнить три факта.
Листьев на один больше, чем узлов с двумя детьми. В нашем дереве два ребёнка у узлов 1 и 2, а листьев три. Это верно для любого непустого бинарного дерева, и причина простая. В дереве из узлов ровно ребро, потому что в каждый узел, кроме корня, входит одно ребро. С другой стороны, рёбра выходят из родителей: узел с двумя детьми даёт два ребра, с одним — одно. Если узлов с двумя детьми , с одним , а листьев , то
На уровне не больше узлов. Каждый уровень максимум вдвое шире предыдущего. Поэтому листьев в дереве высоты не больше .
Лист не обязан быть на последнем уровне. В дереве ниже лист 2 находится на глубине 1, хотя высота дерева 2:
1 / \ 2 3 / \ 4 5
Отсюда частая ошибка в задаче «минимальная глубина дерева»: считают минимальную глубину до None, а нужно до листа. У узла с одним ребёнком пустая сторона листом не является.
Виды бинарных деревьев
Виды различаются формой: сколько детей у узлов и как заполнены уровни.
| Вид | По-английски | Условие |
|---|---|---|
| Строгое | full, strict | У каждого узла либо 0, либо 2 ребёнка |
| Полное (законченное) | complete | Все уровни, кроме последнего, заполнены, а последний заполнен слева направо без пропусков |
| Совершенное | perfect | Заполнены все уровни, все листья на одной глубине |
| Сбалансированное | balanced | У каждого узла высоты левого и правого поддерева отличаются максимум на 1 |
| Вырожденное | degenerate | У каждого узла не больше одного ребёнка, дерево вытянуто в цепочку |
Путаница с «полным» деревом
В английской литературе термины разведены чётко: full, complete, perfect. В русской слово «полное» достаётся то одному, то другому. В одних учебниках полным называют дерево, где у каждого узла 0 или 2 ребёнка (full). В других — дерево с заполненными слева направо уровнями (complete). В школьной информатике под полным бинарным деревом нередко понимают дерево, где заполнены вообще все уровни (perfect).
Что с этим делать: в задаче или билете смотрите на определение, а не на слово. Если определения нет, спросите. В этой статье «полное» означает complete, для full используется слово «строгое», для perfect — «совершенное».
Строгое дерево
У каждого узла либо нет детей, либо их двое.
1 / \ 2 3 / \ 4 5
Из формулы следует, что в строгом дереве с листьями всего узлов: узлов с одним ребёнком нет. Типичный пример строгого дерева — дерево арифметического выражения: в листьях числа, во внутренних узлах операции с двумя аргументами.
def is_full(node): if node is None: return True if (node.left is None) != (node.right is None): return False return is_full(node.left) and is_full(node.right)
Полное бинарное дерево
Все уровни, кроме, возможно, последнего, заполнены целиком. Последний уровень заполняется слева направо без дырок.
1 / \ 2 3 / \ / 4 5 6
Главное свойство: такое дерево укладывается в массив без пустых ячеек. Именно поэтому полным деревом является бинарная куча. Высота полного дерева из узлов всегда равна .
Проверка идёт по уровням через очередь. В очередь кладём и отсутствующих детей. Как только встретили None, дальше настоящих узлов быть не должно:
from collections import deque def is_complete(root): queue = deque([root]) seen_gap = False while queue: node = queue.popleft() if node is None: seen_gap = True else: if seen_gap: return False queue.append(node.left) queue.append(node.right) return True
Наше дерево из начала статьи эту проверку не проходит: у узла 3 нет левого ребёнка, но есть правый, то есть в последнем уровне дырка. Сам обход по уровням подробно разобран в статье про level order.
Совершенное дерево
Все уровни заполнены, все листья на одной глубине.
1 / \ 2 3 / \ / \ 4 5 6 7
Здесь всё считается точно. В совершенном дереве высоты :
- листьев ;
- всего узлов ;
- листьев на один больше, чем всех остальных узлов вместе.
При высоте 2 это 4 листа и 7 узлов, при высоте 20 — уже больше двух миллионов узлов. Обратная сторона той же формулы: чтобы дойти до любого из миллиона элементов, достаточно около 20 шагов.
def is_perfect(root): return size(root) == 2 ** (height(root) + 1) - 1
Совершенное дерево одновременно строгое и полное. Обратное неверно: дерево из примера про строгие деревья строгое, но не полное.
Вырожденное дерево
У каждого узла один ребёнок. По сути это связный список, который притворяется деревом.
1 \ 2 \ 3 \ 4
Высота такого дерева , и все преимущества дерева пропадают: чтобы добраться до последнего узла, нужно пройти все остальные. Вырожденное дерево получается, например, если вставлять в обычное бинарное дерево поиска уже отсортированные данные.
Сбалансированное бинарное дерево
Самое распространённое определение: дерево сбалансировано по высоте, если у каждого узла высоты левого и правого поддерева отличаются не больше чем на 1.
Слово «каждого» здесь ключевое. Проверить только корень недостаточно: слева и справа могут висеть две одинаково длинные цепочки.
Наивная проверка вызывает height в каждом узле и в худшем случае работает за . Правильный вариант считает высоту и проверяет баланс за один проход снизу вверх:
def is_balanced(root): def check(node): # возвращает высоту поддерева или None, если оно не сбалансировано if node is None: return -1 left = check(node.left) if left is None: return None right = check(node.right) if right is None or abs(left - right) > 1: return None return 1 + max(left, right) return check(root) is not None
Зачем это нужно. Поиск, вставка и удаление в деревьях идут от корня вниз и стоят . У сбалансированного дерева высота , у вырожденного . На миллионе элементов это разница между парой десятков шагов и миллионом.
Баланс сам не поддерживается: после вставок и удалений дерево нужно чинить поворотами. Этим занимаются самобалансирующиеся деревья. AVL-дерево держит именно то строгое условие, что описано выше. Красно-чёрное дерево использует более мягкое правило: его высота может быть примерно вдвое больше минимальной, зато перестраивать его приходится реже.
Проверяем всё вместе
Результаты функций на деревьях из этой статьи:
| Дерево | Узлов | Высота | Строгое | Полное | Совершенное | Сбалансированное |
|---|---|---|---|---|---|---|
| Пример из начала статьи | 6 | 2 | нет | нет | нет | да |
| Из раздела про строгое | 5 | 2 | да | нет | нет | да |
| Из раздела про полное | 6 | 2 | нет | да | нет | да |
| Из раздела про совершенное | 7 | 2 | да | да | да | да |
| Цепочка из 4 узлов | 4 | 3 | нет | нет | нет | нет |
Полезные следствия: любое совершенное дерево полное, любое полное сбалансировано. В обратную сторону ни одно из утверждений не работает.
Виды по содержимому
Всё, что выше, касалось формы. Вторая ось классификации — правило для значений в узлах.
| Структура | Правило | Что даёт |
|---|---|---|
| Дерево поиска (BST) | Слева от узла всё меньше него, справа всё больше | Поиск, вставка и удаление за |
| Бинарная куча | Родитель не больше детей (или не меньше), форма полная | Минимум за , вставка за |
| AVL-дерево | BST плюс строгий баланс высот | Гарантированный на все операции |
| Красно-чёрное дерево | BST плюс правила раскраски узлов | Тот же , меньше поворотов |
Частая ошибка новичков — говорить «бинарное дерево», имея в виду дерево поиска. Это разные вещи: в произвольном бинарном дереве значения могут стоять как угодно, и найти элемент можно только полным перебором за .
Построение бинарного дерева
Собирать дерево руками, как в начале статьи, удобно только для маленьких примеров. Вот три способа, которые встречаются на практике.
Из списка по уровням
Так деревья записывают в условиях задач на LeetCode: значения идут уровень за уровнем слева направо, отсутствующий ребёнок обозначен None. Наше дерево выглядит как [1, 2, 3, 4, 5, None, 6].
Строим через очередь: достаём узел и выдаём ему двух следующих детей из списка.
from collections import deque def from_level_order(values): if not values or values[0] is None: return None root = Node(values[0]) queue = deque([root]) i = 1 while queue and i < len(values): node = queue.popleft() if values[i] is not None: node.left = Node(values[i]) queue.append(node.left) i += 1 if i < len(values) and values[i] is not None: node.right = Node(values[i]) queue.append(node.right) i += 1 return root root = from_level_order([1, 2, 3, 4, 5, None, 6]) print(leaves(root)) # [4, 5, 6] print(height(root)) # 2
Важная деталь формата: у отсутствующего узла детей в списке нет вообще. Поэтому строгое дерево из примера выше записывается как [1, 2, 3, None, None, 4, 5], а цепочка вправо — как [1, None, 2, None, 3, None, 4].
Сбалансированное дерево из отсортированного списка
Если данные отсортированы, сбалансированное дерево поиска строится за один рекурсивный проход: середина становится корнем, левая половина уходит в левое поддерево, правая — в правое. Это та же идея деления пополам, что и в бинарном поиске.
def build_balanced(values): if not values: return None mid = len(values) // 2 return Node( values[mid], build_balanced(values[:mid]), build_balanced(values[mid + 1 :]), ) tree = build_balanced([1, 2, 3, 4, 5, 6, 7]) print(tree.val, tree.left.val, tree.right.val) # 4 2 6 print(height(tree)) # 2 print(is_balanced(tree)) # True
Получилось дерево
4 / \ 2 6 / \ / \ 1 3 5 7
Половины отличаются по размеру максимум на один элемент, поэтому и высоты поддеревьев отличаются не больше чем на 1. Срезы копируют список, из-за чего эта версия работает за . Если передавать границы lo и hi вместо срезов, выйдет .
В массиве, без ссылок
Полное дерево можно вообще не строить из узлов. Запишем значения по уровням в массив, и структура дерева окажется зашита в индексы:
- левый ребёнок узла
iлежит в2 * i + 1; - правый — в
2 * i + 2; - родитель — в
(i - 1) // 2.
tree = [1, 2, 3, 4, 5, 6] i = 1 # узел со значением 2 print(tree[2 * i + 1]) # 4, левый ребёнок print(tree[2 * i + 2]) # 5, правый ребёнок print(tree[(i - 1) // 2]) # 1, родитель
Никаких ссылок, данные лежат подряд в памяти. Так устроена бинарная куча и модуль heapq. Для неполных деревьев способ плох: под каждый пропущенный узел придётся держать пустую ячейку, и цепочка из 20 узлов займёт массив больше чем на миллион элементов.
Как посмотреть на дерево
При отладке помогает короткая функция, которая печатает дерево, повёрнутое на 90 градусов: корень слева, правое поддерево сверху.
def show(node, prefix='', label=''): if node is None: return show(node.right, prefix + ' ', '┌── ') print(prefix + label + str(node.val)) show(node.left, prefix + ' ', '└── ') show(from_level_order([1, 2, 3, 4, 5, None, 6]))
┌── 6 ┌── 3 1 ┌── 5 └── 2 └── 4
Обходы: как перебрать все узлы
У списка порядок перебора один, у дерева их несколько. Обходы в глубину (preorder, inorder, postorder) отличаются тем, когда обрабатывается сам узел: до детей, между ними или после. Обход в ширину идёт по уровням.
Функции size, height и leaves из этой статьи — уже обходы в глубину, просто они ничего не печатают. Подробности, итеративные версии и выбор порядка под задачу есть в статье про обходы в глубину и в статье про обход по уровням.
Где встречаются бинарные деревья
- Словари и множества с порядком.
TreeMapв Java иstd::mapв C++ обычно реализованы на красно-чёрных деревьях. - Очереди с приоритетом.
heapqв Python иPriorityQueueв Java — бинарная куча в массиве. - Разбор выражений. Компиляторы и калькуляторы хранят выражение
(2 + 3) * 4как дерево, где в листьях числа, а во внутренних узлах операции. - Сжатие данных. Код Хаффмана строится по бинарному дереву: путь от корня до листа задаёт код символа.
- Собеседования. Деревья — одна из самых частых тем алгоритмических секций. Подборка типовых задач с решениями есть в отдельной статье.
Частые ошибки
- Путать бинарное дерево и дерево поиска. Бинарное дерево — только форма. Упорядоченность значений есть лишь в BST.
- Путать строгое, полное и совершенное дерево. Особенно в русских источниках, где «полным» называют разное. Сверяйтесь с определением.
- Проверять баланс только в корне. Условие должно выполняться в каждом узле.
- Считать лист по одному
None. Лист — узел, у которого нет обоих детей. Проверкаif not node.leftнаходит и узлы с одним правым ребёнком. - Не договориться о высоте. В рёбрах или в узлах, чему равна высота пустого дерева. Разница в единицу ломает формулы.
- Забывать про пустое дерево. Обращение к
root.leftприroot is None— самое частое падение в задачах на деревья. - Не думать о глубине рекурсии. В Python по умолчанию лимит около 1000 вложенных вызовов. На вырожденном дереве из нескольких тысяч узлов рекурсивная
heightупадёт сRecursionError. В таких случаях обход переписывают на явный стек или очередь.
Что запомнить
- Бинарное дерево: у каждого узла максимум два ребёнка, левый и правый. Пустое дерево — тоже дерево.
- Лист — узел без детей. Листьев всегда на один больше, чем узлов с двумя детьми.
- В дереве высоты не больше узлов, а дерево из узлов не может быть ниже .
- Строгое: 0 или 2 ребёнка. Полное: уровни заполнены слева направо. Совершенное: заполнено всё. Сбалансированное: высоты поддеревьев в каждом узле отличаются максимум на 1.
- Стоимость операций определяется высотой, поэтому форма дерева важнее числа узлов.
- BST, куча, AVL и красно-чёрное дерево — это бинарное дерево плюс правило для значений или формы.