Бинарные деревья поиска

Бинарное дерево представляет собой упорядоченную тройку (, , ),

где – корневая вершина,

и – левое и правое поддеревья соответственно.

Общее число вершин составляет .

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

Представление бинарного дерева:,

где

INFO – информационное поле,

LLINK – указатель на левое поддерево,

RLINK – указатель на правое поддерево.