Структуры данных: двоичное дерево поиска

В информатике двоичные деревья поиска (BST, binary search tree), иногда называемые упорядоченными или отсортированными двоичными деревьями, представляют собой особый тип контейнера: структуру данных, которая хранит "элементы" (такие как числа, имена и т. д.) в памяти. Они позволяют осуществлять быстрый поиск, добавление и удаление элементов и могут использоваться для реализации либо динамических наборов элементов, либо таблиц поиска, которые позволяют найти элемент по его ключу (например, найти номер телефона человека по имени).

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

Несколько вариантов бинарного дерева поиска были изучены в информатике; этот пост посвящен в основном базовому типу.

Определение

Двоичное дерево поиска - это корневое двоичное дерево, каждый из внутренних узлов которого хранит ключ (и, возможно, связанное с ним значение), и у каждого есть два выделенных поддерева, обычно обозначаемых левое (left) и правое (right). Дерево дополнительно удовлетворяет свойству двоичного поиска, которое гласит, что ключ в каждом узле должен быть больше или равен любому ключу, хранящемуся в левом поддереве, и меньше или равен любому ключу, хранящемуся в правом поддереве. Листья (конечные узлы) дерева не содержат ключа и не имеют структуры, чтобы отличать их друг от друга.

Часто информация, представляемая каждым узлом, является записью, а не отдельным элементом данных. Однако в целях упорядочения узлы сравниваются по их ключам, а не по какой-либо части связанных с ними записей. Основное преимущество бинарных деревьев поиска перед другими структурами данных состоит в том, что связанные алгоритмы сортировки и алгоритмы поиска, такие как обход по порядку, могут быть очень эффективными; они также легко реализуются в коде.

Деревья двоичного поиска - это фундаментальная структура данных, используемая для построения более абстрактных структур данных, таких как множества (set), мультимножества (multiset) и ассоциативные массивы.

• При вставке или поиске элемента в двоичном дереве поиска ключ каждого посещаемого узла должен сравниваться с ключом элемента, который нужно вставить или найти.
• Форма дерева двоичного поиска полностью зависит от порядка вставок и удалений и может стать вырожденной.
• После длинной перемешанной последовательности случайных вставок и удалений ожидаемая высота дерева приближается к квадратному корню из числа ключей, который растет намного быстрее, чем log n.
• Было проведено много исследований, чтобы предотвратить вырождение дерева, приводящее к наихудшему временному усложнению O(n).

Отношение порядка

Бинарный поиск требует отношения порядка, с помощью которого каждый элемент (item) можно сравнивать с любым другим элементом в смысле полного предварительного порядка. Часть элемента, которая принимает участие при сравнении, называется его ключом. То, будут ли дубликаты, то есть различные элементы с одним и тем же ключом, разрешаться в дереве или нет, зависит не от отношения порядка, а только от приложения.

В контексте деревьев бинарного поиска полный предварительный порядок реализован наиболее гибко с помощью процедуры трехстороннего сравнения.

---

Читайте также:

• Структуры данных: B-дерево (B-tree)
• Структуры данных: динамический массив
• Структуры данных: хэш-таблица