О.В. Сенюкова - Сбалансированные деревья поиска (1113408), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

Одинарный поворотОбозначим корень за y, а его сына – искомый узел – за x. Для сохранения денежного инварианта потребуется сумма  r( x)  r( y)  r ( x)  r ( y) .После поворота x и у меняются ролями – x становится отцом, а y –сыном. Поэтому r( x)  r ( y) и r( y)  r( x) . В остальных узлахзначения r не меняются. Следовательно,  r( y)  r ( x)  r( x)  r ( x).Для выполнения, собственно, вращения потребуется 1 операция, и,следовательно, 1 рубль. Поэтому общее количество рублей N, необходимое для выполнения поворота и сохранения денежного инварианта, удовлетворяет неравенству:N  r( x)  r ( x)  1  3(r( x)  r ( x))  1.2.

Два одинарных поворота60(14)Обозначим искомый узел за x, его отца за y, а деда за z. Для сохранения денежного инварианта потребуется сумма  r( x)  r( y)  r( z)  r ( x)  r ( y)  r ( z) .После выполнения двух одинарных поворотов узел x становится«старшим» в этой комбинации, его отец y становится его сыном, аего дед z – его внуком. Поэтому r( x)  r ( z ) , r( y)  r( x) иr ( y)  r ( x) . В остальных узлах значения r не меняются. Следовательно, получим:  r( y)  r( z)  r ( x)  r ( y)  r( x)  r( z)  2r ( x) .Непосредственно два поворота составляют 2 операции, следовательно, требуют 2 рубля. Поэтому, для выполнения вращения исохранения денежного инварианта потребуется суммаN  r( x)  r( z)  2r ( x)  2 .Докажем, чтоr( x)  r( z)  2r ( x)  2  3(r( x)  r ( x)) .(15)Перепишем неравенство (15) в видеr ( z)  r ( x)  2r ( x)  2 .По определению рангаr( z)  r ( x)  2r( x)  log 2 | T ( z) |  log 2 | T ( x) | 2 log 2 | T ( x) | ,(16)где T(x) (T(z)) – дерево с корнем в узле x (z) до поворота, а T (x) (T (z ) ) – дерево с корнем в узле x (z) после поворота.Преобразуем правую часть (16):61log 2 | T ( z ) |  log 2 | T ( x) | 2 log 2 | T ( x) | (log 2 | T ( z ) |  log 2 | T ( x) |)  (log 2 | T ( x) |  log 2 | T ( x) |)  log 2| T ( z ) || T ( x) | log 2.| T ( x) || T ( x) |Зная, как будет перестраиваться дерево при повороте, можно заметить, что | T ( x) || T ( z ) |  | T ( x) | .Следовательно,| T ( z ) | | T ( x) | | T ( z ) |  | T ( x) | 1.| T ( x) | | T ( x) || T ( x) |Выпуклость функции логарифма предполагает, чтоlog 2 x  log 2 y  log 2 xy для x, y  0, x  y  1принимает максимальное значение –2 при1x y .2Поэтомуlog 2| T ( z ) || T ( x) | log 2 2 ,| T ( x) || T ( x) |следовательно,log 2 | T ( z) |  log 2 | T ( x) | 2 log 2 | T ( x) | 2 .Таким образом, мы получили, что для выполнения двух одинарныхповоротов и сохранения денежного инварианта требуется суммаN  3(r( x)  r ( x)) .(17)Двойной поворотПосле выполнения двойного поворота узел x становится «старшим», а его отец y и дед z становятся его сыновьями.

Так же, как ив предыдущем случае, имеют место соотношения r( x)  r ( z )62и r (y) ≥ r(x). Следовательно, для сохранения денежного инварианта потребутся сумма  r( x)  r( y)  r( z)  r( x)  r( y)  r( z)  r( y)  r( z)  2r( x).Для выполнения двойного поворота и сохранения денежного инварианта потребуется сумма N    2 , поэтомуN  r( y )  r( z )  2r( x)  2.Докажем, чтоr ( y)  r ( z)  2r ( x)  2  2(r ( x)  r ( x)) .(18)Перепишем неравенство (18) в видеr( y )  r( z)  2r( x)  2.Это неравенство доказывается аналогично предыдущему случаю,только, учитывая, что y и z стали сыновьями x, используем неравенство| T ( x) || T ( y) |  | T ( z) | .Получаем, что для выполнения двойного поворота и сохраненияденежного инварианта требуется суммаN  2(r( x)  r( x))  3(r( x)  r( x)).(19)Учитывая неравенства (14), (17) и (19), получаем, что для выполнения любого из трех типов поворотов и сохранения денежногоинварианта требуется не более3(r( x)  r ( x))  1 рублей.Лемма доказана.Теорема 4: Любая последовательность из m словарных операцийна самоперестраивающемся дереве, которое было изначально пусто и на каждом шаге содержало не более n узлов, занимает не более O(m log n) времени.63Доказательство:Из Леммы 2 следует, что операция splay(T, x) требует инвестирования не более 3 log 2 n  1 рублей.

