Информатика и технология программирования


Индексное дерево


Двоичное дерево является наиболее удобной структурой для реализации двоичного поиска. Напомним основное свойство такого дерева: если вершина дерева содержит некоторое значение, то в левом поддереве содержатся значения, меньшие данного, а в правом - большие данного. Алгоритмы поиска и включения в такое дерево являются рекурсивными. Двоичное дерево может использоваться для хранения самих записей файла - в этом случае значением, по которому строится дерево, является значение ключевого поля. В то же время в виде дерева может быть построен индекс. В этом случае вершина дерева содержит ссылку на запись в файле записей фиксированной длины.

Прежде всего рассмотрим способы хранения дерева в файле. Первый способ аналогичен представлению дерева в памяти в виде структур со ссылками. В этом случае каждая вершина дерева в файле имеет аналог ссылки в памяти - ссылку в файле, которая может быть либо ее адресом, либо номе- ром записи, если записи имеют фиксированный размер. Размещение в виде связанных записей позволяет наиболее эффективно использовать как память программы, так и файловую память.

Второй способ основан на естественном хранении дерева в массиве в следующем виде: индексы вершин левого и правого поддерева для вершины с номером n имеют значения 2n и 2n+1 соотвественно. Однако если различные ветви дерева имеют разную длину, то такое представление неэффективно использует память. Кроме того, при выполнении сложных преобразований структуры дерева требуется выполнять копирование его вершин.

Основной проблемой, возникающей при включении вершин в дерево, является возможная различная длина его ветвей. Конкретный вид дерева при этом зависит от последовательности значений включаемых элементов. В крайнем случае дерево может выродиться в односвязный список. Поэтому для дерева требуется выполнять операции выравнивания ветвей, которые называются балансировкой. Соответственно дерево с длиной ветвей, отличающейся не более чем на 1, называется сбалансированным.

Условие сбалансированности является рекурсивным: если сбалансировано все дерево, то сбалансированы все его поддеревья.


Начало  Назад  Вперед