AOP_Tom3 (1021738), страница 56
Текст из файла (страница 56)
Будем называть бинарное дерево с этим свойством левосторонним деревом, поскольку оно, как правило, сильно "тянется" влево. Из этих определений ясно, что равенство 013Т(Р) = и подразу'мевает существование, по крайней мере, 2" пустых поддеревьев, расположенных ниже Р; в противном случае нашелся бы более короткий путь от Р до концевого узла Л.
Таким образом, если в левостароннем дереве имеется Х узлов, то путь, ведущий из корня вниз по направлению вправо, содержит не более чем ((К(М + 1)) узлов. Новый Связанное представление приоритетных очередей. Эффективный способ представления приоритетных очередей в ниде связанных бинарных деревьев предложил в 1971 году Кларк Э. Крэйн [см. С!аг)с А. Стане, Тесйп!са! Нерогг БТАйь СБ-72-259 (Сошрп(ег Яс!енсе 1)ераг(шеп(, Бсапгога' Пштегэйу, 1972))). Его метод требует наличия в каждой записи двух полей связи и короткого поля счетчика, но по сравнению с пирамидами он обладает следующими преимуществами.
!) Если с приоритетной очередью работают, как со стеком, та операции включения и исключения более эффективны (они отнимают фиксированное время, не зависящее от длины очереди). Н) Записи никогда не перемещаются, изменяются только указатели. ш) Можно слить две непересекающиеся приоритетные очереди, содержащие в общей сложности Х элементов, всего за О(!оК Х) шагов. Немного видоизмененный метод Крэйна проиллюстрирован на рис. 27, на котором показан особый тип структуры бинарного дерева.
В каждом узле содержатся паче КЕУ, поле 013Т и два поля связи — РЕЕТ и НХСНТ. Поле 013Т всегда устанавливается равным длине кратчайшего пути от этого узла да конечного узла (т. е. до пустого узла Л дерева). Если считать, что 013Т(Л) = 0 и КЕУ(Л) = — оа, то поля КЕУ и Р13Т в этом дереве удовлетворяют следующим соотношениям: Рнс. 27. Приоритетная очередь, представленная в виде левостороннего дерева. узел можно вставить в приоритетную очередь, пройдя по этому пути (см.
упр. 33). Следовательно, в худшем случае необходимо всего 0(1оЕХ) шагов. Наилучший случай достигается, когда дерево линейно (все связи Н1СНТ равны Л), а наихудший случай - — когда ано абсолютно сбалансировано. Чтобы удалить узел из корня, нужно просто слить два его поддерева. Операция слияния двух непересекающихся левосторонних деревьев, на которые ссылаются указатели Р и Ц, по своей идее проста: если КЕТ(Р) > КЕТА), то берем в качестве корня Р и сливаем () с правым поддеревом Р.
При этом изменится 01БТ(Р), а ЕЕРТ(Р) поменяется местами с Е1СНТ(Р) в случае необходимости, Нетрудно составить подробное описание этого процесса (см. упр. 33). Сравнение методов работы с приоритетными очередями. Если число узлов Х мэлб, то для поддержания приоритетной очереди лучше всего прибегнуть к одному из простых методов с использонанием линейных списков. Если же М велико, та, очевидно, гораздо более быстрым будет метод, использующий пирамиду нли левастороннее дерево, время работы которого составляет порядка 1оЕХ. В разделе 6.2.3 будет рассмотрен еще один способ представлении линейных списков— в виде сбалансированных дерееьее. Он приводит нас к третьему методу, пригодному для представления приоритетных очередей со временем работы порядка 1окФ. Поэтому уместно сравнить трн данных метода. Мы видели, что операции над левосторонними деревьями, в целом, выполняются несколько быстрее, чем операции над пирамидами, на пирамиды занимают меньше памяти.
Сбалансированные деревья занимают примерно столько же памяти, сколько левосторонние (быть может, чуть меньше); операции над ними выполняются медленнее, чем над пирамидами, и программирование сложнее, но структура сбалансированных деревьев в некоторых отношениях существенно более гибкая. Работая с пирамидами, не так просто предсказать, что произойдет с элементами, если у них равные ключи. Нельзя гарантировать, что элементы с равными ключами будут обрабатываться по принципу "последним пришел — первым вышел" или "первым пришел — первым вьппел", если только ключ не расширен и не содержит дополнительного поля "порядковый номер вставки'; тогда равных ключей просто иет.
С другой стороны, если применять сбалансированные деревья, можно легко оговорить жесткие условия, относящиеся к равным ключам. Можно также выполнять такие действия, как "вставить х непосредственно перед (или после) у". Сбалансированные деревья симметричны, так что в любой момент можно исключить либо наибольший, либо наименьший элемент, в то время как левостаронние деревья и пярамиды должны быть так или иначе ориентированы.
(См., тем не менее, упр. 31, в котором показано, как строить симмсшричиме пирамиды.) Сбъсансированные деревья можно использовать и для поиска, и для сортировки. Из сбалапсированнога дерева можно довольно быстро удалять последовательные блоки элементов. Но два сбалансированных дерева нельзя слить менее чем за Й(Дс) шагов, в то время как два левосторонних дерева можно слить всего за 0(!о8 Л) шагов.
Итак, сортировка с использованием пирамид наиболее экономна с точки зрения требований к объему памяти; левосторонние деревья хороши тем, что позволяют быстро слить две непересекающиегя приоритетные очереди; и, если нужно, по весьма умеренной цене можно получить гибкость, предоставляемую сбалансированными деревьями. Ф Со времени выхода в свет "пионерской" работы Ъбзльямса и Крэйна разработано много новых способов представления лриорлтетных очередей. Теперь в раси лорнжснил программистов имеется большое разнообразие опций, помимо простых списков, левостороннпх и сбалансированных деревьев. Некоторые из лих перечислены ниже: ° спрямленные деревья, которые обеспечивают обработку симметричной приоритетной очереди всего за 0(1о81о8М) шагов, если все ключи лежат в заданном диапазоне 0 ( К < М [Р.
чапс Ешс(е Воая, К. Каая, Е. Х1)!ягга, Магйс Яуясешя Т1сеогу 10 (1977), 99-127]; ° биномиальные очереди [Я. Чшйеш1п, САСМ 12 (1978), 309 — 315; М. В.. Вгокп, 81СОМР 7 (1978), 298-319]; ° пагоды [Л. Ггапчоп, С. "я'1еппоц Л. 1сп1!1еш1сс, ГОСЯ 19 (1978), 1 — 7]; ° парные пирамиды [М. Ь. Ггес1псасц К. 8едйекчс)с, О. О.
81ежог, К. Е. Тат]ап, А18ог115ппса 1 (1986), 111 — 129; Л. Т. 8гая1со, Л. 8. 'сс1гсег, САСМ 30 (1987), 234-249]; ° спиральные пирамиды [О, О. 8!еасог, К. Е. Тат)асц аСОМ~ 15 (1986), 52-59]; ° пиралсиды Фибоначчи [М. 1.. Ггес1псап, К. Е. Таг1ап, 7АСМ 34 (1987), 596-615] н более общие АГ-пирамиды [М. 1,. Ггейпап, О. Е. %1Пвгс1, Х Сошрпгег апс) Яуясеш ЯсЬ 48 (1994), 533-551]; я календарные очереди [К. Вгокп, САСМ 31 (1988), 1220 — 1227; С. А. Оач1яоп, САСМ 32 (1989), 1241 — 1243]; «ослабленные пирамиды [5.
В. Рг1зсо11, Н. Л». ОаЬоэч, В. БЬга1гшап, В. Е. Тат(ап, САС64 31 (1988), 1343-1354]; ° острбга [М. 3. Р1зсЬег, М. Б. Ратегзоп,,7АСМ 41 (1994), 3-30); ° "горячие" очереди [В. У'. СЬегбазэ1су, А. Ъ'. Оо14Ьег8, С. 81!тегэсе1п, БОРА 8 (1997), 83-92). Не все нз этих методов выдержалн испытание временем. Левосторонние деревья сегодня — уже анахронизм; они используются разве, что в тех приложениях, в которых необходимо жестко соблюдать дисциплину "последним пришел — - первым вышел". Детали реллиэацпп бпномнальиых очередей п пирамид Фпбоначчп можно найти в работе Р.
Е. КпиВЬ ТЛе Б1апГог»1 ОгарЛВазе (»Л»е»г Уог(г: АСМ Ргеэз, 1994), 475-489. 26'» 15, 10', 7, 7, 6', 3, 3, 3, 3., 3, 3, 2', 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1'. (12) Звездочками помечены особые под»уеревьл с корнями в особых узлах; в упр. 20 показано, что если Л» имеет двоичное представление Лг — (Ь 6 — » ° ° Ь\ 60)з и — [18 Л ), (13) то размеры особых поддеревьев равны (16~-»...6»6о)э, (16е-т ° ..Ь»Ьо)э,, (1Ь»Ьо)э (16е)з (1)э ° (14) Неособые поддеревья всегда абсолютно сбалансированы, так что их размеры имеют вид 2" — 1. В упр. 21 показано, что среди неособых поддеревьев существует ровно Лг — 11 1 Лг — 2 1 1 Лг — 4! 2 з ~ размером 1, ~ [ размером 3, ~ — [ размером 7, 4 [ ' [.
8 .! 2и-» ~ (2" — 1) размера. (15) Например, на рис. 28 изображено двенадцать неособых поддеревьев размером 1„ шесть поддеревьев размером 3, два — размером 7 н одно — размером 15. Пусть з» вЂ” размер поддерева с корнем 1, а Мм — мультимножество (з», зз,..., зл») всех этих размеров. Используя (14) и (15), легко вычислить Мл» прн любом заданном Л». В упр. 5.1.4-20 показано, что общее число способов построения пирамиды из целых чисел (1,2,..., Лг) равно Л"~э»ээ 'и=~(/П(з[эб Ми) (16) «Анализ пирамидальной сортировки. Алгоритм Н до сих пор не был пш»н»ютью проанализирован математическими методами, но некоторые его свойства можно вывести без особого труда. Поэтому данный раздел завершается довольно подробным анализом пирамид. На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
