Н.С. Гриценко, Ю.С. Белов
4
ранее, а указатели на левое и правое поддерево ссылаются на пустые
элементы. Таким образом, листья такого дерева лишь формально явля-
ются листьями; фактически они ссылаются еще на один узел, который и
будет являться концом дерева, т. е. можно утверждать, что лист у дерева
один.
а
б
Рис. 2.
Схемы двоичного дерева поиска с «барьером»:
a
— теоретическая интерпретация;
б
— фактическое представление
На практике двоичное дерево поиска с «барьером» структурно
реализуется немного иначе. Его листья ссылаются не на один зара-
нее установленный элемент, а на множество таких элементов, т. е.
каждый лист дерева в свою очередь имеет по два листа-«барьера»
(рис. 2,
б
):
