(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)
Quest Software. TOAD for Oracle Edition
Антивирус ESET NOD32 SMALL Business Pack renewal for 5 user. Электронный ключ.
ZBrush 4R6 Win Commercial Single License ESD
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Новости ITShop.ru - ПО, книги, документация, курсы обучения
Программирование на Microsoft Access
CASE-технологии
СУБД Oracle "с нуля"
Каждый день новые драйверы для вашего компьютера!
Windows и Office: новости и советы
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
Обсуждения в форумах
Слот Биг Бэнг (6)
Большой взрыв как правящая теория сотворения мира. Теперь вы можете поиграть слот Big Bang в...
 
Отличается ли ДрифтКазино от беттинга? (57)
Друзья, давно заметил, что на Дрифте уже несколько месяцев во всю рекламируется и предлагается...
 
Подскажите лучшее онлайн казино (8)
Вот нашёл интересную игровую площадку, и это онлайн казино Вавада. Может кто что подсказать по...
 
Помощь по MS Access (345)
Доброе время суток. Случайно оказался на этом сайте, искал статьи по OLAP. Вижу, что...
 
Требуется Краснодар: Java -разрабочик (2)
Обязанности: Разработка корпоративных backend-приложений для автоматизации розничных продаж...
 
 
 



    
rambler's top100 Rambler's Top100