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


Индексное дерево - часть 2


Для контроля сбалансированности в каждой вершине дерева вводится переменная balance, которая содержит разницу длин правого и левого поддерева и в сбалансированном дереве принимает следующие значения:



- -1 - левое поддерево на 1 длиннее правого;



- 0 - длины поддеревьев совпадают;



- 1 - правое поддерево на 1 длиннее левого.

Это позволяет контролировать состояние сбалансированности дерева и принимать меры по его балансировке. В первом приближении требуется учитывать изменение длины дерева, происходящее при включении нового элемента. Для этого рекурсивная функция включения должна иметь результат 1 или 0 в зависимости от того, увеличилась ли длина поддерева.

В приведенном примере используется ссылка на указатель для передачи в функцию указателя на текущую вершину с возможностью его изменения:


//------------------------------------------------------bk510-01.cpp


struct tree
{
int value; // Значение элемента


tree *left,*right; // Ссылки на поддеревья


int balance; // Значение разницы длин


}; // поддеревьев


int insert( tree *&#38pp, int v) // Включение вершины со значением v


{
tree *pnew;
if (pp == NULL) // Включить на место пустой ссылки


{
pnew = new tree;
pnew-&#62right = NULL; // Правое и левое поддерево


pnew-&#62left = NULL; // пусты


pnew-&#62balance = 0; // Вершина сбалансирована


pp = pnew; // Включить новую вершину


return 1; // Длина увеличилась


}
if (pp-&#62value) &#62 v) // Включить в левое поддерево


{
if (!insert(pp-&#62left, v))
return 0 ; // Длина дерева не возросла


pp-&#62balance --; // Иначе - баланс влево


switch(pp-&#62balance)
{
case 0: return 0; // Длина уменьшилась


case -1: return 1; // Длина возросла


case -2: .... // Выполнить балансировку


} // левого поддерева


}
else // Включить в правое поддерево


{
if (!insert(pp-&#62right, v))
return 0; // Длина дерева не возросла


pp-&#62balance ++; // Иначе - баланс вправо


switch(pp-&#62balance)
{
case 0: return 0; // Длина уменьшилась


case 1: return 1; // Длина возросла




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



Книжный магазин