23 (1108022)

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

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

Курс «Алгоритмы и алгоритмические языки»1 семестр 2015/2016Лекция 231Красно-черные деревьяКрасно-черное дерево – двоичное дерево поиска, каждаявершина которого окрашена либо в красный, либо в черный цветПоля – цвет, дети, родителиtypedef struct rbtree {int key;char color;struct rbtree *left, *right, *parent;} rbtree, *prbtree;Будем считать, что если left или right равны NULL, то это“указатели” на фиктивные листы, т.е. все вершины внутренние2Красно-черные деревьяСвойства красно-черных деревьев:1.2.3.4.Каждая вершина либо красная, либо черная.Каждый лист (фиктивный) – черный.Если вершина красная, то оба ее сына – черные.Все пути, идущие от корня к любому листу, содержат одинаковоеколичество черных вершин264117142116107123nilnilnilnil15nilnil19nilnilnil2320nil4730nilnil28nilnil38nilnilnil35nilnil39nilnil3Красно-черные деревьяОбозначим bh(x) – "черную" высоту поддерева с корнем х (самувершину в число не включаем), т.е.

количество черных вершин отх до листаЧерная высота дерева – черная высота его корняЛемма: Красно-черное дерево с n внутренними вершинами (безфиктивных листьев) имеет высоту не более 2log2(n+1).(1) Покажем вначале, что поддерево х содержит не меньше2bh(x) – 1 внутренних вершин(1a) Индукция. Для листьев bh = 0, т.е. 2bh(x) – 1 = 20– 1 = 0.(1б) Пусть теперь х – не лист и имеет черную высоту k.Тогда каждый сын х имеет черную высоту не меньше k – 1(красный сын имеет высоту k, черный – k – 1).(1в) По предположению индукции каждый сын имеет не меньше2k-1 – 1 вершин. Поэтому поддерево х имеет не меньше 2k-1 – 1 +2k-1 – 1 + 1 = 2k – 1.4Красно-черные деревьяЛемма: Красно-черное дерево с n внутренними вершинами (безфиктивных листьев) имеет высоту не более 2log2(n+1).(2) Теперь пусть высота дерева равна h.(2а) По свойству 3 черные вершины составляют не меньшеполовины всех вершин на пути от корня к листу.

