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


           

и правого поддерева абсолютно симметричны.



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;


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





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий