Patricia Trie (Radix Tree / PATRICIA)

Что такое Patricia Trie

PATRICIA — Practical Algorithm To Retrieve Information Coded In Alphanumeric.
Предложена Дональдом Морриссоном в 1968 году.

Patricia Trie = сжатый Trie, в котором цепочки узлов с одним ребёнком сжимаются в одно ребро с меткой (строкой, а не символом). Это устраняет главную проблему обычного Trie — избыточные узлы.

Ключевая идея: сжатие путей

Обычный Trie для "interview", "internal", "intro":

root → i → n → t → e → r → v → i → e → w ✓
                          ↘ n → a → l ✓
               ↘ r → o ✓

Patricia Trie:

root → "int" → "er" → "view" ✓
                    ↘ "nal"  ✓
            ↘ "ro"  ✓

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

Слова: cat, car, card, care, bat, bad

Каждое ребро теперь несёт строку, а не один символ

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

┌──────────────────────────────────────┐
│  children: map<string → Node>        │  ← ключ ребра — строка (метка)
│  is_end: bool                        │
│  value: any                          │
└──────────────────────────────────────┘

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

➕ Вставка — O(m)

При вставке возможны три ситуации:

Случай 1: Метка совпадает полностью

Есть ребро "car", вставляем "car" → просто is_end = true

Случай 2: Новое слово — префикс метки

Есть ребро "card", вставляем "car":
  Разбиваем "card" → "car" (is_end=true) + "d" (is_end=true, дочерний)

Случай 3: Нужно разбить метку

Есть ребро "card", вставляем "care":
  Общий префикс: "car"
  Разбиваем → "car" → "d" ✓
                     ↘ "e" ✓

def insert(node, word):
    for label, child in node.children.items():
        common = longest_common_prefix(label, word)
        if not common:
            continue
        if common == label:                  # случай 1/2
            insert(child, word[len(common):])
        else:                                # случай 3 — split
            split_node = Node()
            split_node.children[label[len(common):]] = child
            node.children[common] = split_node
            node.children.pop(label)
            if word == common:
                split_node.is_end = True
            else:
                split_node.children[word[len(common):]] = Node(is_end=True)
        return
    node.children[word] = Node(is_end=True)  # новая ветка

🔍 Поиск — O(m)

Поиск "care" в Patricia Trie:
  root: смотрим дочерние метки
  Совпадает "ca" → переходим, остаток "re"
  Совпадает "r"  → переходим, остаток "e"
  Совпадает "e"  → переходим, остаток ""
  is_end = true  → НАЙДЕНО ✓

➖ Удаление — O(m)

После удаления узла — объединяем родителя и единственного оставшегося ребёнка:

Удаляем "card", остаётся только "care":
  Узел "car" → {"d": ✓, "e": ✓}
  После удаления "d":
  Узел "car" → {"e": ✓}  →  схлопываем в "care" ✓

Trie vs Patricia Trie — сравнение

{
  "title": { "text": "Количество узлов: Trie vs Patricia", "left": "center" },
  "tooltip": { "trigger": "axis" },
  "legend": { "data": ["Trie", "Patricia Trie"], "bottom": 0 },
  "xAxis": {
    "type": "category",
    "name": "Число слов",
    "data": ["10", "50", "100", "500", "1000"]
  },
  "yAxis": {
    "type": "value",
    "name": "Узлов (примерно)"
  },
  "series": [
    {
      "name": "Trie",
      "type": "line",
      "data": [60, 310, 650, 3400, 7000],
      "smooth": true,
      "lineStyle": { "color": "#d9534f", "width": 3 }
    },
    {
      "name": "Patricia Trie",
      "type": "line",
      "data": [19, 99, 199, 999, 1999],
      "smooth": true,
      "lineStyle": { "color": "#5cb85c", "width": 3 }
    }
  ]
}

Варианты и применение

Radix Tree (Radix Trie)