Поэтомучерная высота дерева bh не меньше h/2.(2б) Тогда n ≥ 2h/2 – 1 и h ≤ 2log2(n + 1). Лемма доказана.Следовательно, поиск по красно-черному дереву имеетсложность O (log2n).5Красно-черные деревья: вставка вершиныСначала мы используем обычную процедуру занесения новойвершины в двоичное дерево поиска:красим новую вершину в красный цвет.Если дерево было пустым, то красим новый корень в черныйцветСвойство 4 при вставке изначально не нарушено, т.к. новаявершина краснаяЕсли родитель новой вершины черный (новая – красная), тосвойство 3 также не нарушеноИначе (родитель красный) свойство 3 нарушено6Красно-черные деревья: вставка вершиныСлучай 1: “дядя” (второй сын родителя родителя текущейвершины) тоже красный (как текущая вершина и родитель)Возможно выполнить перекраску:родителя и дядю (вершины A и D) – в черный цвет,деда – (вершина C) – в красный цветСвойство 4 не нарушено (черные высоты поддеревьевсовпадают)СперекраскаAαδγDADBβСεαδBβεγ7Красно-черные деревья: вставка вершиныСлучай 2: “дядя” (второй сын родителя родителя текущейвершины) черныйШаг 1: Необходимо выполнить левый поворот родителятекущей вершины (вершины A)ССЛевыйповоротδAαBβγAγδBαβ8Красно-черные деревья: вставка вершиныСлучай 2: “дядя” (второй сын родителя родителя текущейвершины) черныйШаг 2: Необходимо выполнить правый поворотвершины C, после чего …Шаг 3: … перекрасить вершины B и CВсе поддеревья имеют черные корни и одинаковуючерную высоту, поэтому свойства 3 и 4 верныПравыйповоротCδBγAαBAαCβγδβ9Самоперестраивающиеся деревья (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-Harry10Lewis/dp/067339736XСамоперестраивающиеся деревья (splay trees)Идея: эвристика Move-to-FrontСписок: давайте при поиске элемента в спискеперемещать найденный элемент в начало спискаЕсли он потребуется снова в обозримом будущем,он найдется быстрееMove-to-Front для двоичного дерева поиска: oперация Splay(K, T)(подравнивание, перемешивание, расширение)После выполнения операции Splay дерево Tперестраивается (оставаясь деревом поиска) так, что:Если ключ K есть в дереве, то он становится корнемЕсли ключа K нет в дереве, то в корне оказываетсяего предшественник или последователь в симметричномпорядке обхода11Реализация словарных операций через splayПоиск (LookUp): выполним операцию Splay(K, T) и проверимзначение ключа в корне:если значение равно K, то ключ найден12Реализация словарных операций через splayВставка (Insert): выполним операцию Splay(K, T) и проверимзначение ключа в корне:если значение уже равно K, то обновим данные ключаесли значение другое, то вставим новый корень К ипоместим старый корень J слева или справа(в зависимости от значения J)13Реализация словарных операций через splayОперация Concat (T1, T2) – слияние деревьев поиска T1 и T2 таких,что все ключи в дереве T1 меньше, чем все ключи в дереве T2,в одно дерево поискаСлияние (Concat): выполним операцию Splay(+∞, T1) со значениемключа, заведомо больше любого другого в T1После Splay(+∞, T1) у корня дерева T1 нет правого сынаПрисоединим дерево T2 как правый сын корня T114Реализация словарных операций через splayУдаление (Delete): выполним операцию Splay(K, T) и проверимзначение ключа в корне:если значение не равно K, то ключа в дереве нет иудалять нам нечегоиначе (ключ был найден) выполним операцию Concatнад левым и правым сыновьями корня, а корень удалим15Реализация операции splayШаг 1: ищем ключ K в дереве обычным способом, запоминаяпройденный путь по деревуМожет потребоваться память, линейная от количестваузлов дереваДля уменьшения количества памяти можновоспользоваться инверсией ссылок (link inversion)○перенаправление указателей на сынаназад на родителя вдоль пути по деревуплюс 1 бит на обозначение направленияШаг 2: получаем указатель P на узел дерева либо с ключом K,либо с его соседом в симметричном порядке обхода, на которомзакончился поиск (сосед имеет единственного сына)Шаг 3: возвращаемся назад вдоль запомненного пути,перемещая узел P к корню (узел P будет новым корнем)16Реализация операции splayШаг 3а): отец узла P – корень дерева (или у P нет деда)выполняем однократный поворот налево или направо17Реализация операции splayШаг 3б): узел P и отец узла P – оба левые или правые детивыполняем два однократных поворота направо (налево),сначала вокруг деда P, потом вокруг отца P18Реализация операции splayШаг 3в): отец узла P – правый сын, а P – левый сын (или наоборот)выполняем два однократных поворота в противоположныхнаправлениях (сначала вокруг отца P направо, потомвокруг деда P налево)19Пример операции splay над узлом DСлучай б): отец узла D (E) и сам узел D – оба левые сыновья20Пример операции splay над узлом DСлучай в): отец узла D (H) – правый сын, а сам узел D – левый сын21Пример операции splay над узлом DСлучай а): отец узла D (L) – корень дерева22Сложность операции splay23Пусть каждый узел дерева содержит некоторую сумму денег.Весом узла является количество ее потомков,включая сам узелРангом узла 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)Анализ слабых АВЛ-деревьев, анализ потенциалов24Сбалансированные деревья: понятие рангаРанг (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-вершины не различаются.25Сбалансированные деревья: ранговый формализмКонкретный вид сбалансированного дерева определяетсярангом и ранговым правилом.Ранговое правило должно гарантировать:Высота дерева (h) превосходит его ранг не более чемв константное количество раз (плюс, возможно, O(1))Ранг вершины (k) превосходит логарифм ее размера (n)не более чем в константное количество раз(плюс, возможно, O(1))Размер вершины – число ее потомков, включая себя,т.е. размер поддерева с корнем в этой вершинеТ.е. h = O (k), k = O (log n)  h = O (log n)Совершенное дерево:ранг дерева – его высота; все вершины – 1,1.26Сбалансированные деревья: ранговые правилаАВЛ-правило: каждая вершина – 1,1 или 1,2.Ранг: высота дерева.(или: все ранги положительны, каждая вершина имеет хотя бы одного 1-сына)Можно хранить один бит, указывающий наранговую разницу вершиныКрасно-черное правило: ранговая разница любой вершиныравна 0 или 1, при этом родитель 0-сына не может быть 0-сыном.0-сын – красная вершина, 1-сын – черная вершинаРанг: черная высотаКорень не имеет цвета (т.к.

не имеет ранговой разницы!)Слабое АВЛ-правило: ранговая разница любой вершиныравна 1 или 2; все листья имеют ранг 0.Вдобавок к АВЛ-деревьям разрешаются 2,2-вершиныБит на узел для ранговой разницы или ее четностиБалансировка: не более двух поворотов и O(log n)изменений ранга для вставки/удаления, при этомамортизированно – лишь O(1) изменений.27Слабое АВЛ-дерево является красно-черным деревом.

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

Тип файла PDF

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

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

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