Сортирующее дерево

Сортирующее дерево (англ. sorting tree) — это структура данных в информатике, представляющая собой бинарное дерево, в котором каждый узел содержит значение, а все дочерние узлы слева содержат меньшие значения, а справа — большие или равные. Сортирующее дерево является разновидностью бинарного дерева поиска (BST) и используется для эффективной сортировки данных, а также для организации быстрого поиска, вставки и удаления элементов. Основное свойство такого дерева — поддержание упорядоченности элементов, что позволяет выполнять обход в порядке возрастания (in-order traversal) за линейное время.

История

Концепция сортирующего дерева восходит к ранним работам по бинарным деревьям поиска, которые были формализованы в 1960-х годах. Первые упоминания о бинарных деревьях для сортировки данных связывают с исследованиями в области алгоритмов и структур данных, проводимыми такими учёными, как Дональд Кнут (описал в своей книге «Искусство программирования», 1968) и Эдсгер Дейкстра. В 1970-х годах термин «сортирующее дерево» стал использоваться для обозначения деревьев, специально предназначенных для сортировки, в отличие от более общих бинарных деревьев поиска, которые могут быть несбалансированными. В 1980-х годах с развитием вычислительной техники сортирующие деревья нашли применение в базах данных и системах управления памятью, а в 1990-х годах были адаптированы для параллельных вычислений и распределённых систем. В России и СССР сортирующие деревья изучались в рамках курсов по алгоритмам и структурам данных, начиная с 1970-х годов, в частности в работах А. Н. Колмогорова и его учеников.

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

Сортирующее дерево обладает следующими ключевыми характеристиками:

• Бинарность: каждый узел имеет не более двух дочерних узлов (левый и правый).
• Упорядоченность: для любого узла все значения в левом поддереве меньше значения узла, а в правом поддереве — больше или равны (в зависимости от реализации).
• Рекурсивность: левое и правое поддеревья сами являются сортирующими деревьями.
• Динамичность: дерево может изменять свой размер при вставке или удалении элементов, в отличие от статических массивов.

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

Классификация

Сортирующие деревья можно классифицировать по нескольким признакам:

По способу балансировки

• Несбалансированные сортирующие деревья: стандартные бинарные деревья поиска, не гарантирующие логарифмической высоты. Пример — наивное сортирующее дерево, построенное без балансировки.
• Самобалансирующиеся сортирующие деревья: поддерживают высоту O(log n) за счёт ротаций или перестроения. К ним относятся:
• АВЛ-дерево (по именам Адельсона-Вельского и Ландиса, 1962) — поддерживает строгий баланс (разница высот поддеревьев не более 1).
• Красно-чёрное дерево (Р. Байер, 1972) — использует цветовую маркировку узлов для балансировки.
• Splay-дерево (Д. Слейтор и Р. Тарьян, 1985) — автоматически перестраивает дерево при каждом доступе.
• B-дерево (Р. Байер и Э. МакКрейт, 1972) — обобщение на случай, когда узел может иметь более двух дочерних элементов.

По типу хранимых данных

• Целочисленные сортирующие деревья: хранят числа, для которых определён порядок.
• Строковые сортирующие деревья: хранят строки, сравниваемые лексикографически.
• Объектные сортирующие деревья: хранят произвольные объекты с заданным компаратором.

По способу обхода

• In-order (симметричный): левое поддерево, узел, правое поддерево — выдаёт отсортированный список.
• Pre-order (прямой): узел, левое поддерево, правое поддерево.
• Post-order (обратный): левое поддерево, правое поддерево, узел.

Устройство и реализация

Сортирующее дерево строится на основе узлов, каждый из которых содержит:

• Ключ (значение) — данные, по которым производится сортировка.
• Ссылки на левого и правого потомка (или NULL, если потомка нет).
• Дополнительные поля (например, высота для АВЛ-дерева, цвет для красно-чёрного дерева).

Операции

Основные операции над сортирующим деревом:

1. Вставка:

• Начинается с корня.
• Если дерево пусто, новый узел становится корнем.
• Иначе сравнивается ключ нового узла с ключом текущего узла: если меньше, рекурсивно переходим в левое поддерево; если больше или равно — в правое.
• После вставки может потребоваться балансировка (для самобалансирующихся деревьев).

1. Поиск:

• Аналогично вставке, но без добавления узла.
• Возвращает узел с заданным ключом или NULL, если ключ не найден.

1. Удаление:

• Три случая: удаление листа (простое удаление), удаление узла с одним потомком (замена на потомка), удаление узла с двумя потомками (замена на минимальный узел правого поддерева или максимальный левого).
• После удаления выполняется балансировка.

1. Обход:

• In-order обход выдаёт элементы в порядке возрастания.
• Pre-order и post-order используются для других целей (например, копирования дерева).

Пример реализации на псевдокоде

``` class Node: key: int left: Node | None right: Node | None

function insert(root, key): if root is None: return new Node(key) if key < root.key: root.left = insert(root.left, key) else: root.right = insert(root.right, key) return root ```

Применение

Сортирующие деревья широко используются в различных областях информатики и программирования:

• Сортировка данных: обход in-order позволяет получить отсортированный список за O(n). Это используется в алгоритмах, таких как tree sort.
• Базы данных: индексы в реляционных СУБД (например, B-деревья в PostgreSQL, MySQL) основаны на сортирующих деревьях для ускорения поиска.
• Операционные системы: управление памятью (например, красно-чёрные деревья в Linux для планирования процессов).
• Компиляторы: синтаксические деревья (AST) часто используют сортирующие деревья для хранения символов.
• Игровые движки: пространственное разбиение (например, BSP-деревья) для сортировки объектов по глубине.
• Алгоритмы машинного обучения: деревья решений (CART, ID3) используют принципы сортирующих деревьев для разбиения данных.

Сравнение с другими структурами данных

Сортирующие деревья часто сравнивают с другими структурами для сортировки и поиска:

Интересные факты

• Первое самобалансирующееся сортирующее дерево — АВЛ-дерево — было разработано советскими учёными Георгием Адельсоном-Вельским и Евгением Ландисом в 1962 году. Это один из первых примеров самобалансирующихся структур данных в мире.
• Красно-чёрные деревья используются в стандартной библиотеке C++ (std::map) и в Java (TreeMap).
• В 2000-х годах были предложены «танцующие деревья» (dancing trees), которые оптимизируют вставку для потоковых данных.
• Сортирующие деревья могут быть реализованы на аппаратном уровне, например, в некоторых процессорах для кэширования данных.

Критика и ограничения

Несмотря на широкое применение, сортирующие деревья имеют недостатки:

• Чувствительность к порядку вставки: несбалансированные деревья могут вырождаться в линейный список, что ухудшает производительность до O(n).
• Потребление памяти: каждый узел требует хранения ссылок на потомков, что увеличивает накладные расходы по сравнению с массивами.
• Сложность реализации: самобалансирующиеся варианты (например, АВЛ-дерево) требуют сложных алгоритмов ротаций и пересчёта высот.
• Параллелизм: в многопоточных средах требуется синхронизация доступа к дереву, что может снижать производительность.

Источники

• Дональд Кнут. «Искусство программирования», том 3: Сортировка и поиск, 1968.
• Георгий Адельсон-Вельский, Евгений Ландис. «Один алгоритм организации информации», 1962.
• Томас Кормен и др. «Алгоритмы: построение и анализ», 3-е издание, 2009.
• Роберт Седжвик. «Алгоритмы на Java», 4-е издание, 2011.
• Статья «Binary search tree» в Википедии, 2023.