Обобщение Patricia Trie — сжатие по группам битов (radix 2, 4, 8...).
Используется в ядре Linux для хранения адресного пространства процессов.

Где применяется Patricia / Radix Tree

Итоговое сравнение всех трёх структур

Input

добавляем описание Binary-Heap :)

Result

Binary Heap (Двоичная куча)

Что такое Binary Heap

Binary Heap — полное двоичное дерево, удовлетворяющее свойству кучи: каждый узел больше (или меньше) своих потомков. Это делает кучу идеальной структурой для реализации приоритетных очередей.

Предложена Дж. Уильямсом в 1964 году как основа алгоритма HeapSort.

Два вида кучи

Ключевые свойства

Хранение в массиве

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

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

Массив: [ _, 1, 3, 2, 7, 4, 5, 6 ]  (индекс с 1)
            0  1  2  3  4  5  6  7

Навигация по индексам:

Для узла с индексом i:
┌─────────────────────────────────┐
│  Родитель   →  i / 2            │
│  Левый сын  →  2 * i            │
│  Правый сын →  2 * i + 1        │
└─────────────────────────────────┘

(при индексации с 0: parent = (i-1)/2, left = 2i+1, right = 2i+2)

Визуализация Max-Heap

Массив: [100, 85, 90, 70, 60, 75, 80, 40, 50, 55]
Индекс:   0    1   2   3   4   5   6   7   8   9

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

🔼 Sift Up (всплытие) — вспомогательная

Используется после вставки: новый элемент добавляется в конец и «всплывает» вверх.

Вставка 95 в Max-Heap:

[100, 85, 90, 70, 60, 75, 80, 40, 50, 55, 95]
                                           ↑ добавили в конец

95 > 60 (родитель) → меняем местами
95 > 85 (родитель) → меняем местами
95 < 100 (родитель) → стоп

Результат: [100, 95, 90, 70, 85, 75, 80, 40, 50, 55, 60]

def sift_up(heap, i):
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] > heap[parent]:      # для Max-Heap
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
        else:
            break

🔽 Sift Down (погружение) — вспомогательная

Используется после удаления корня: последний элемент ставится на место корня и «тонет» вниз.

Удаление корня 100:
  Ставим последний элемент (60) на место корня
  [60, 95, 90, 70, 85, 75, 80, 40, 50, 55]

  60 < max(95, 90) = 95 → меняем с левым
  [95, 60, 90, 70, 85, 75, 80, 40, 50, 55]

  60 < max(70, 85) = 85 → меняем с правым
  [95, 85, 90, 70, 60, 75, 80, 40, 50, 55]

  60 > нет детей → стоп  ✓

def sift_down(heap, i, n):
    while True:
        largest = i
        left, right = 2*i + 1, 2*i + 2
        if left < n and heap[left] > heap[largest]:
            largest = left
        if right < n and heap[right] > heap[largest]:
            largest = right
        if largest == i:
            break
        heap[i], heap[largest] = heap[largest], heap[i]
        i = largest

➕ Вставка — O(log n)

1. Добавить элемент в конец массива
2. Sift Up от добавленного элемента

def push(heap, val):
    heap.append(val)
    sift_up(heap, len(heap) - 1)

🏆 Получить максимум/минимум — O(1)

def peek(heap):
    return heap[0]    # просто смотрим корень

🗑️ Удаление корня (Extract Max/Min) — O(log n)

1. Запомнить корень (результат)
2. Поставить последний элемент на место корня
3. Уменьшить размер кучи на 1
4. Sift Down от корня

def pop(heap):
    heap[0], heap[-1] = heap[-1], heap[0]
    val = heap.pop()
    sift_down(heap, 0, len(heap))
    return val

🏗️ Построение кучи из массива — O(n)

Наивный способ (n вставок) = O(n log n)
Оптимальный способ (Флойд, 1964) = O(n) — sift_down от середины к корню:

def heapify(arr):
    n = len(arr)
    # Начинаем с последнего внутреннего узла
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)

