Идеально сбалансированные деревья поиска: свойства, построение и алгоритмы

Поиск вершины в двоичном дереве поиска (ДДП) осуществляется по алгоритму, использующему ключ X. Начиная с корня (Root), алгоритм последовательно сравнивает X с данными вершины (p→Data). Если X больше значения в вершине, переход выполняется в правое поддерево (p→Right), если меньше — в левое поддерево (p→Left). Процесс завершается при обнаружении вершины с p→Data = X или достижении NIL (вершина отсутствует). Максимальное количество сравнений определяется высотой дерева h и составляет Cmax = 2h. Эффективность поиска напрямую зависит от сбалансированности дерева.

Идеально сбалансированное дерево (ИСД) — подвид ДДП, где для каждой вершины размеры левого и правого поддеревьев отличаются не более чем на 1 (см. Рисунок 30. Примеры ИСД и неИСД). Это обеспечивает минимально возможную высоту дерева для заданного числа вершин n. Свойство 1 утверждает, что высота ИСД вычисляется как hИСД(n) = ⌈log₂(n+1)⌉, что оптимально для минимизации операций поиска. Свойство 2 подчеркивает рекурсивную природу ИСД: все его поддеревья также идеально сбалансированы, что гарантирует предсказуемую производительность.

Построение ИСД из массива A = (a₁, a₂, …, aₙ) выполняется в два этапа. Этап 1: сортировка массива по возрастанию. Этап 2: рекурсивное конструирование дерева. Корнем выбирается средний элемент отсортированного массива. Элементы, меньшие среднего, формируют левое поддерево, большие — правое поддерево. Процесс повторяется для каждого поддерева до исчерпания элементов. Пример построения для n = 16 (элементы — шестнадцатеричные цифры) иллюстрирует Рисунок 31. Построение ИСДП. Исходный массив A: [B, 9, 2, 4, 1, 7, E, F, A, D, C, 3, 5, 8, 6] сортируется в Aупор: [1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F], после чего определяется корень, разделы подмассивов и рекурсивно строятся поддеревья.

Алгоритм построения ИСДП формализуется через функцию ИСДП(L, R), возвращающую указатель на дерево. Параметры L и R задают левую и правую границы подмассива. Базовый случай: при L > R возвращается NIL. Иначе вычисляется средний индекс M = (L + R) / 2, создается вершина с данными A[M]. Рекурсивные вызовы ИСДП(L, M-1) и ИСДП(M+1, R) строят левое и правое поддеревья. Такой подход гарантирует сбалансированность и минимальную высоту, обеспечивая асимптотику поиска O(log n). Ключевые преимущества ИСДП включают оптимизацию операций вставки, удаления и поиска, что критично для баз данных и алгоритмов обработки больших данных.

Функция ИСДП(L, R):
  ЕСЛИ L > R ВОЗВРАТ NIL
  M := (L + R) / 2
  Создать вершину p с p→Data = A[M]
  p→Left := ИСДП(L, M-1)
  p→Right := ИСДП(M+1, R)
  ВОЗВРАТ p

Использование ИСДП особенно эффективно в задачах, требующих частых запросов к статическим данным, где однократное построение дерева компенсируется скоростью последующих операций. Для динамических данных предпочтительны самобалансирующиеся деревья (AVL, красно-черные), поддерживающие оптимальную высоту при модификациях. Тем не менее, ИСДП остаются фундаментальной структурой для изучения принципов балансировки и оптимизации древовидных иерархий.