Бинарное дерево: что это, виды, листья, полное и сбалансированное дерево

Бинарное дерево простыми словами: корень, узлы и листья, высота, виды деревьев (строгое, полное, совершенное, сбалансированное, вырожденное) и построение на Python с рабочим кодом.

15 мин чтенияструктуры данных · деревья · python

Коротко

ВопросОтвет
Что этоДерево, в котором у каждого узла не больше двух детей: левый и правый
ЛистУзел без детей
ВысотаЧисло рёбер на самом длинном пути от корня до листа
Сколько узлов помещаетсяНа уровне kk не больше 2k2^k узлов, во всём дереве высоты hh не больше 2h+1−12^{h+1} - 1
Главные видыСтрогое, полное (законченное), совершенное, сбалансированное, вырожденное
Почему важна формаОперации идут от корня вниз и стоят O(h)O(h). В сбалансированном дереве h≈log⁡2nh \approx \log_2 n, в вырожденном h=n−1h = n - 1
Как хранитьУзлы со ссылками 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 для пустого дерева не случайно: тогда у листа получается 1+max⁡(−1,−1)=01 + \max(-1, -1) = 0, и особый случай для листа писать не приходится.

Обе функции заходят в каждый узел один раз, поэтому работают за O(n)O(n). Памяти нужно O(h)O(h): столько вызовов одновременно лежит в стеке.

Листья бинарного дерева

Лист — узел, у которого оба ребёнка отсутствуют. Собрать листья слева направо и посчитать их можно так:

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, а листьев три. Это верно для любого непустого бинарного дерева, и причина простая. В дереве из nn узлов ровно n−1n - 1 ребро, потому что в каждый узел, кроме корня, входит одно ребро. С другой стороны, рёбра выходят из родителей: узел с двумя детьми даёт два ребра, с одним — одно. Если узлов с двумя детьми n2n_2, с одним n1n_1, а листьев n0n_0, то

n0+n1+n2−1=n1+2n2⇒n0=n2+1.n_0 + n_1 + n_2 - 1 = n_1 + 2 n_2 \quad\Rightarrow\quad n_0 = n_2 + 1.

На уровне kk не больше 2k2^k узлов. Каждый уровень максимум вдвое шире предыдущего. Поэтому листьев в дереве высоты hh не больше 2h2^h.

Лист не обязан быть на последнем уровне. В дереве ниже лист 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

Из формулы n0=n2+1n_0 = n_2 + 1 следует, что в строгом дереве с LL листьями всего 2L−12L - 1 узлов: узлов с одним ребёнком нет. Типичный пример строгого дерева — дерево арифметического выражения: в листьях числа, во внутренних узлах операции с двумя аргументами.

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

Главное свойство: такое дерево укладывается в массив без пустых ячеек. Именно поэтому полным деревом является бинарная куча. Высота полного дерева из nn узлов всегда равна ⌊log⁡2n⌋\lfloor \log_2 n \rfloor.

Проверка идёт по уровням через очередь. В очередь кладём и отсутствующих детей. Как только встретили 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

Здесь всё считается точно. В совершенном дереве высоты hh:

  • листьев 2h2^h;
  • всего узлов 1+2+4+⋯+2h=2h+1−11 + 2 + 4 + \dots + 2^h = 2^{h+1} - 1;
  • листьев на один больше, чем всех остальных узлов вместе.

При высоте 2 это 4 листа и 7 узлов, при высоте 20 — уже больше двух миллионов узлов. Обратная сторона той же формулы: чтобы дойти до любого из миллиона элементов, достаточно около 20 шагов.

def is_perfect(root): return size(root) == 2 ** (height(root) + 1) - 1

Совершенное дерево одновременно строгое и полное. Обратное неверно: дерево из примера про строгие деревья строгое, но не полное.

Вырожденное дерево

У каждого узла один ребёнок. По сути это связный список, который притворяется деревом.

1 \ 2 \ 3 \ 4

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

Сбалансированное бинарное дерево

Самое распространённое определение: дерево сбалансировано по высоте, если у каждого узла высоты левого и правого поддерева отличаются не больше чем на 1.

Слово «каждого» здесь ключевое. Проверить только корень недостаточно: слева и справа могут висеть две одинаково длинные цепочки.

Наивная проверка вызывает height в каждом узле и в худшем случае работает за O(n2)O(n^2). Правильный вариант считает высоту и проверяет баланс за один проход снизу вверх:

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

Зачем это нужно. Поиск, вставка и удаление в деревьях идут от корня вниз и стоят O(h)O(h). У сбалансированного дерева высота O(log⁡n)O(\log n), у вырожденного O(n)O(n). На миллионе элементов это разница между парой десятков шагов и миллионом.

