Деревья и кучи

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

  • Университет
  • 25 мин
  • 10 вопросов
  • Урок 49 из 59

В этом уроке ты узнаешь

  • Обходить двоичное дерево в прямом, симметричном, обратном порядке и по уровням
  • Выполнять поиск, вставку и удаление в двоичном дереве поиска и объяснять стоимость O(h)
  • Отслеживать вставку и извлечение минимума в куче на её представлении массивом

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

Двоичные деревья и их обходы

Двоичное деревоОпределение

Дерево, в котором у каждого узла не более двух потомков (левого и правого). Верхний узел — корень, узел без потомков — лист. Глубина узла — число рёбер от корня до него, высота дерева h — наибольшая глубина.

n ≤ 2ʰ⁺¹ − 1 ⇒ h ≥ ⌈log₂(n + 1)⌉ − 1 ≈ log₂ n

Где

n
число узлов
h
высота дерева (в рёбрах)

На глубине d помещается не более 2ᵈ узлов: 1 + 2 + 4 + … + 2ʰ = 2ʰ⁺¹ − 1. Значит, высота двоичного дерева из n узлов не может быть меньше примерно log₂ n, но может достигать n − 1.

Text
          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80
       /
     35
Пример дерева: ключи 50, 30, 70, 20, 40, 60, 80, 35 вставлены в этом порядке в двоичное дерево поиска. Высота h = 3 (50 → 30 → 40 → 35).
ОбходПравилоРезультат для примераГде применяется
Прямой (preorder)корень, левое, правое50 30 20 40 35 70 60 80копирование дерева
Симметричный (inorder)левое, корень, правое20 30 35 40 50 60 70 80ключи в отсортированном порядке
Обратный (postorder)левое, правое, корень20 35 40 30 60 80 70 50удаление, подсчёт размера папок
По уровнямс очередью, сверху вниз50 30 70 20 40 60 80 35кратчайшие пути, печать по уровням
Каждый обход посещает каждый узел один раз — O(n).

Чтобы читать дальше, зарегистрируйся бесплатно

Остальные разделы урока, тест и заметки открываются с аккаунтом Educora. Регистрация занимает минуту, а прогресс сохраняется на всех твоих устройствах.

Двоичные деревья поиска (BST)

В двоичном дереве поиска для каждого узла все ключи левого поддерева меньше его, а правого — больше. Поиск начинается с корня: если ключ меньше — идём влево, если больше — вправо; это древесный вариант двоичного поиска. Вставка тем же путём находит свободное место. Обе операции занимают O(h).

Пример 1: удаление узла с двумя потомками

Задача

Удали 30 из дерева-примера. Каким будет симметричный обход после удаления?

Показать решениеСкрыть решение

Решение

У удаления три случая: лист просто удаляется; узел с одним потомком заменяется этим потомком; узел с двумя потомками заменяется симметричным преемником — наименьшим ключом правого поддерева.
У 30 два потомка (20 и 40). Правое поддерево: 40 → 35. Наименьший ключ — 35 (идём влево до упора).
Записываем 35 на место 30 и удаляем 35 со старого места (это лист).
Новое дерево: 50 → (35 → 20, 40), (70 → 60, 80).
Симметричный обход: 20 35 40 50 60 70 80 — по-прежнему по возрастанию, свойство BST сохранено.
Python
class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

def inorder(t):
    return inorder(t.left) + [t.key] + inorder(t.right) if t else []
def preorder(t):
    return [t.key] + preorder(t.left) + preorder(t.right) if t else []
def height(t):
    return -1 if t is None else 1 + max(height(t.left), height(t.right))

root = chain = None
for k in [50, 30, 70, 20, 40, 60, 80, 35]:
    root = insert(root, k)
for k in range(1, 9):
    chain = insert(chain, k)
print('inorder: ', inorder(root))
print('preorder:', preorder(root))
print('height:', height(root), '| sorted input height:', height(chain))
Ожидаемый результат
inorder:  [20, 30, 35, 40, 50, 60, 70, 80]
preorder: [50, 30, 20, 40, 35, 70, 60, 80]
height: 3 | sorted input height: 7
Один и тот же код строит два дерева. Восемь ключей в перемешанном порядке дают дерево высоты 3, а упорядоченные ключи 1, 2, …, 8 — «цепочку» высоты 7, по сути связный список с поиском O(n).

Выход — сбалансированные деревья: после каждой вставки и удаления они с помощью поворотов (rotation) удерживают высоту O(log n). В АВЛ-дереве высоты левого и правого поддеревьев любого узла отличаются не больше чем на 1 (h < 1,44 log₂ n); в красно-чёрном дереве h ≤ 2 log₂(n + 1). TreeMap в Java и std::map в C++ — красно-чёрные деревья, а индексы баз данных — B-деревья, хранящие в каждом узле сотни ключей.

