Двоичные деревья: назначение, виды и применение

Двоичное (бинарное) дерево — это иерархическая структура данных, в которой у каждого узла не больше двух потомков, причем они различаются как левый и правый. Назначение двоичного дерева — хранить данные так, чтобы на каждом шаге выбирать одну из двух ветвей: это дает быстрый поиск по ключу (дерево поиска), быструю выдачу минимума (куча) и естественное представление выражений и кодов (дерево выражения, код Хаффмана).

Важно сразу развести три вещи. Двоичное дерево — это форма (не больше двух упорядоченных потомков). Двоичное дерево поиска — форма плюс правило порядка ключей. Двоичная куча — почти полное дерево (без пропусков по уровням) плюс другое правило: в min-куче родитель не больше потомков, в max-куче — не меньше. Ниже — виды, хранение в памяти, операции, обходы и таблица применения. Код проверен на Python 3.14.

Что такое двоичное дерево: термины

Короткий словарь, которого хватит для статьи:

• Корень — единственный узел без родителя.
• Лист — узел без потомков; остальные узлы называют внутренними.
• Поддерево — узел вместе со всеми его потомками; у каждого узла есть левое и правое поддерево (возможно, пустое).
• Высота — число уровней от корня до самого дальнего листа. Ее считают в уровнях или в ребрах; дальше в коде — в уровнях.

Двоичное дерево — не просто «дерево со степенью не больше 2». В двоичном дереве узел с единственным левым потомком и узел с единственным правым — разные деревья, а в обычном дереве такого различия нет. Общие термины и три рекурсивных обхода подробно разобраны в статье Дерево как структура данных, здесь фокус на двоичном случае.

Виды двоичных деревьев

В русских источниках названия видов путаются: «полным» называют то full, то complete, то perfect. Поэтому в таблице рядом дан английский термин и проверяемое условие.

Три полезных свойства, которые проверяются подсчетом:

• В совершенном дереве из h уровней ровно 2^h — 1 узлов и 2^(h-1) листьев: при h = 3 это 7 узлов и 4 листа.
• В строгом дереве листьев на один больше, чем внутренних узлов.
• Минимальное число уровней для n узлов — ⌈log2(n + 1)⌉: для 1000 узлов это 10 уровней, а у вырожденного дерева — все 1000.

Именно разница между 10 и 1000 уровнями объясняет, зачем нужны сбалансированные деревья.

Как двоичное дерево хранится в памяти

Есть два способа. Первый — узлы со ссылками left и right: подходит для любой формы дерева. Второй — массив без ссылок: подходит для почти полного дерева, потому что в нем нет «дыр». У узла с индексом i левый потомок лежит в 2i + 1, правый — в 2i + 2, родитель — в (i — 1) // 2.

import heapq

# Почти полное (complete) дерево в массиве: потомки узла i лежат в 2*i+1 и 2*i+2
tree = [8, 3, 10, 1, 6, 9, 14]

def children(i):
    kids = [j for j in (2 * i + 1, 2 * i + 2) if j < len(tree)]
    return [tree[j] for j in kids]