Почему O(n)? Большинство узлов — листья (n/2 штук), 
они делают 0 операций. Узлы выше делают O(1), O(2)...
Суммарно: O(n) по формуле геометрической прогрессии.

HeapSort — O(n log n)

Куча лежит в основе классического алгоритма сортировки:

1. Построить Max-Heap из массива     → O(n)
2. n раз: извлечь максимум           → O(n log n)
   - поменять корень с последним
   - уменьшить размер кучи
   - sift_down

Сортировка на месте, без доп. памяти!

def heap_sort(arr):
    n = len(arr)
    heapify(arr)                           # O(n)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]   # корень в конец
        sift_down(arr, 0, i)              # O(log n)

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

{
  "title": { "text": "Сложность операций Binary Heap", "left": "center" },
  "tooltip": { "trigger": "axis" },
  "legend": { "data": ["O(1)", "O(log n)", "O(n)"], "bottom": 0 },
  "xAxis": {
    "type": "category",
    "data": ["1K", "10K", "100K", "1M", "10M"]
  },
  "yAxis": {
    "type": "value",
    "name": "Операций"
  },
  "series": [
    {
      "name": "O(1)",
      "type": "line",
      "data": [1, 1, 1, 1, 1],
      "smooth": true,
      "lineStyle": { "color": "#5cb85c", "width": 3 }
    },
    {
      "name": "O(log n)",
      "type": "line",
      "data": [10, 13, 17, 20, 23],
      "smooth": true,
      "lineStyle": { "color": "#f0ad4e", "width": 3 }
    },
    {
      "name": "O(n)",
      "type": "line",
      "data": [1000, 10000, 100000, 1000000, 10000000],
      "smooth": true,
      "lineStyle": { "color": "#d9534f", "width": 2, "type": "dashed" }
    }
  ]
}

Плюсы и минусы

Где используется

Итоговое сравнение всех четырёх структур

Input

добавляем Бинарное дерево поиска (BST)

Result

Бинарное дерево поиска (BST)

Что такое BST

Binary Search Tree — двоичное дерево, в котором для каждого узла выполняется инвариант BST:

Все ключи в левом поддереве  <  ключ узла
Все ключи в правом поддереве >  ключ узла

Это позволяет эффективно искать, вставлять и удалять элементы, используя принцип двоичного поиска на каждом шаге.

Основные свойства

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

┌──────────────────────────────────┐
│  key:   int/any                  │  ← ключ для сравнения
│  value: any        (опционально) │  ← полезная нагрузка
│  left:  *Node                    │  ← левый потомок (< key)
│  right: *Node                    │  ← правый потомок (> key)
│  parent: *Node     (опционально) │  ← родитель
└──────────────────────────────────┘

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

Вставка ключей в порядке: 50, 30, 70, 20, 40, 60, 80

In-Order обход: 20 → 30 → 40 → 50 → 60 → 70 → 80 ✓

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

🔍 Поиск — O(log n) / O(n)

На каждом шаге отбрасываем половину дерева:

Поиск 40:
  50: 40 < 50 → идём влево
  30: 40 > 30 → идём вправо
  40: 40 == 40 → НАЙДЕНО ✓

Поиск 45:
  50 → 30 → 40 → нет правого ребёнка → НЕ НАЙДЕНО ✗

def search(node, key):
    if node is None or node.key == key:
        return node
    if key < node.key:
        return search(node.left, key)
    return search(node.right, key)

➕ Вставка — O(log n) / O(n)

Спускаемся как при поиске, вставляем в найденное пустое место:

Вставка 35:
  50: 35 < 50 → влево
  30: 35 > 30 → вправо
  40: 35 < 40 → влево
  None → вставляем сюда!

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    # key == node.key: дубликат, игнорируем
    return node

➖ Удаление — O(log n) / O(n)

Три случая в зависимости от числа детей удаляемого узла:

Случай 1 — узел является листом:

Удаляем 20 (нет детей):
  Просто убираем узел
  30.left = None

Случай 2 — узел имеет одного ребёнка:

Удаляем 60 (один ребёнок):
  Заменяем узел его единственным ребёнком
  70.left = child(60)

Случай 3 — узел имеет двух детей:

Удаляем 30 (два ребёнка 20 и 40):

  Находим In-Order Successor (наименьший в правом поддереве)
  или In-Order Predecessor (наибольший в левом поддереве)

  In-Order Successor для 30 → 35
  Копируем ключ 35 в узел 30
  Удаляем узел 35 (он уже без левого ребёнка → случай 1 или 2)

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:
        # Случай 1 и 2
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        # Случай 3: находим In-Order Successor
        successor = find_min(node.right)
        node.key = successor.key
        node.right = delete(node.right, successor.key)
    return node

def find_min(node):
    while node.left:
        node = node.left
    return node

Обходы дерева

def inorder(node):
    if node:
        inorder(node.left)
        print(node.key)       # Left → Node → Right
        inorder(node.right)

def preorder(node):
    if node:
        print(node.key)       # Node → Left → Right
        preorder(node.left)
        preorder(node.right)

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.key)       # Left → Right → Node

Проблема вырождения

Главный недостаток BST — зависимость от порядка вставки:

Вырожденное дерево = связный список
Поиск: O(n) вместо O(log n) 😱

Решение → Самобалансирующиеся деревья:

Min / Max / Successor / Predecessor

# Минимум — самый левый узел
def find_min(node):
    while node.left:
        node = node.left
    return node

# Максимум — самый правый узел
def find_max(node):
    while node.right:
        node = node.right
    return node

# In-Order Successor (следующий по возрастанию)
def successor(node):
    if node.right:
        return find_min(node.right)
    # Идём вверх пока не выйдем из правого поддерева
    parent = node.parent
    while parent and node == parent.right:
        node, parent = parent, parent.parent
    return parent

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

{
  "title": { "text": "BST: сбалансированное vs вырожденное", "left": "center" },
  "tooltip": { "trigger": "axis" },
  "legend": { "data": ["O(log n) — сбалансированное", "O(n) — вырожденное"], "bottom": 0 },
  "xAxis": {
    "type": "category",
    "name": "Число элементов",
    "data": ["100", "1K", "10K", "100K", "1M"]
  },
  "yAxis": {
    "type": "value",
    "name": "Операций"
  },
  "series": [
    {
      "name": "O(log n) — сбалансированное",
      "type": "line",
      "data": [7, 10, 13, 17, 20],
      "smooth": true,
      "lineStyle": { "color": "#5cb85c", "width": 3 }
    },
    {
      "name": "O(n) — вырожденное",
      "type": "line",
      "data": [100, 1000, 10000, 100000, 1000000],
      "smooth": true,
      "lineStyle": { "color": "#d9534f", "width": 3, "type": "dashed" }
    }
  ]
}

Где используется

Итоговое сравнение всех пяти структур

* — O(log n) только для сбалансированного дерева; O(n) в худшем случае

Input

Бинарное дерево поиска (BST) vs Binary Heap

Result

BST vs Binary Heap

Главный вопрос

Обе структуры — двоичные деревья с упорядоченными элементами. Но они решают разные задачи и имеют принципиально разные инварианты.

Инвариант — ключевое различие

Один и тот же массив — два разных дерева

Данные: [20, 30, 40, 50, 60, 70, 80]

BST вырождается в список — O(n) для всех операций.
Heap всегда остаётся полным деревом — гарантированный O(log n).

Детальное сравнение операций

🔍 Поиск произвольного элемента

BST — поиск 40:
  50 → 30 → 40 ✓   (3 шага = O(log n))

  Каждый шаг отсекает половину дерева —
  левое или правое поддерево

Heap — поиск 40:
  80 → проверяем 70 и 60
     → проверяем 50, 40... ✓  но могли пойти и вправо

  Нет информации о горизонтальном порядке —
  нужно обойти всё дерево в худшем случае

