Бинарное дерево как частный случай

В прошлом уроке мы рассмотрели деревья в общем виде — узлы могут иметь любое число детей. Сейчас сузим до бинарного дерева: каждый узел имеет максимум 2 ребёнка. Обычно их называют left и right, и их позиция (левый/правый) важна.

Зачем сужать? Потому что бинарные деревья:

1. Просты в реализации: два указателя left/right на узел вместо переменного списка children.
2. Дают логарифмическую высоту: при N узлов сбалансированное бинарное дерево имеет высоту log2(N) ≈ 20 для миллиона записей.
3. Лежат в основе многих алгоритмов: BST, AVL, red-black, heap, segment tree.

Многие реальные структуры — не бинарные (B-tree имеет сотни детей на узел), но изучение бинарных деревьев даёт главные интуиции, которые потом обобщаются.

Структура узла

class BinaryTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None    # левый ребёнок или None
        self.right = None   # правый ребёнок или None

В отличие от общего дерева, здесь две конкретные ссылки. None означает «нет ребёнка». Лист имеет left == right == None.

# простое бинарное дерево
#       1
#      / \
#     2   3
#    / \
#   4   5

root = BinaryTreeNode(1)
root.left = BinaryTreeNode(2)
root.right = BinaryTreeNode(3)
root.left.left = BinaryTreeNode(4)
root.left.right = BinaryTreeNode(5)

Виды бинарных деревьев

Это самая путаная часть терминологии. Разберём четыре основных типа.

Full binary tree

Каждый узел либо лист, либо имеет ровно 2 детей. Никогда 1.

      1
     / \
    2   3
   / \
  4   5

Это full (всё что не лист — имеет 2 детей: 1 имеет 2, 2 имеет 2).

      1
     / \
    2   3
   /
  4

Это НЕ full (узел 2 имеет одного ребёнка).

Complete binary tree

Все уровни кроме последнего заполнены полностью. Последний уровень заполнен слева направо, без «дырок».

      1
     / \
    2   3
   / \  /
  4  5 6     -- complete: дырок справа нет

      1
     / \
    2   3
   /     \
  4       5    -- НЕ complete: на последнем уровне дырка между 4 и 5

Complete tree важно потому, что его можно компактно хранить в массиве — без указателей. Это основа heap (модуль 11).

Perfect binary tree

Все уровни заполнены полностью. Все листья на одной глубине. Это «идеальное» бинарное дерево.

      1
     / \
    2   3
   /\   /\
  4 5  6 7   -- perfect: 7 узлов, h=2, идеальная симметрия

Perfect tree с высотой h имеет ровно 2^(h+1) - 1 узлов. Это и full, и complete одновременно.

Balanced binary tree

«Сбалансированное» — слабее, чем perfect. Точное определение разное в разных вариантах, но идея одна: высота поддеревьев не сильно отличается.

Самое строгое — AVL: разница высот left и right поддеревьев каждого узла не больше 1.

      1
     / \
    2   3
   / \   \
  4   5   6   -- balanced (AVL): для каждого узла |h(left) - h(right)| <= 1

Балансировка даёт высоту O(log N) — это и есть главное практическое требование в BST.

Memory layout: linked vs array

Бинарное дерево можно хранить двумя способами:

Linked representation

Каждый узел — отдельный объект в памяти, связан указателями:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None    # указатель
        self.right = None   # указатель

• Память: на узел нужно value + 2 указателя = ~24-32 байта. Узлы разбросаны по heap’у.
• Cache behaviour: плохой. Каждый шаг по дереву = chase указателя в случайное место памяти, потенциальный cache miss.
• Гибкость: дерево может быть любой формы.

Array representation

Для complete binary tree можно хранить узлы в массиве, используя формулы:

# для индекса i:
parent = (i - 1) // 2
left_child = 2 * i + 1
right_child = 2 * i + 2

tree = [1, 2, 3, 4, 5, 6, 7]
#         1 (idx 0)
#       /   \
#      2     3  (idx 1, 2)
#     / \   / \
#    4  5  6  7 (idx 3-6)

• Память: только value на узел. Никаких указателей. Очень компактно.
• Cache behaviour: отличный. Узлы лежат подряд, доступ — sequential.
• Гибкость: работает только для complete trees. Если есть «дырки», массив будет содержать None’ы и тратить память.

Применения

Linked: для BST с произвольной формой

Когда дерево не обязательно complete (большинство BST), linked — единственный вариант.

Array: для heap

Heap всегда complete (это инвариант). Поэтому array-layout идеальный: heappush делает O(log n) sift up с sequential доступом по индексу. Все детали в модуле 11.

Array: для огромных перфектных деревьев

Например, segment tree для интервальных запросов — обычно array-based. Когда N известно заранее (например, 1M), выделяется массив 4N и в нём строится дерево.

Сложность операций

Все операции на бинарном дереве работают за O(h), где h — высота:

• Поиск (для BST): O(h)
• Вставка: O(h)
• Удаление: O(h)
• Обход всего дерева: O(N)

Поэтому главная задача при использовании дерева — минимизировать высоту. Для сбалансированного дерева h = log2(N), для вырожденного h = N - 1 (катастрофа).

Эксперимент: размер дерева в памяти

import sys

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

# linked tree из 100 узлов
def build_linked(n):
    if n == 0:
        return None
    root = Node(0)
    nodes = [root]
    for i in range(1, n):
        parent = nodes[(i - 1) // 2]
        new_node = Node(i)
        if parent.left is None:
            parent.left = new_node
        else:
            parent.right = new_node
        nodes.append(new_node)
    return root, nodes

root, nodes = build_linked(1000)

# подсчёт памяти
total_linked = sum(sys.getsizeof(n) for n in nodes)
print(f"Linked tree (1000 nodes): ~{total_linked} bytes")
# ~56000 bytes (56 байт на узел: 16 header + 24 __slots__ + value + 2 pointers)

# array tree
arr = list(range(1000))
print(f"Array tree (1000 nodes): {sys.getsizeof(arr)} bytes")
# ~8000 bytes (только int объекты + list overhead)

# для большого N разница ~6-7×

Попробуй сам

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

# 1. Высота дерева (рекурсия)
def height(node):
    if node is None:
        return -1   # высота пустого "дерева" = -1, для листа 0
    return 1 + max(height(node.left), height(node.right))

# 2. Подсчёт узлов
def count_nodes(node):
    if node is None:
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)

# 3. Является ли дерево perfect?
def is_perfect(node):
    if node is None:
        return True
    n = count_nodes(node)
    h = height(node)
    return n == 2 ** (h + 1) - 1

# 4. Является ли дерево balanced (AVL-style)?
def is_balanced(node):
    if node is None:
        return True
    h_left = height(node.left)
    h_right = height(node.right)
    if abs(h_left - h_right) > 1:
        return False
    return is_balanced(node.left) and is_balanced(node.right)

# постройте дерево и протестируйте
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

print(f"height = {height(root)}")       # 2
print(f"nodes = {count_nodes(root)}")   # 7
print(f"perfect = {is_perfect(root)}")  # True
print(f"balanced = {is_balanced(root)}") # True

# 5. Array layout: реализуйте left_child, right_child, parent для индекса
def left_child(i):
    return 2 * i + 1

def right_child(i):
    return 2 * i + 2

def parent(i):
    return (i - 1) // 2

# проверьте на этом дереве
arr = [1, 2, 3, 4, 5, 6, 7]
for i in range(7):
    lc = left_child(i)
    rc = right_child(i)
    p = parent(i)
    lc_val = arr[lc] if lc < 7 else None
    rc_val = arr[rc] if rc < 7 else None
    p_val = arr[p] if i > 0 else None
    print(f"arr[{i}]={arr[i]}: left={lc_val}, right={rc_val}, parent={p_val}")

В следующем уроке — обходы дерева: pre-order, in-order, post-order, level-order (BFS). Что каждый делает и где применяется.