Что такое бинарное дерево?

# Бинарное дерево

Бинарное дерево — это структура данных, где каждый узел имеет максимум двух потомков: левого и правого. Это иерархическая структура, похожая на перевёрнутое дерево в природе.

Базовая структура

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None   # Левый потомок
        self.right = None  # Правый потомок

Визуализация

        1 (корень)
       / \
      2   3
     / \
    4   5

Это бинарное дерево с 5 узлами. Узел 1 — корень, узлы 4 и 5 — листья (нет потомков).

Типы бинарных деревьев

1. Полное бинарное дерево (Full Binary Tree)

Каждый узел имеет 0 или 2 потомков.

        1
       / \
      2   3
     / \ / \
    4  5 6  7

2.完整二叉树 (Complete Binary Tree)

Все уровни заполнены, кроме последнего (заполняется слева направо).

        1
       / \
      2   3
     / \ /
    4  5 6

3. Perfect Binary Tree (Совершенное)

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

        1
       / \
      2   3
     / \ / \
    4  5 6  7

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

Высота левого и правого поддеревьев отличается максимум на 1.

5. Бинарное дерево поиска (BST — Binary Search Tree)

Для каждого узла: все значения в левом поддереве < значение узла < все значения в правом поддереве.

        5
       / \
      3   7
     / \ / \
    2  4 6  8

Это упорядоченная структура! Можно быстро искать элементы.

Основные операции

Поиск

def search(node, value):
    # Базовый случай
    if node is None:
        return False
    
    if node.value == value:
        return True
    elif value < node.value:
        return search(node.left, value)  # Ищем слева
    else:
        return search(node.right, value)  # Ищем справа

Вставка

def insert(node, value):
    if node is None:
        return TreeNode(value)
    
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    
    return node

# Использование
root = None
root = insert(root, 5)
root = insert(root, 3)
root = insert(root, 7)

Удаление

def delete(node, value):
    if node is None:
        return None
    
    if value < node.value:
        node.left = delete(node.left, value)
    elif value > node.value:
        node.right = delete(node.right, value)
    else:
        # Найдён узел для удаления
        
        # Случай 1: Нет потомков (листь)
        if node.left is None and node.right is None:
            return None
        
        # Случай 2: Один потомок
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        
        # Случай 3: Два потомка
        # Найти минимальный в правом поддереве
        min_larger_node = find_min(node.right)
        node.value = min_larger_node.value
        node.right = delete(node.right, min_larger_node.value)
    
    return node

Обход дерева

In-order (Симметричный обход)

Лево → Узел → Право. Для BST даёт отсортированный порядок.

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.value)
    inorder(node.right)

# Результат для BST выше: 2, 3, 4, 5, 6, 7, 8

Pre-order (Прямой обход)

Узел → Левo → Право. Полезен для копирования дерева.

def preorder(node):
    if node is None:
        return
    print(node.value)
    preorder(node.left)
    preorder(node.right)

# Результат для BST: 5, 3, 2, 4, 7, 6, 8

Post-order (Обратный обход)

Лево → Право → Узел. Полезен для удаления дерева.

def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.value)

# Результат для BST: 2, 4, 3, 6, 8, 7, 5

Level-order (Уровневый обход)

Читаем уровень за уровнем. Нужна очередь (BFS).

from collections import deque

def levelorder(node):
    if node is None:
        return
    
    queue = deque([node])
    while queue:
        current = queue.popleft()
        print(current.value)
        if current.left:
            queue.append(current.left)
        if current.right:
            queue.append(current.right)

# Результат: 5, 3, 7, 2, 4, 6, 8

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

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

• Поиск: O(log n)
• Вставка: O(log n)
• Удаление: O(log n)

Несбалансированное BST (худший случай — цепочка)

    1
     \
      2
       \
        3  <- деградирует в связный список!

• Поиск: O(n)
• Вставка: O(n)
• Удаление: O(n)

Высота и размер

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

def size(node):
    if node is None:
        return 0
    return 1 + size(node.left) + size(node.right)

Практические применения

1. Binary Search Trees — быстрый поиск и сортировка
2. AVL Trees / Red-Black Trees — самобалансирующиеся для гарантированной O(log n)
3. Heap — приоритетные очереди, сортировка
4. Expression Trees — вычисление математических выражений
5. Huffman Trees — сжатие данных
6. DOM в браузере — структура HTML документа

Важные свойства

• Минимальная высота: log₂(n) при идеальной балансировке
• Максимальная высота: n при цепочке узлов
• Всегда рекурсивная структура: дерево — это узел + два дерева
• Для BST: инфиксный обход даёт отсортированный порядок

Бинарные деревья — фундаментальная структура данных, появляется везде: от базовых алгоритмов до сложных СУБД и систем индексирования.