for i, value in enumerate(tree):
    parent = tree[(i - 1) // 2] if i > 0 else None
    print(f"индекс {i}: узел {value}, родитель {parent}, дети {children(i)}")

# heapq хранит двоичную кучу в обычном списке по той же схеме индексов
tasks = [(3, "отчет"), (1, "авария"), (2, "ревью")]
heapq.heapify(tasks)
print("корень кучи:", tasks[0])
print("порядок выдачи:", [heapq.heappop(tasks)[1] for _ in range(3)])

Вывод:

индекс 0: узел 8, родитель None, дети [3, 10]
индекс 1: узел 3, родитель 8, дети [1, 6]
индекс 2: узел 10, родитель 8, дети [9, 14]
индекс 3: узел 1, родитель 3, дети []
индекс 4: узел 6, родитель 3, дети []
индекс 5: узел 9, родитель 10, дети []
индекс 6: узел 14, родитель 10, дети []
корень кучи: (1, 'авария')
порядок выдачи: ['авария', 'ревью', 'отчет']

Модуль heapq — готовая двоичная куча: базовые функции работают с min-кучей, в корне (tasks[0]) всегда наименьший элемент, поэтому задача с приоритетом 1 выдается первой. С Python 3.14 в модуле есть и функции max-кучи (heapify_max, heappush_max, heappop_max); в более ранних версиях для max-кучи ключи хранят с обратным знаком. Вставка и извлечение стоят O(log n), потому что элемент «всплывает» или «тонет» только по одной ветви.

Бинарное дерево поиска: поиск, вставка, удаление

В двоичном дереве поиска (BST) для каждого узла все ключи левого поддерева меньше ключа узла, а все ключи правого — больше. Поиск и вставка идут от корня вниз: меньше — влево, больше — вправо. Сложнее всего удаление, у него три случая:

1. У узла нет потомков — просто убираем его.
2. Один потомок — ставим потомка на место узла.
3. Два потомка — берем минимальный ключ правого поддерева (преемника), копируем его в узел и удаляем преемника из правого поддерева. Симметричный вариант — максимум левого поддерева.

Полный пример: вставка без рекурсии, удаление всех трех случаев и проверка высоты при разном порядке вставки.

import random

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None

def insert(root, key):
    """Итеративная вставка: не упирается в лимит рекурсии."""
    new = Node(key)
    if root is None:
        return new
    cur = root
    while True:
        if key < cur.key:
            if cur.left is None:
                cur.left = new
                return root
            cur = cur.left
        elif key > cur.key:
            if cur.right is None:
                cur.right = new
                return root
            cur = cur.right
        else:
            return root  # дубликат не вставляем

def delete(node, key):
    if node is None:
        return None                      # ключа нет - дерево не меняется
    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        if node.left is None:            # случаи 1 и 2: ноль или один потомок
            return node.right
        if node.right is None:
            return node.left
        succ = node.right                # случай 3: два потомка
        while succ.left is not None:     # минимум правого поддерева
            succ = succ.left
        node.key = succ.key
        node.right = delete(node.right, succ.key)
    return node

def inorder(node):
    """Симметричный обход без рекурсии, через явный стек."""
    stack, out = [], []
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.key)
        node = node.right
    return out

def height(node):
    """Высота в уровнях, обход в ширину."""
    level, h = [node] if node else [], 0
    while level:
        h += 1
        level = [c for n in level for c in (n.left, n.right) if c]
    return h

root = None
for k in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, k)
root = delete(root, 3)    # у 3 два потомка: ее место займет 4
root = delete(root, 14)   # у 14 один потомок: 13 поднимется
root = delete(root, 7)    # 7 - лист: просто исчезает
root = delete(root, 99)   # такого ключа нет
print("после удалений:", inorder(root))
print("корень левого поддерева:", root.left.key)

n = 1000
chain = None
for k in range(1, n + 1):          # ключи по возрастанию
    chain = insert(chain, k)
keys = list(range(1, n + 1))
random.seed(42)
random.shuffle(keys)
mixed = None
for k in keys:                     # те же ключи в случайном порядке
    mixed = insert(mixed, k)
print("высота, вставка по порядку:", height(chain))
print("высота, случайный порядок:", height(mixed))

Вывод:

после удалений: [1, 4, 6, 8, 10, 13]
корень левого поддерева: 4
высота, вставка по порядку: 1000
высота, случайный порядок: 21

Симметричный обход выдал ключи по возрастанию — значит, после удалений правило BST не нарушено. Число 21 получено в одном прогоне с random.seed(42), при другом порядке оно будет другим, но близкого порядка.

Главный вывод из последних двух строк: оценка O(log n) для BST верна только для сбалансированного дерева. Операции стоят O(h), где h — высота, и в худшем случае h = n. Отсортированные данные превращают BST в список. Поэтому в библиотеках используют самобалансирующиеся деревья: например, java.util.TreeMap по документации построен на красно-черном дереве. Удаление в примере рекурсивное: для учебного дерева этого достаточно, на вырожденном дереве его стоит переписать циклом так же, как вставку.

Обходы двоичного дерева: в глубину и в ширину

Обход — посещение каждого узла ровно один раз. Порядки различаются моментом, когда обрабатывается сам узел.

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

from collections import deque

class Node:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

# Дерево выражения (2 + 3) * (7 - 4): операции во внутренних узлах, числа в листьях
expr = Node("*", Node("+", Node(2), Node(3)), Node("-", Node(7), Node(4)))

def preorder(n):
    return [] if n is None else [n.value] + preorder(n.left) + preorder(n.right)

def postorder(n):
    return [] if n is None else postorder(n.left) + postorder(n.right) + [n.value]

