24 (1106261)

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

Текст из файла

Курс «Алгоритмы и алгоритмические языки»1 семестр 2013/2014Лекция 24Самоперестраивающиеся деревья (splay trees)Двоичное дерево поиска, не содержащее дополнительныхслужебных полей в структуре данных(нет баланса, цвета и т.п.)Гарантируется не логарифмическая сложность в худшем случае,а амортизированная логарифмическая сложность:Любая последовательность из m словарных операций(поиска, вставки, удаления) над n элементами, начинаяс пустого дерева, имеет сложность O(m log n)Средняя сложность одной операции O(log n)Некоторые операции могут иметь сложность Θ(n)Не делается предположений о распределениивероятностей ключей дерева и словарных операций(т.е.

что некоторые операции выполнялись чаще других)Хорошее описание в:Harry R. Lewis, Larry Denenberg. Data Structures andTheir Algorithms. HarperCollins, 1991. Глава 7.3.http://www.amazon.com/Structures-Their-Algorithms-Harry2Lewis/dp/067339736XСамоперестраивающиеся деревья (splay trees)Идея: эвристика Move-to-FrontСписок: давайте при поиске элемента в спискеперемещать найденный элемент в начало спискаЕсли он потребуется снова в обозримом будущем,он найдется быстрееMove-to-Front для двоичного дерева поиска: oперация Splay(K, T)(подравнивание, перемешивание, расширение)После выполнения операции Splay дерево Tперестраивается (оставаясь деревом поиска) так, что:Если ключ K есть в дереве, то он становится корнемЕсли ключа K нет в дереве, то в корне оказываетсяего предшественник или последователь в симметричномпорядке обхода3Реализация словарных операций через splayПоиск (LookUp): выполним операцию Splay(K, T) и проверимзначение ключа в корне:если значение равно K, то ключ найден4Реализация словарных операций через splayВставка (Insert): выполним операцию Splay(K, T) и проверимзначение ключа в корне:если значение уже равно K, то обновим данные ключаесли значение другое, то вставим новый корень К ипоместим старый корень J слева или справа(в зависимости от значения J)5Реализация словарных операций через splayОперация Concat (T1, T2) – слияние деревьев поиска T1 и T2 таких,все ключи в дереве T1 меньше, чем все ключи в дереве T2,в одно дерево поискаСлияние (Concat): выполним операцию Splay(+∞, T1) со значениемключа, заведомо больше любого другого в T1После Splay(+∞, T1) у корня дерева T1 нет правого сынаПрисоединим дерево T2 как правый сын корня T16Реализация словарных операций через splayУдаление (Delete): выполним операцию Splay(K, T) и проверимзначение ключа в корне:если значение не равно K, то ключа в дереве нет иудалять нам нечегоиначе (ключ был найден) выполним операцию Concatнад левым и правым сыновьями корня, а корень удалим7Реализация операции splayШаг 1: ищем ключ K в дереве обычным способом, запоминаяпройденный путь по деревуМожет потребоваться память, линейная от количестваузлов дереваДля уменьшения количества памяти можновоспользоваться инверсией ссылок (link inversion)○перенаправление указателей на сынаназад на родителя вдоль пути по деревуплюс 1 бит на обозначение направленияШаг 2: получаем указатель P на узел дерева либо с ключом K,либо с его соседом в симметричном порядке обхода, на которомзакончился поиск (сосед имеет единственного сына)Шаг 3: возвращаемся назад вдоль запомненного пути,перемещая узел P к корню (узел P будет новым корнем)8Реализация операции splayШаг 3а): отец узла P – корень дерева (или у P нет деда)выполняем однократный поворот налево или направо9Реализация операции splayШаг 3б): узел P и отец узла P – оба левые или правые детивыполняем два однократных поворота направо (налево),сначала вокруг деда P, потом вокруг отца P10Реализация операции splayШаг 3в): отец узла P – правый сын, а P – левый сын (или наоборот)выполняем два однократных поворота в противоположныхнаправлениях (сначала вокруг отца P направо, потомвокруг деда P налево)11Пример операции splay над узлом DСлучай б): отец узла D (E) и сам узел D – оба левые сыновья12Пример операции splay над узлом DСлучай в): отец узла D (H) – правый сын, а сам узел D – левый сын13Пример операции splay над узлом DСлучай а): отец узла D (L) – корень дерева14Сложность операции splay15Пусть каждый узел дерева содержит некоторую сумму денег.Весом узла является количество ее потомков,включая сам узелРангом узла 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) хватает на все операции..

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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