Балансування дерев

Після виконання ряду операцій звпорядкованим деревом, Вставки і видалення
вузлів, воно може стати незбалансованим. Якщо подібне відбувається, алгоритми-
ми обробки дерева стають менш ефективними. При сильному ступені раз-
балансування дерево фактично являє собою всього лише складну форму
пов’язаного списку, а у програми, що використовує дерево, може різко знизитися
продуктивність.
Високі, тонкідерева, Такі як дере-
во, вказане ліворуч, можуть мати глибину
до O (N). Додавання або розміщення еле-
та в такому розбалансованому дереві може
займати O (N) кроків. Навіть якщо нові еле-
менти розміщуються безладно, в середньому
вони дадуть дерево з глибиною N / 2, обробка
якого зажадає так само порядку O (N) опе-
рацій.
Припустимо, що ви будуєте впорядкований-
ведвійкове дерево, Що містить 1000 вузлів.
Дерева, побудовані <brв різному порядку “src =” http://codingrus.ru/images/delphi/474.JPG “>
Рис. 7.1. Дерева, побудовані в різному порядку
Якщодерево збалансовано, Висота дерева буде порядку Iog2 (1000), або при-
блізітельно 10. Додавання нового елемента до дерева буде займати 10 кроків.
Якщо дерево високе й тонке, його висота дорівнює 1000. У цьому випадку для вставки
нового елемента буде потрібно 1000 кроків.
Тепер припустимо, що ви хочете додати ще 1000 вузлів. Якщо дерево ос-
шається збалансованим, всі 1000 вузлів будуть розміщені на декількох рівнях-
нях дерева. При цьому для додавання нових елементів потрібно приблизитель-
але 10 * 1000 = 10 000 кроків. Якщодеревобулоне збалансованоі залишається таким
в процесі росту, то при вставці кожного нового елемента воно буде ставати
всі вище. Додавання елементів займе приблизно 1000 + 1001 + … + 2000 =
= 1500000 кроків.
Хоча невідомо, в якому порядку елементи будуть додаватися і віддалятися з
дерева, в будь-якому випадку можна використовувати методи, які підтримають його СБА-
лансірованним.

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*