5.2. Представление древовидной таблицы
 

Вышеизложенное наталкивает на мысль о возможности представления двоичного дерева поиска в виде таблицы, то есть создания древовидной таблицы поиска. Напомним, что бинарное дерево поиска организовано таким образом, что для любого узла t_i, все ключи в левом поддереве меньше ключа t_i, а ключи в правом поддереве больше ключа t_i (все ключи уникальные). В дереве поиска можно на место каждого ключа, двигаясь начиная от корня и переходя на левое или правое поддерево каждого узла в зависимости от соотношения искомого ключа и ключа в узле дерева. Каждый узел, кроме ключа и данных, содержит два указателя: на левое и правое поддеревья.

Древовидная таблица поиска, как и обычная, представ собой массив. Каждый элемент массива — строка таблицы является записью, имеющей по крайней мере три поля: поле данных (ключа), указатель на левое поддерево и указатель на правое поддерево. Так как доступ к элементам массива осуществляется по индексам, то указатели являются не чем иным, как индексами элементов массива.

Таким образом, структура записи таблицы имеет вид: Левый указатель — Ключ + данные — Правый указатель

Поле «Ключ + данные» может иметь структуру любой сложности, состоящую из однородных или неоднородных элементов. Однако нас интересуют только ключи записей, по которым строится дерево и осуществляются все операции над записями: поиск, включение, удаление, выборка, обработка и обнов данных.