Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


«адача поиска. ƒеревь€, сбалансированные по высоте. ќсновные типы




Ѕалансировки.

—балансированные деревь€ поиска (balanced search tree). ¬ерхнюю оценку в худшем дл€ времени поиска получаем O(log(n)), если удаетс€ поддерживать сбалансированную структуру дерева поиска Ц не менее двух сыновей (почти) у каждой вершины и примерно одинакова€ высота поддеревьев у каждого сына.

Ќа сегодн€шний день разработано несколько методов перестройки деревьев поиска, которые позвол€ют поддерживать сбалансированную структуру дерева поиска с приемлемыми расходами по времени, так чтобы общее врем€ в худшем дл€ операций поиска, вставки, удалени€ и min (ј“ƒ Ђћножествої, Ђ—ловарьї и Ђќчередь с приоритетомї) сохран€лось O(log(n)). Ѕалансировку структуры дерева можно проводить и по высоте, и по объему (весу) поддеревьев. ƒл€ бинарных деревьев известны методы балансировки Ц ј¬Ћ-деревь€, красно-черные деревь€ (RB-tree) и их вариации. Ѕ-деревь€ Ч это один из видов сбалансированных деревьев, обеспечивающих эффективное хранение информации на магнитных дисках и других внешних устройствах с пр€мым доступом. Ѕ-деревь€ €вл€ютс€ обобщением 2-3 деревьев, разница в том, что в Ѕ- дереве каждый внутренний узел может иметь много детей, на практике до тыс€чи, в зависимости от характеристик используемого диска. Ѕлагодар€ этому можно значительно уменьшить высоту дерева и понизить константу в оценке O (log n) времени поиска элемента. ¬ основном Ѕ-деревь€ служат дл€ реализации доступа к данным файла по ключу поиска. ƒл€ этого создаетс€ (и поддерживаетс€) индексный файл, который фактически €вл€етс€ реализацией ј“ƒ словарь. —пецифическа€ структура данных Ц Splay-дерево. Ёто бинарное дерево поиска, но при этом не поддерживаетс€ €вного баланса, оно может оказатьс€ разбалансированным в определенном (традиционном) смысле. ¬место этого после выполнени€ каждой операции, типовой дл€ бинарных поисковых деревьев, осуществл€етс€ перестройка (сохран€юща€ определ€ющие свойства поискового дерева) с целью Ђподт€нутьї вершину этой операции (дл€ операции удалени€ - еЄ родител€), поближе к корню, что ускорит еЄ нахождение в будущем. ƒл€ такого представлени€ вышеупом€нутые операции с множествами (и некоторый набор дополнительных операций) имеют врем€ работы O(log(n)), но амортизированное. ѕерестройка проводитс€ с помощь трех Splay-операций: І Zig: ≈сли родитель вершины x €вл€етс€ корнем:

І Zig-Zig: ≈сли родитель вершины x не €вл€етс€ конем, но x и его родитель либо оба левые либо оба правые сыновь€:

І Zig-Zag: ≈сли родитель вершины x не €вл€етс€ конем, но x Ц левый сын, а его родитель Ц правый сын:

ѕродолжение 23

¬озможности организовать балансировку расшир€ютс€, если допускать изменение количества сыновей вершины в фиксированном диапазоне [k,m].   таким методам балансировки относ€тс€ 2-3-деревь€, ¬ деревь€ и их вариации. —ильно ветв€щиес€ ¬-деревь€ представл€ют особый интерес при работе с данными, хран€щимис€ во внешней пам€ти. —уществует множество других операций над сбалансированными деревь€ми, которые поддерживают их сбалансированность. —балансированные деревь€ используютс€ и дл€ представлени€ последовательностей таким образом, что можно будет быстро вставл€ть элементы в последовательность, преодолева€ трудности, которые св€заны с последовательным расположением элементов (в массиве), и обеспечива€ при этом произвольный доступ к элементам последовательности, т. е. преодолева€ сложности св€занного размещени€ элементов. ѕри этом такие представлени€ позвол€ют эффективно реализовать операции сцепить (конкатенаци€) и расцепить дл€ последовательностей. »сследуютс€ и известны расширени€ выше отмеченных структур данных предназначенные дл€ применени€ в различных предметных област€х, естественно имеющих свою специфику интерпретации данных. Ќапример, расширение красно- черных деревьев дл€ работы с ключами вида интервал вещественных чисел, которое представл€ет пр€мой интерес в задачах вычислительной геометрии.

Ѕалансировка

1.ћалое левое вращение

ƒанное вращение используетс€ тогда, когда (высота b-поддерева - высота L) = 2 и высота — <= высота R. 2.Ѕольшое левое вращение

3.ћалое правое вращение

ƒанное вращение используетс€ тогда, когда (высота b-поддерева Ч высота R) = 2 и высота — <= высота L.

4.Ѕольшое правое вращение





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2016-11-18; ћы поможем в написании ваших работ!; просмотров: 720 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

—амообман может довести до саморазрушени€. © Ќеизвестно
==> читать все изречени€...

782 - | 634 -


© 2015-2023 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.011 с.