Вспоминая, что каждая из словарных операций требует O(1) операций splay и O(1) дополнительного времени, получаем, что для выполнения последовательностииз m операций дополнительно требуется не более O(m( 3 log 2 n  1 ))инвестиций (при удалении операция splay производится два раза)и при этом можно использовать деньги узла. Сначала дерево содержит 0 рублей, в конце ≥ 0 рублей. Следовательно, O(m log n)рублей хватает на все операции. Теорема доказана.5.5 Задачи1. Дано самоперестраивающееся дерево, такое, что путь от корняк узлу с ключом 90 проходит через следующие узлы в порядке: 10,20, 30, 40, 50, 60, 70, 80, 90.

Нарисовать результат операции splayнад узлом 90.2. Дано самоперестраивающееся дерево, такое, что путь от корняк узлу с ключом 90 проходит через следующие узлы в порядке: 50,130, 60, 120, 70, 110, 80, 100, 90. Нарисовать результат операцииsplay над узлом 90.3. Пусть до выполнения операции splay все узлы дерева из задачи 1 на пути к узлу 90 имеют ранг k. Показать, что после выполнения операции splay над узлом 90 ранги этих узлов не увеличатся, аранги как минимум трех из них уменьшатся.4.

Пусть до выполнения операции splay все узлы дерева из задачи 2 на пути к узлу 90 имеют ранг k. Показать, что после выполнения операции splay над узлом 90 ранги этих узлов не увеличатся, аранги как минимум четырех из них уменьшатся.646. Сравнение АВЛ-деревьев, КЧ-деревьеви самоперестраивающихся деревьевВ общем случае сравнение трех рассмотренных типов деревьевпровести затруднительно, поскольку для разных задач и разныхнаборов данных лучший тип дерева может быть разным.

Сравнивать деревья можно по разным критериям: по сложности реализации, в теории, на практике.По сложности реализации самые простые – АВЛ-дерево, самыесложные – КЧ-деревья, поскольку приходится рассматривать много нетривиальных случаев при вставке и удалении узла.В теории оценки сверху для всех трех типов деревьев примерноодинаковые. Восстановление свойств как АВЛ-дерева, так и КЧдерева после вставки требует не более двух поворотов. Но послеудаления узла из КЧ-дерева потребуется не более трех поворотов,а в АВЛ-дереве после удаления узла может потребоваться количество поворотов до высоты дерева (от листа до корня). Поэтомуоперация удаления в КЧ-дереве эффективнее, в связи с чем онибольше распространены.Самоперестраивающиеся деревья существенно отличаются отАВЛ- и КЧ-деревьев потому как не накладываются никакие ограничения на структуру дерева.

Операция поиска в дереве модифицирует само дерево, поэтому в случае обращения к разным узламсамоперестраивающееся дерево может работать медленнее. К томуже, в процессе работы дерево может оказаться полностью разбалансированным. Но доказано, что если вероятности обращения кузлам фиксированы, то самоперестраивающееся дерево будет работать асимптотически не медленнее двух других рассмотренныхвидов деревьев [6]. Отсутствие дополнительных полей дает преимущество по памяти.Различные виды сбалансированных деревьев поиска используются, в частности, в системном программном обеспечении, например,в ядрах операционных систем.

В статье [9] приведены результаты65тестов, имитирующих некоторую реальную нагрузку на деревьяпоиска. Учитывая, что таблицы виртуальных адресов в Linux частоделаются на двоичных деревьях поиска, авторы инструментировали несколько приложений, чтобы получить последовательность ихобращений к подсистемам виртуальной памяти, а затем использовали эти последовательности для эмуляции нагрузки на двоичныедеревья в ядре операционной системы.

Так, например, показано,что если при использовании браузером Mozilla виртуальной памяти менеджер виртуальной памяти будет использовать самоперестраивающиеся деревья, то преимущество этого вида деревьев повремени работы над АВЛ- и КЧ-деревьями будет минимум в 2, амаксимум в 3.4 раза.В статье также показано, в каком случае какой вид деревьев лучшевсего использовать. Если входные данные полностью рандомизированы, то наилучшим вариантом оказываются деревья поискаобщего вида – несбалансированные.

Если входные данные в основном рандомизированные, но периодически встречаются упорядоченные наборы, то стоит выбрать КЧ-деревья. Если при вставкепреобладают упорядоченные данные, то АВЛ-деревья оказываются лучше в случае, когда дальнейший доступ к элементам рандомизирован, а самоперестраивающиеся деревья – когда дальнейшиедоступ последователен или кластеризован.667. Литература1.

А.А. Белеванцев. Лекции по курсу «Алгоритмы и алгоритмические языки». 2013. http://algcourse.cs.msu.su/?page_id=302. Вирт Н. Алгоритмы и структуры данных М.: Мир, 1989. Глава4.5 (С. 272–286).3. Г. М. Адельсон-Вельский, Е. М. Ландис.

Один алгоритм организации информации // Доклады АН СССР. 1962. Т. 146, № 2.C. 263–266.4. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ = Introduction to algorithms. — 2-е изд. — М.:Издательский дом «Вильямс», 2011. — С. 336–364.5. Д. Кнут. Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. FundamentalAlgorithms. — 3-е изд. — М.: «Вильямс», 2006.

Характеристики

Список файлов книги