Вывод: BST выигрывает — O(log n) vs O(n)

🏆 Получить максимум / минимум

Max-Heap — получить максимум:
  return heap[0]   ← просто корень, O(1) ✓

BST — получить максимум:
  идём по правым детям до конца
  O(log n) для сбалансированного
  O(n) для вырожденного

Min-Heap — получить минимум:
  return heap[0]   ← O(1) ✓

BST — получить минимум:
  идём по левым детям до конца
  O(log n) / O(n)

Вывод: Heap выигрывает — O(1) vs O(log n)

➕ Вставка

BST — вставка 45:
  50 → 30 → 40 → правый ребёнок пуст → вставляем
  Но! Может понадобиться ребалансировка (AVL/RB)

Heap — вставка 45:
  Добавляем в конец массива → sift up
  Гарантированно O(log n), без ребалансировки

➖ Удаление

Heap — удаление произвольного:
  1. Нужно НАЙТИ элемент → O(n)
  2. Только потом удалить → O(log n)
  Итого: O(n) — плохо!

  Удаление корня (min/max) — O(log n) ✓

BST — удаление любого:
  1. Найти → O(log n)
  2. Удалить (3 случая) → O(log n)
  Итого: O(log n) ✓

Вывод: BST выигрывает для произвольного удаления

📊 Хранение в памяти

Heap → массив (идеально):

  Индекс:  0   1   2   3   4   5   6
  Данные: [80, 70, 60, 50, 40, 30, 20]

  parent(i) = (i-1) / 2
  left(i)   = 2*i + 1
  right(i)  = 2*i + 2

  ✅ Нет указателей
  ✅ Cache-friendly
  ✅ Минимум памяти

BST → узлы с указателями:

  Node { key, left*, right*, parent* }

  ❌ Каждый узел = отдельная аллокация
  ❌ Указатели = доп. память
  ❌ Cache-miss при обходе

Визуальное сравнение сложностей

{
  "title": { "text": "Сравнение операций: BST vs Binary Heap", "left": "center" },
  "tooltip": { "trigger": "axis" },
  "legend": { "data": ["BST (сбалансированный)", "Binary Heap"], "bottom": 0 },
  "xAxis": {
    "type": "category",
    "data": ["Поиск любого", "Min/Max", "Вставка", "Удаление Min/Max", "Удаление любого", "Построение"]
  },
  "yAxis": {
    "type": "value",
    "name": "Условная сложность (n=1000)",
    "max": 1100
  },
  "series": [
    {
      "name": "BST (сбалансированный)",
      "type": "bar",
      "data": [10, 10, 10, 10, 10, 10000],
      "itemStyle": { "color": "#5b9bd5" },
      "label": {
        "show": true,
        "position": "top",
        "formatter": ["O(log n)", "O(log n)", "O(log n)", "O(log n)", "O(log n)", "O(n log n)"]
      }
    },
    {
      "name": "Binary Heap",
      "type": "bar",
      "data": [1000, 1, 10, 10, 1000, 1000],
      "itemStyle": { "color": "#f0ad4e" },
      "label": {
        "show": true,
        "position": "top",
        "formatter": ["O(n)", "O(1)", "O(log n)", "O(log n)", "O(n)", "O(n)"]
      }
    }
  ]
}

Итоговая таблица

Когда что выбирать

Типичные сценарии

Реализации в стандартных библиотеках

Краткий вывод

┌─────────────────────────────────────────────────────┐
│                                                     │
│  Heap  = специалист по Min/Max                      │
│          «Дай мне наибольший/наименьший — быстро»   │
│          O(1) для главной операции                  │
│                                                     │
│  BST   = универсальный упорядоченный словарь        │
│          «Найди, вставь, удали что угодно»          │
│          O(log n) для всего, полный порядок         │
│                                                     │
└─────────────────────────────────────────────────────┘