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


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



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


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


}
}

Варианты балансировки левого и правого поддерева абсолютно симметричны. Структура фрагмента дерева и фрагмент алгоритма балансировки приводятся ниже для правого поддерева:



C &#62 B B &#62 C
pp-&#62balance == 2 p1-&#62balance == 1 p1-&#62balance == -1
--¬ --¬ --¬
pp --&#62¦5¦ pp ---&#62¦7¦ pp-----&#62¦B¦
L-- L-- L--
-----+--¬ ----+---¬ ----+-----¬
--¬ --¬ --¬ --¬ --¬ --¬
¦A¦ ¦7¦&#60-- p1 ¦5¦ ¦C¦ ¦5¦ ¦7¦
L-- L-- L-- L-- L-- L--
-----+----¬ ---+--¬ -----+---¬ ---+---¬
--¬ --¬ --¬ --¬ --¬ --¬--¬ --¬
p2--&#62¦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-&#62 right;
if (p1-&#62balance == 1) // Вариант 1


{
pp-&#62balance = 0;
pp-&#62right = p1-&#62left; // Правый (5) = B


p1-&#62left = pp; // Левый (7) = 5


pp = p1; // Вершина поддерева = 7


}
else // Вариант 2


{
p2 = p1-&#62left; //


p1-&#62left = p2-&#62right; // Левый (7) = E


p2-&#62right = p1; // Правый (B) = 7


pp-&#62right = p2-&#62left; // Правый (5) = D


p2-&#62left = pp; // Левый (B) = 5


// Баланс (5) = 0 или -1


// Баланс (7) = 0 или 1


pp-&#62balance = -(p2-&#62balance == 1);
p1-&#62balance = (p2-&#62balance == -1);
pp = p2; // Вершина поддерева = B


}
pp-&#62balance = 0;
return 0;




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