Индексное дерево
Двоичное дерево является наиболее удобной структурой для реализации двоичного поиска. Напомним основное свойство такого дерева: если вершина дерева содержит некоторое значение, то в левом поддереве содержатся значения, меньшие данного, а в правом - большие данного. Алгоритмы поиска и включения в такое дерево являются рекурсивными. Двоичное дерево может использоваться для хранения самих записей файла - в этом случае значением, по которому строится дерево, является значение ключевого поля. В то же время в виде дерева может быть построен индекс. В этом случае вершина дерева содержит ссылку на запись в файле записей фиксированной длины.
Прежде всего рассмотрим способы хранения дерева в файле. Первый способ аналогичен представлению дерева в памяти в виде структур со ссылками. В этом случае каждая вершина дерева в файле имеет аналог ссылки в памяти - ссылку в файле, которая может быть либо ее адресом, либо номе- ром записи, если записи имеют фиксированный размер. Размещение в виде связанных записей позволяет наиболее эффективно использовать как память программы, так и файловую память.
Второй способ основан на естественном хранении дерева в массиве в следующем виде: индексы вершин левого и правого поддерева для вершины с номером n имеют значения 2n и 2n+1 соотвественно. Однако если различные ветви дерева имеют разную длину, то такое представление неэффективно использует память. Кроме того, при выполнении сложных преобразований структуры дерева требуется выполнять копирование его вершин.
Основной проблемой, возникающей при включении вершин в дерево, является возможная различная длина его ветвей. Конкретный вид дерева при этом зависит от последовательности значений включаемых элементов. В крайнем случае дерево может выродиться в односвязный список. Поэтому для дерева требуется выполнять операции выравнивания ветвей, которые называются балансировкой. Соответственно дерево с длиной ветвей, отличающейся не более чем на 1, называется сбалансированным.
Условие сбалансированности является рекурсивным: если сбалансировано все дерево, то сбалансированы все его поддеревья.
Для контроля сбалансированности в каждой вершине дерева вводится переменная balance, которая содержит разницу длин правого и левого поддерева и в сбалансированном дереве принимает следующие значения:
- -1 - левое поддерево на 1 длиннее правого;
- 0 - длины поддеревьев совпадают;
- 1 - правое поддерево на 1 длиннее левого.
Это позволяет контролировать состояние сбалансированности дерева и принимать меры по его балансировке. В первом приближении требуется учитывать изменение длины дерева, происходящее при включении нового элемента. Для этого рекурсивная функция включения должна иметь результат 1 или 0 в зависимости от того, увеличилась ли длина поддерева.
В приведенном примере используется ссылка на указатель для передачи в функцию указателя на текущую вершину с возможностью его изменения:
//------------------------------------------------------bk510-01.cpp
struct tree
{
int value; // Значение элемента
tree *left,*right; // Ссылки на поддеревья
int balance; // Значение разницы длин
}; // поддеревьев
int insert( tree *&pp, int v) // Включение вершины со значением v
{
tree *pnew;
if (pp == NULL) // Включить на место пустой ссылки
{
pnew = new tree;
pnew->right = NULL; // Правое и левое поддерево
pnew->left = NULL; // пусты
pnew->balance = 0; // Вершина сбалансирована
pp = pnew; // Включить новую вершину
return 1; // Длина увеличилась
}
if (pp->value) > v) // Включить в левое поддерево
{
if (!insert(pp->left, v))
return 0 ; // Длина дерева не возросла
pp->balance --; // Иначе - баланс влево
switch(pp->balance)
{
case 0: return 0; // Длина уменьшилась
case -1: return 1; // Длина возросла
case -2: .... // Выполнить балансировку
} // левого поддерева
}
else // Включить в правое поддерево
{
if (!insert(pp->right, v))
return 0; // Длина дерева не возросла
pp->balance ++; // Иначе - баланс вправо
switch(pp->balance)
{
case 0: return 0; // Длина уменьшилась
case 1: return 1; // Длина возросла
case 2: .... // Выполнить балансировку
} // правого поддерева
}
}
Варианты балансировки левого и правого поддерева абсолютно симметричны. Структура фрагмента дерева и фрагмент алгоритма балансировки приводятся ниже для правого поддерева:
C > B B > C
pp->balance == 2 p1->balance == 1 p1->balance == -1
--¬ --¬ --¬
pp -->¦5¦ pp --->¦7¦ pp----->¦B¦
L-- L-- L--
-----+--¬ ----+---¬ ----+-----¬
--¬ --¬ --¬ --¬ --¬ --¬
¦A¦ ¦7¦<-- p1 ¦5¦ ¦C¦ ¦5¦ ¦7¦
L-- L-- L-- L-- L-- L--
-----+----¬ ---+--¬ -----+---¬ ---+---¬
--¬ --¬ --¬ --¬ --¬ --¬--¬ --¬
p2-->¦B¦ ¦C¦
¦A¦ ¦B¦ ¦A¦ ¦D¦¦E¦ ¦C¦
L-- L-- L-- L-- L-- L--L-- L--
D --+-- E
//------------------------------------------------------bk510-02.cpp
tree *p1,*p2;
p1 = pp-> right;
if (p1->balance == 1) // Вариант 1
{
pp->balance = 0;
pp->right = p1->left; // Правый (5) = B
p1->left = pp; // Левый (7) = 5
pp = p1; // Вершина поддерева = 7
}
else // Вариант 2
{
p2 = p1->left; //
p1->left = p2->right; // Левый (7) = E
p2->right = p1; // Правый (B) = 7
pp->right = p2->left; // Правый (5) = D
p2->left = pp; // Левый (B) = 5
// Баланс (5) = 0 или -1
// Баланс (7) = 0 или 1
pp->balance = -(p2->balance == 1);
p1->balance = (p2->balance == -1);
pp = p2; // Вершина поддерева = B
}
pp->balance = 0;
return 0;
