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