def by_levels(root):
    out, queue = [], deque([root])
    while queue:
        n = queue.popleft()
        out.append(n.value)
        queue.extend(c for c in (n.left, n.right) if c)
    return out

def evaluate(n):
    """Вычисление = обратный обход: сначала операнды, потом операция."""
    if n.left is None and n.right is None:
        return n.value
    a, b = evaluate(n.left), evaluate(n.right)
    return {"+": a + b, "-": a - b, "*": a * b}[n.value]

print("прямой:  ", " ".join(map(str, preorder(expr))))
print("обратный:", " ".join(map(str, postorder(expr))))
print("в ширину:", " ".join(map(str, by_levels(expr))))
print("значение:", evaluate(expr))

Вывод:

прямой:   * + 2 3 - 7 4
обратный: 2 3 + 7 4 - *
в ширину: * + - 2 3 7 4
значение: 15

Прямой обход дал польскую (префиксную) запись, обратный — обратную польскую, которую вычисляют стеком. Это дерево строгое: у каждой операции ровно два операнда. Симметричный обход здесь дал бы 2 + 3 * 7 - 4 — без скобок он теряет порядок действий, поэтому для вывода выражения скобки добавляют при обходе.

Назначение и применение двоичных деревьев

Выбор структуры идет от задачи, а не от названия дерева:

Если ключи лежат на диске, а не в памяти, двоичное дерево обычно проигрывает: индексы СУБД строят на B-деревьях, у которых у узла много потомков и меньше чтений с диска. Для точного поиска по ключу без порядка чаще хватает хеш-таблицы (dict), дерево нужно, когда важны порядок, минимум или диапазоны.

Если не получилось

Типичные симптомы и причины:

• RecursionError на большом дереве. Рекурсивный обход вырожденного дерева уходит на глубину n.
• Ключи теряются при вставке. Нет ветки для равных ключей или не возвращается корень из рекурсивной функции.
• После удаления пропало поддерево. В случае с двумя потомками узел удален целиком вместо замены преемником.

Первый симптом легко воспроизвести — рекурсивный симметричный обход цепочки из 5000 узлов:

import sys

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None

def inorder_rec(node, out):
    if node:
        inorder_rec(node.left, out)
        out.append(node.key)
        inorder_rec(node.right, out)

root = cur = Node(1)
for k in range(2, 5001):   # вырожденное дерево-«цепочка» из 5000 узлов
    cur.right = Node(k)
    cur = cur.right

print("лимит рекурсии:", sys.getrecursionlimit())
out = []
inorder_rec(root, out)

Результат на Python 3.14 (фрагмент):

лимит рекурсии: 1000
Traceback (most recent call last):
  ...
RecursionError: maximum recursion depth exceeded

Исправление — не поднимать лимит, а обходить итеративно: функция inorder со стеком из раздела про BST обработает те же 5000 узлов без ошибки. Лучшая защита — не допускать вырождения: минимальная высота для 5000 узлов — 13 уровней, и у AVL или красно-черного дерева она того же порядка, а не 5000.

Выводы

• Двоичное дерево — узлы с не более чем двумя упорядоченными потомками; дерево поиска и куча — это двоичные деревья с дополнительным правилом порядка.
• Названия видов путаются, поэтому проверяйте условие: строгое (0 или 2 потомка), почти полное (без дыр по уровням), совершенное, сбалансированное.
• Почти полное дерево удобно хранить в массиве по индексам 2i + 1 и 2i + 2 — так устроен heapq.
• Операции BST стоят O(h): при балансе это O(log n), при отсортированной вставке высота растет до n.
• Порядок обхода выбирают под задачу: in-order для сортировки ключей, post-order для вычисления выражений, обход в ширину — по уровням через очередь.

Где применяется / связь с практикой

FAQ

Чем двоичное дерево отличается от двоичного дерева поиска?
Двоичное дерево ограничивает только число потомков. В дереве поиска дополнительно действует правило: слева меньшие ключи, справа большие, поэтому по нему можно искать за O(h).

Можно ли хранить в BST одинаковые ключи?
Можно, если заранее договориться: считать равные ключи правыми (или левыми) потомками либо хранить в узле счетчик повторов. В примере выше дубликаты просто игнорируются.

Куча — это дерево поиска?
Нет. В куче известно только, что родитель не больше потомков, порядок между левым и правым поддеревом не задан, поэтому искать произвольный ключ в ней приходится перебором.