1
УДК 004.022
Особенности структуры и функционирования
двоичного дерева поиска с «барьером»
© Н.С. Гриценко, Ю.С. Белов
КФ МГТУ им. Н.Э. Баумана, Калуга, 248000, Россия
Рассмотрена структурная организация двоичного дерева поиска с «барьером».
Описаны особенности его построения и функционирования. Дано графическое
отображение схем хранения двоичного дерева. Показана реализация алгоритмов
поиска и построения двоичного дерева.
Ключевые слова:
типы и структуры данных, графы, деревья, двоичные деревья,
двоичные деревья поиска.
К основным операциям, выполняемым с различными структурами
данных, можно отнести поиск среди набора данных. Один из широко
используемых для этого методов — построение двоичного дерева по-
иска, которое ускоряет и упрощает задачу поиска данных в определен-
ном наборе информации, структурирует заданную информацию для
более эффективного ее дальнейшего использования, а при отсутствии
необходимой информации возвращает указатель на пустой элемент [1].
Однако существуют ситуации, когда это свойство дерева неуместно и
вместо пустого элемента необходимо получить установленное значе-
ние. В этом случае рационально использовать дерево поиска с «барье-
ром».
Известно, что в основе поиска с использованием двоичного дерева
лежит операция сравнения, не требующая больших затрат как памяти,
так и времени, поэтому предлагаемый алгоритм при большом числе
элементов позволяет ускорить поиск и повысить производительность
[2]. Данный метод особенно эффективен в случае, когда двоичное дере-
во сбалансировано, т. е. пути от вершины до всех его листьев примерно
одинаковой длины. В наихудшем случае (дерево не сбалансировано)
время поиска будет линейным, и теряется смысл использования дерева.
В наилучшем случае (дерево сбалансировано) время поиска будет про-
порционально log
n
, где
n
— число элементов дерева. Обосновывается
данное время тем, что длина пути от вершины до любого из листьев де-
рева не более чем log
n
[3].
Чаще всего при построении двоичного дерева поиска каждый его
узел представляет собой структуру, содержащую следующие поля:
указатель на левое поддерево, указатель на правое поддерево, ин-
формационное и поле-ключ, по которому будет проводиться опера-
ция сравнения. Кроме того, при построении двоичного дерева поиска
необходимо соблюдать следующие требования:
