Слайды лекций - 2014 (лектор - Белеванцев А. А.) (1107979), страница 18

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

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

что некоторые операции выполнялись чаще других)Хорошее описание в:Harry R. Lewis, Larry Denenberg. Data Structures andTheir Algorithms. HarperCollins, 1991. Глава 7.3.http://www.amazon.com/Structures-Their-Algorithms-Harry13Lewis/dp/067339736XСамоперестраивающиеся деревья (splay trees)Идея: эвристика Move-to-FrontСписок: давайте при поиске элемента в спискеперемещать найденный элемент в начало спискаЕсли он потребуется снова в обозримом будущем,он найдется быстрееMove-to-Front для двоичного дерева поиска: oперация Splay(K, T)(подравнивание, перемешивание, расширение)После выполнения операции Splay дерево Tперестраивается (оставаясь деревом поиска) так, что:Если ключ K есть в дереве, то он становится корнемЕсли ключа K нет в дереве, то в корне оказываетсяего предшественник или последователь в симметричномпорядке обхода14Реализация словарных операций через splayПоиск (LookUp): выполним операцию Splay(K, T) и проверимзначение ключа в корне:если значение равно K, то ключ найден15Реализация словарных операций через splayВставка (Insert): выполним операцию Splay(K, T) и проверимзначение ключа в корне:если значение уже равно K, то обновим данные ключаесли значение другое, то вставим новый корень К ипоместим старый корень J слева или справа(в зависимости от значения J)16Реализация словарных операций через splayОперация Concat (T1, T2) – слияние деревьев поиска T1 и T2 таких,что все ключи в дереве T1 меньше, чем все ключи в дереве T2,в одно дерево поискаСлияние (Concat): выполним операцию Splay(+∞, T1) со значениемключа, заведомо больше любого другого в T1После Splay(+∞, T1) у корня дерева T1 нет правого сынаПрисоединим дерево T2 как правый сын корня T117Реализация словарных операций через splayУдаление (Delete): выполним операцию Splay(K, T) и проверимзначение ключа в корне:если значение не равно K, то ключа в дереве нет иудалять нам нечегоиначе (ключ был найден) выполним операцию Concatнад левым и правым сыновьями корня, а корень удалим18Реализация операции splayШаг 1: ищем ключ K в дереве обычным способом, запоминаяпройденный путь по деревуМожет потребоваться память, линейная от количестваузлов дереваДля уменьшения количества памяти можновоспользоваться инверсией ссылок (link inversion)○перенаправление указателей на сынаназад на родителя вдоль пути по деревуплюс 1 бит на обозначение направленияШаг 2: получаем указатель P на узел дерева либо с ключом K,либо с его соседом в симметричном порядке обхода, на которомзакончился поиск (сосед имеет единственного сына)Шаг 3: возвращаемся назад вдоль запомненного пути,перемещая узел P к корню (узел P будет новым корнем)19Реализация операции splayШаг 3а): отец узла P – корень дерева (или у P нет деда)выполняем однократный поворот налево или направо20Реализация операции splayШаг 3б): узел P и отец узла P – оба левые или правые детивыполняем два однократных поворота направо (налево),сначала вокруг деда P, потом вокруг отца P21Реализация операции splayШаг 3в): отец узла P – правый сын, а P – левый сын (или наоборот)выполняем два однократных поворота в противоположныхнаправлениях (сначала вокруг отца P направо, потомвокруг деда P налево)22Пример операции splay над узлом DСлучай б): отец узла D (E) и сам узел D – оба левые сыновья23Пример операции splay над узлом DСлучай в): отец узла D (H) – правый сын, а сам узел D – левый сын24Пример операции splay над узлом DСлучай а): отец узла D (L) – корень дерева25Сложность операции splay26Пусть каждый узел дерева содержит некоторую сумму денег.Весом узла является количество ее потомков,включая сам узелРангом узла r(N) называется логарифм ее весаДенежный инвариант: во время всех операций с деревомкаждый узел содержит r(N) рублейКаждая операция с деревом стоит фиксированную суммуза единицу времениЛемма.

Операция splay требует инвестирования не более чем в3lg n  + 1 рублей с сохранением денежного инварианта.Теорема. Любая последовательность из m словарных операцийна самоперестраивающемся дереве, которое было изначальнопусто и на каждом шаге содержало не более n узлов, занимаетне более O(m log n) времени.Каждая операция требует не более O(log n) инвестиций,при этом может использовать деньги узлаПо лемме инвестируется всего не более m(3lg n  + 1)рублей, сначала дерево содержит 0 рублей, в концесодержит ≥0 рублей – O(m log n) хватает на все операции.Сбалансированные деревья: обобщение через рангиHaeupler, Sen, Tarjan.

Rank-balanced trees. ACM Transactions onAlgorithms, 2014 (to appear).Обобщение разных видов сбалансированных деревьев черезпонятие ранга (rank) и ранговой разницы (rank difference)АВЛ, красно-черные деревья, 2-3 деревья, B-деревьяНовый вид деревьев: слабые АВЛ-деревья (weak AVL)Анализ слабых АВЛ-деревьев, анализ потенциалов27Сбалансированные деревья: понятие рангаРанг (rank) вершины r(x): неотрицательное целое числоРанг отсутствующей (null) вершины равен -1Ранг дерева: ранг корня дереваРанговая разница (rank difference): если у вершины x естьродитель p(x), то это число r(p(x)) – r(x).У корня дерева нет ранговой разницыi-сын: вершина с ранговой разницей, равной i.i,j-вершина: вершина, у которой левый сын – это i-сын,а правый сын – это j-сын.

Один или оба сына могутотсутствовать. i,j- и j,i-вершины не различаются.28Сбалансированные деревья: ранговый формализмКонкретный вид сбалансированного дерева определяетсярангом и ранговым правилом.Ранговое правило должно гарантировать:Высота дерева (h) превосходит его ранг не более чемв константное количество раз (плюс, возможно, O(1))Ранг вершины (k) превосходит логарифм ее размера (n)не более чем в константное количество раз(плюс, возможно, O(1))Размер вершины – число ее потомков, включая себя,т.е.

размер поддерева с корнем в этой вершинеТ.е. h = O (k), k = O (log n)  h = O (log n)Совершенное дерево:ранг дерева – его высота; все вершины – 1,1.29Сбалансированные деревья: ранговые правилаАВЛ-правило: каждая вершина – 1,1 или 1,2.Ранг: высота дерева.(или: все ранги положительны, каждая вершина имеет хотя бы одного 1-сына)Можно хранить один бит, указывающий наранговую разницу вершиныКрасно-черное правило: ранговая разница любой вершиныравна 0 или 1, при этом родитель 0-сына не может быть 0-сыном.0-сын – красная вершина, 1-сын – черная вершинаРанг: черная высотаКорень не имеет цвета (т.к. не имеет ранговой разницы!)Слабое АВЛ-правило: ранговая разница любой вершиныравна 1 или 2; все листья имеют ранг 0.Вдобавок к АВЛ-деревьям разрешаются 2,2-вершиныБит на узел для ранговой разницы или ее четностиБалансировка: не более двух поворотов и O(log n)изменений ранга для вставки/удаления, при этомамортизированно – лишь O(1) изменений.30Слабое АВЛ-дерево является красно-черным деревом.

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

Список файлов лекций