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


           

в каждой вершине дерева вводится


Для контроля сбалансированности в каждой вершине дерева вводится переменная 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; // Длина возросла


Содержание  Назад  Вперед