Баланс сам не поддерживается: после вставок и удалений дерево нужно чинить поворотами. Этим занимаются самобалансирующиеся деревья. AVL-дерево держит именно то строгое условие, что описано выше. Красно-чёрное дерево использует более мягкое правило: его высота может быть примерно вдвое больше минимальной, зато перестраивать его приходится реже.

Проверяем всё вместе

Результаты функций на деревьях из этой статьи:

ДеревоУзловВысотаСтрогоеПолноеСовершенноеСбалансированное
Пример из начала статьи62нетнетнетда
Из раздела про строгое52данетнетда
Из раздела про полное62нетданетда
Из раздела про совершенное72дададада
Цепочка из 4 узлов43нетнетнетнет

Полезные следствия: любое совершенное дерево полное, любое полное сбалансировано. В обратную сторону ни одно из утверждений не работает.

Виды по содержимому

Всё, что выше, касалось формы. Вторая ось классификации — правило для значений в узлах.

СтруктураПравилоЧто даёт
Дерево поиска (BST)Слева от узла всё меньше него, справа всё большеПоиск, вставка и удаление за O(h)O(h)
Бинарная кучаРодитель не больше детей (или не меньше), форма полнаяМинимум за O(1)O(1), вставка за O(log⁡n)O(\log n)
AVL-деревоBST плюс строгий баланс высотГарантированный O(log⁡n)O(\log n) на все операции
Красно-чёрное деревоBST плюс правила раскраски узловТот же O(log⁡n)O(\log n), меньше поворотов

Частая ошибка новичков — говорить «бинарное дерево», имея в виду дерево поиска. Это разные вещи: в произвольном бинарном дереве значения могут стоять как угодно, и найти элемент можно только полным перебором за O(n)O(n).

Построение бинарного дерева

Собирать дерево руками, как в начале статьи, удобно только для маленьких примеров. Вот три способа, которые встречаются на практике.

Из списка по уровням

Так деревья записывают в условиях задач на 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. Срезы копируют список, из-за чего эта версия работает за O(nlog⁡n)O(n \log n). Если передавать границы lo и hi вместо срезов, выйдет O(n)O(n).

В массиве, без ссылок

Полное дерево можно вообще не строить из узлов. Запишем значения по уровням в массив, и структура дерева окажется зашита в индексы:

  • левый ребёнок узла 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 как дерево, где в листьях числа, а во внутренних узлах операции.
  • Сжатие данных. Код Хаффмана строится по бинарному дереву: путь от корня до листа задаёт код символа.
  • Собеседования. Деревья — одна из самых частых тем алгоритмических секций. Подборка типовых задач с решениями есть в отдельной статье.

Частые ошибки

  1. Путать бинарное дерево и дерево поиска. Бинарное дерево — только форма. Упорядоченность значений есть лишь в BST.
  2. Путать строгое, полное и совершенное дерево. Особенно в русских источниках, где «полным» называют разное. Сверяйтесь с определением.
  3. Проверять баланс только в корне. Условие должно выполняться в каждом узле.
  4. Считать лист по одному None. Лист — узел, у которого нет обоих детей. Проверка if not node.left находит и узлы с одним правым ребёнком.
  5. Не договориться о высоте. В рёбрах или в узлах, чему равна высота пустого дерева. Разница в единицу ломает формулы.
  6. Забывать про пустое дерево. Обращение к root.left при root is None — самое частое падение в задачах на деревья.
  7. Не думать о глубине рекурсии. В Python по умолчанию лимит около 1000 вложенных вызовов. На вырожденном дереве из нескольких тысяч узлов рекурсивная height упадёт с RecursionError. В таких случаях обход переписывают на явный стек или очередь.

Что запомнить

  • Бинарное дерево: у каждого узла максимум два ребёнка, левый и правый. Пустое дерево — тоже дерево.
  • Лист — узел без детей. Листьев всегда на один больше, чем узлов с двумя детьми.
  • В дереве высоты hh не больше 2h+1−12^{h+1} - 1 узлов, а дерево из nn узлов не может быть ниже ⌊log⁡2n⌋\lfloor \log_2 n \rfloor.
  • Строгое: 0 или 2 ребёнка. Полное: уровни заполнены слева направо. Совершенное: заполнено всё. Сбалансированное: высоты поддеревьев в каждом узле отличаются максимум на 1.
  • Стоимость операций определяется высотой, поэтому форма дерева важнее числа узлов.
  • BST, куча, AVL и красно-чёрное дерево — это бинарное дерево плюс правило для значений или формы.

Потренироваться в спокойной обстановке

Все задачи

Читать дальше

Все статьи