(495) 925-0049, ITShop интернет-магазин 229-0436, Учебный Центр 925-0049
  Главная страница Карта сайта Контакты
Поиск
Вход
Регистрация
Рассылки сайта
 
 
 
 
 

Балансировка деревьев

Источник: codingrus
Kest

После выполнения ряда операций с упорядоченным деревом, вставки и удаления
узлов, оно может стать несбалансированным. Если подобное происходит, алгорит-
мы обработки дерева становятся менее эффективными. При сильной степени раз-
балансировки дерево фактически представляет собой всего лишь сложную форму
связанного списка, а у программы, использующей дерево, может резко снизиться
производительность.
Высокие, тонкие деревья, такие как дере-
во, изображенное слева, могут иметь глубину
до O(N). Добавление или размещение элемен-
та в таком разбалансированном дереве может
занимать O(N) шагов. Даже если новые эле-
менты размещаются беспорядочно, в среднем
они дадут дерево с глубиной N/2, обработка
которого потребует так же порядка O(N) опе-
раций.
Предположим, что вы строите упорядочен-
ное двоичное дерево, содержащее 1000 узлов.
Деревья, построенные<br />
в различном порядке
Рис. 7.1. Деревья, построенные в различном порядке
Если дерево сбалансировано, высота дерева будет порядка Iog2(1000), или при-
близительно 10. Добавление нового элемента к дереву будет занимать 10 шагов.
Если дерево высокое и тонкое, его высота равна 1000. В этом случае для вставки
нового элемента потребуется 1000 шагов.
Теперь предположим, что вы хотите добавить еще 1000 узлов. Если дерево ос-
тается сбалансированным, все 1000 узлов будут размещены на нескольких уров-
нях дерева. При этом для добавления новых элементов потребуется приблизитель-
но 10 * 1000 = 10 000 шагов. Если дерево было не сбалансировано и остается таким
в процессе роста, то при вставке каждого нового элемента оно будет становиться
все выше. Добавление элементов займет приблизительно 1000 + 1001 + ... + 2000 =
= 1,5 млн шагов.
Хотя неизвестно, в каком порядке элементы будут добавляться и удаляться из
дерева, в любом случае можно использовать методы, которые поддержат его сба-
лансированным.

Ссылки по теме


 Распечатать »
 Правила публикации »
  Обсудить материал в конференции Embarcadero »
Написать редактору 
 Рекомендовать » Дата публикации: 27.07.2012 
 

Магазин программного обеспечения   WWW.ITSHOP.RU
Delphi Professional Named User
Enterprise Connectors (1 Year term)
VideoStudio X9 ULTIMATE. Электронный ключ.
IBM RATIONAL Rose Enterprise Floating User License + Sw Subscription & Support 12 Months
DevExpress / Universal Subscription
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Новости ITShop.ru - ПО, книги, документация, курсы обучения
Программирование на Microsoft Access
CASE-технологии
СУБД Oracle "с нуля"
Компьютерная библиотека: книги, статьи, полезные ссылки
Adobe Photoshop: алхимия дизайна
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
Обсуждения в форумах
Ставки на спорт через зеркало БК Пинакл (1)
Актуальное зеркало букмекерской конторы Пинакл https://superbet.guru/pinacle-mirror/ всегда...
 
Ищу программиста для написания программы (57)
Ищу программиста ,владеющего Вижуал Бэйсик и программированием в Экселе, для написания...
 
Разработка программ базы данных (48)
Написание прикладных компьютерных программ (базы данных) на заказ. Разработка корпоративных...
 
Пишу программы на заказ для студентов (241)
Пишу для студентов на с, с++, паскаль в средах ms visual studio, qt, builder, borland c, delphi....
 
Программы Delphi на заказ (240)
Пишу программы в среде Delphi на заказ http://bddelphi.ucoz.ru/
 
 
 



    
rambler's top100 Rambler's Top100