Поиск: бинарный, деревья, сбалансированные структуры

Линейный и бинарный поиск, бинарное дерево поиска и его вырождение, балансировка AVL и красно-чёрные деревья, интерполяционный поиск, сравнение с хеш-таблицей.

Поиск — операция, которая в программе выполняется чаще всех остальных. Разница между линейным перебором и правильной структурой данных на миллионе записей — это разница между секундой и микросекундой.

Линейный и бинарный поиск

def linear_search(a, target):
    for i, x in enumerate(a):
        if x == target:
            return i
    return -1

def binary_search(a, target):
    """Массив обязан быть отсортирован."""
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2       # так не будет переполнения в C++
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# Поиск границ: первое вхождение
def lower_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target: lo = mid + 1
        else: hi = mid
    return lo

Число сравнений при бинарном поиске:  ⌈log₂(n+1)⌉

  n = 1 000        → 10 сравнений
  n = 1 000 000    → 20
  n = 1 000 000 000 → 30

Линейный поиск в среднем: n/2 сравнений

Для миллиона элементов: 20 против 500 000 —
разница в 25 тысяч раз.

Когда бинарный поиск не выгоден

Он требует отсортированного массива, а сортировка стоит O(n log n). Если поиск выполняется один раз, дешевле линейный перебор за O(n). Бинарный выигрывает при многократных поисках по одним данным: сортируем однажды, ищем тысячи раз.

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

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

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

def find(root, key):
    while root:
        if key == root.key: return root
        root = root.left if key < root.key else root.right
    return None

def inorder(root, out=None):
    """Обход по возрастанию — свойство дерева поиска."""
    out = [] if out is None else out
    if root:
        inorder(root.left, out)
        out.append(root.key)
        inorder(root.right, out)
    return out

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

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

# Случайный порядок вставки — дерево сбалансировано
import random
keys = list(range(1, 1024))
random.shuffle(keys)
root = None
for k in keys: root = insert(root, k)
print('случайный порядок, высота:', height(root))     # около 20

# Отсортированный порядок — дерево превращается в список
root2 = None
for k in range(1, 1024): root2 = insert(root2, k)
print('по возрастанию, высота:', height(root2))       # 1023

Вставка отсортированных данных — не экзотика, а типичный случай: идентификаторы из базы, даты, номера по порядку. Дерево вырождается в связный список, поиск деградирует до O(n), и вся выгода структуры исчезает. Именно поэтому и придумали балансировку.

Сбалансированные деревья

Балансировка AVL — четыре случая:

  Левое-левое   → одно правое вращение
  Правое-правое → одно левое вращение
  Левое-правое  → левое вращение поддерева, затем правое
  Правое-левое  → правое вращение поддерева, затем левое

Баланс-фактор узла = height(left) − height(right)
Допустимые значения: −1, 0, +1
При выходе за пределы выполняется вращение.

def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    update_height(y); update_height(x)
    return x                          # новый корень поддерева

def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    update_height(x); update_height(y)
    return y

Где что применяется

Интерполяционный поиск

Вместо середины оценивает вероятное положение элемента:

  pos = lo + (target − a[lo]) · (hi − lo) / (a[hi] − a[lo])

Сложность O(log log n) для равномерно распределённых данных
— быстрее бинарного поиска.

Но на неравномерных данных деградирует до O(n),
поэтому применяется редко и только там, где
распределение известно.

Что делают в курсовой по поиску

1. Реализовать линейный и бинарный поиск, дерево поиска и его сбалансированный вариант.
2. Замерить время на данных 10³, 10⁵, 10⁷ элементов.
3. Показать вырождение дерева при отсортированной вставке — с замером высоты.
4. Построить график: время поиска от размера данных, в логарифмическом масштабе.
5. Подсчитать среднее число сравнений и сравнить с теоретическим log₂n.
6. Сделать вывод, какая структура подходит для вашей задачи и почему.

График в логарифмическом масштабе особенно наглядно показывает разницу: линейный поиск даёт прямую, бинарный — почти горизонтальную линию. Такая иллюстрация в отчёте убедительнее любых рассуждений о сложности.