lab02_random — случайные данные и баланс¶

Тот же набор структур, что и в lab02.md (Node, LinkedList, Queue, TreeNode, BinaryTree), но:

Список и очередь заполняются случайными значениями через random.sample(range(1, 100), k) — это k различных случайных чисел из диапазона (без повторов, в отличие от randint).
BinaryTree получает дополнительный метод build_balanced.

import random

list_values = random.sample(range(1, 100), 7)   # 7 уникальных чисел 1..99

random.sample(population, k) — выбор без повторений ровно k элементов.
random.choice(seq) — один случайный элемент (используется для удаления случайного узла из списка).

`build_balanced` — сбалансированное дерево¶

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

Идея: отсортировать значения и вставлять «серединой вперёд» — сначала середину (она станет корнем), потом рекурсивно середины левой и правой половин.

    def build_balanced(self, values: list[int]) -> None:
        ordered = sorted(values)          # 1. сортируем

        def insert_middle(lo: int, hi: int) -> None:
            if lo > hi:                   # пустой диапазон — выходим
                return
            mid = (lo + hi) // 2          # 2. середина текущего диапазона
            self.add(ordered[mid])        # 3. вставляем её (через обычный add)
            insert_middle(lo, mid - 1)    # 4. рекурсивно левая половина
            insert_middle(mid + 1, hi)    # 5. рекурсивно правая половина

        insert_middle(0, len(ordered) - 1)

Почему это работает: середина отсортированного массива делит его на две равные части. Она становится корнем; меньшая половина уходит влево, большая — вправо, и так рекурсивно. Высота получается ≈ log₂(n) — минимально возможная.

Пример. Значения [20, 30, 40, 50, 60, 70, 80] (после сортировки), индексы 0..6:

mid = 3 → вставляем 50 (корень)
левая половина [0..2]: mid = 1 → 30, затем 20 и 40
правая половина [4..6]: mid = 5 → 70, затем 60 и 80

        50
       /  \
     30    70
    / \   /  \
  20  40 60  80

Та же форма получится при любом исходном порядке тех же значений — именно в этом смысл метода.

main в lab02_random печатает два дерева для сравнения:

# 1) вставка в случайном порядке — форма зависит от ввода
bt_raw = BinaryTree()
for v in tree_values:
    bt_raw.add(v)
bt_raw.print_tree()

# 2) то же множество значений, но сбалансированно — форма стабильна
bt_balanced = BinaryTree()
bt_balanced.build_balanced(tree_values)
bt_balanced.print_tree()

Где это в проде¶

build_balanced показывает, почему БД и стандартные библиотеки используют самобалансирующиеся деревья, а не наивный BST:

Самобалансирующиеся деревья. Построить идеальное дерево «серединой вперёд» можно только разово; при онлайн-вставках форма снова начинает зависеть от порядка. Поэтому в проде применяют деревья, которые держат высоту ≈ log n автоматически: AVL и красно-чёрные (std::map в C++, TreeMap в Java, планировщик задач CFS в ядре Linux), B-tree / B+-tree в индексах PostgreSQL и MySQL.
Почему это важно для эксплуатации. Главный урок лабы — O(log n) у дерева поиска держится, только пока оно сбалансировано. Данные, вставленные по монотонно растущему ключу (автоинкремент, timestamp), вырождали бы наивный BST в «список» с поиском за O(n); балансировка — это то, что не даёт индексу деградировать независимо от порядка вставки.

lab02_random — случайные данные и баланс¶

build_balanced — сбалансированное дерево¶

Где это в проде¶

`build_balanced` — сбалансированное дерево¶