Кучи и очереди с приоритетом

Двоичная куча (min-heap)Определение

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

left(i) = 2i + 1right(i) = 2i + 2parent(i) = ⌊(i − 1) / 2⌋left(i) = 2i + 1right(i) = 2i + 2parent(i) = ⌊(i − 1) / 2⌋

Где

i
индекс узла в массиве (с 0)

Дерево записывается в массив по уровням; так как оно полное, пропусков нет, а высота равна ⌊log₂ n⌋.

Пример 2: вставка в кучу и извлечение минимума

Задача

Min-куча: [3, 5, 8, 10, 7]. а) Вставь 2. б) Затем извлеки минимум. Записывай массив после каждого шага.

Показать решениеСкрыть решение

Решение

а) Всплытие (sift-up): 2 записывается в конец, индекс 5 → [3, 5, 8, 10, 7, 2].
parent(5) = 2, там 8 > 2 → меняем → [3, 5, 2, 10, 7, 8].
parent(2) = 0, там 3 > 2 → меняем → [2, 5, 3, 10, 7, 8]. Дошли до корня.
б) Погружение (sift-down): забираем корень 2, последний элемент 8 ставим в корень → [8, 5, 3, 10, 7].
Потомки: 5 (i = 1) и 3 (i = 2); меньший — 3 → меняем → [3, 5, 8, 10, 7].
У i = 2 потомков нет (индексы 5 и 6 за пределами массива) → [3, 5, 8, 10, 7], извлечено 2.
Каждая операция делает не больше h = ⌊log₂ n⌋ обменов → O(log n).
Python
import heapq

heap = [3, 5, 8, 10, 7]
heapq.heappush(heap, 2)
print(heap)
print(heapq.heappop(heap), heap)

patients = []
for urgency, name in [(3, 'Aysel'), (1, 'Murad'), (2, 'Leyla'), (1, 'Elvin')]:
    heapq.heappush(patients, (urgency, name))
while patients:
    print(heapq.heappop(patients))

def heap_sort(a):
    h = a[:]
    heapq.heapify(h)
    return [heapq.heappop(h) for _ in range(len(h))]

print(heap_sort([9, 4, 7, 1, 8, 2]))
Ожидаемый результат
[2, 5, 3, 10, 7, 8]
2 [3, 5, 8, 10, 7]
(1, 'Elvin')
(1, 'Murad')
(2, 'Leyla')
(3, 'Aysel')
[1, 2, 4, 7, 8, 9]
Модуль heapq в Python — это min-куча на обычном list: результат совпадает с ручной трассировкой. Пациенты хранятся парами (срочность, имя): меньшее число срочнее, при равенстве сравниваются имена. heapify + n раз heappop = пирамидальная сортировка.
T(build-heap) ≤ ∑ₕ (n / 2ʰ⁺¹) · h = (n/2) · ∑ₕ h / 2ʰ ≤ (n/2) · 2 = n = O(n)T(build-heap) ≤ ∑ₕ (n / 2ʰ⁺¹) · h = (n/2) · ∑ₕ h / 2ʰ ≤ (n/2) · 2 = n = O(n)

Где

h
высота узла над листьями
n / 2ʰ⁺¹n / 2ʰ⁺¹
число узлов высоты h (примерно)

heapify превращает массив в кучу снизу вверх: половина узлов — листья (0 работы), четверть погружается на 1 шаг и т. д. Поскольку ∑ h/2ʰ = 2, всего получается O(n), а не O(n log n). Пирамидальная сортировка затем делает n извлечений — O(n log n).

ОперацияСбалансированное BSTНесбалансированное BST (худший)Двоичная куча
поиск любого ключаO(log n)O(n)O(n)
вставкаO(log n)O(n)O(log n)
посмотреть минимумO(log n)O(n)O(1)
извлечь минимумO(log n)O(n)O(log n)
построить из n элементовO(n log n)O(n²)O(n)

Запомни

  • Высота двоичного дерева из n узлов не меньше ≈ log₂ n и не больше n − 1.
  • Прямой, симметричный и обратный обходы определяются местом корня; симметричный обход BST выдаёт ключи по возрастанию.
  • Операции BST — O(h); сбалансированные деревья (АВЛ, красно-чёрные, B-деревья) удерживают h = O(log n).
  • Куча — полное дерево в массиве: потомки в 2i + 1 и 2i + 2; вставка и извлечение минимума — O(log n), построение — O(n).
  • Очередь с приоритетом строится на куче; пирамидальная сортировка — O(n log n), на месте, но неустойчивая.
Заметил ошибку или неточность в уроке?

Проверь себя

Вопросов: 10. Каждый правильный ответ приносит XP.

Вопрос 1 / 10

Вопрос 1 / 10. Ключи 8, 3, 10, 1, 6 вставляются в этом порядке в пустое BST. Каков его обратный (postorder) обход?