Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 25
Текст из файла (страница 25)
Р. Пратт (Ч. К, Ргагс) обнаружили, что эти сравнения не требуют одного н того же ключа и может оказаться предпочтительным бинарное дерево, внутренние узлы которого определяют либо проверку равенства, либо проверку "меньше, чем", но не обе. Такая ситуация может оказаться интересной альтернативой поставленной задаче. 34.
[11М21] Покажите, что асимптотическое значение полиномиального козффицнента по отдельности, а Н(ХУ) = Н(г~„..., г „) —. энтропия их совместного распределения. Докажите, что Н(Х) < Н(ХУ) < Н(Х)+Н(У). (Ука,заике. Если у -- вогнутая функция, то Еу(Х) < У(Е Х) ) 37. [НМЯО] (П. Дж. Байер (Р. Л. Вауег), 1975.) Предположим, что (Рн...,Р„) предсщвляет собой случайное распределение вероятиостей, а именно — случайную точку в (п — 1)-мерном гимплексе, определенную величинами Рь > О, 1 < 5 < и, где Р~ + -. + Р„= 1 (или, что то же самое, (Рн.,., Р,) представляют собой множество случайных щюмелсупгкое, о которых говорилось в упр. 3.3.2-26).
Чему равно ожидаемое значение энтропии Н(Рп, ..,Р„)? 38. [МВО] Поясните, почему теорема М справедлива в общем случае, хотя мы доказали еетолькодля случая ео < е~ < ез < . < е . ь 39. [Мйб] Пусть оп,..., щ представляют собой кеотрицатель~ые веса (он+ +ж = 1). Докажите, что взвешенная длина пути дерева Хаффмвиа, построенного в разделе 2.3.4.5, меньше, чем Н(ил,..., ш„) + 1. ( Указание.
Обратитесь к доказательству теоремы М.) 49, [М96] Завершите доказательство леммы Е. 41. [611 На рис. 18 показано строение весьма запутаииого бинарного дерева, Перечислите его листья в порядке слева направо. 42. [36] Об ьясиите, почему в подпрограмме С сохраиаяется справедливость условия (31). 43. [ЯО] Поясните, как эффективно реализовать фазу 2 алгоритма Гарсия-Воча. ь 44, [35] Поясните, как эффективно реализовать фазу 3 алгоритма Гарсия-Воча: постройте бинарное дерево с уровнями 1е, й,, 1„листьев в симметричном порядке.
ь 45. [ОО] Поясните, как реализовать подпрограмму С так, чтобы общее время работы алгоритма Гарсия-Воча ие превышало 0(п 1оВ и). 46. [МУО] (Ч. К. Воиг (С. К. Юопб) и Ши-Куо Чанг (БпрКпоСЬап8).) Рассмотрим схему, в которой бинарное дерево поиска строится согласно алгоритму Т, ио, когда количество узлов достигает зиачеиий вида 2 — 1, дерево реорганизуется в идеально сбалансированное дерево с 2» узлами иа уровне 5, 0 < 5 < и. Докажите, что общее количество сравнений, выполненных при построении такого дерева, в средием равно Н 16Ю + О(51). (Нетрудно показать, что время, необходимое для реоргаиизации дерева, составляет 0(Н).) 47. [М40] Обобщите теоремы В и М для 1-ариых деревьев.
По возможности рассмотрите случай, когда цены ветвей неодинаковы, как в упр. 33. 48. [М4 7] Проведите точный анализ устойчивого состояиия бинарного дерева поиска при случайных вставках и удалениях. 49. [НМ46] Проанализируйте средиэио высоту бинарного дерева поиска. 5.2.3. Сбалансированные деревья Алгоритм вставки в дерево, который мы только что изучили, даст хорошие результаты при использовании случайных входных данных, ио все же существует неприятная возможность того, что при этом будет построено вырожденное дерево. Можно было бы разработать алгоритм, поддерживающий дерево в сяпимвльном состоянии все время, однако это, к сожалению, очень сложная задача.
Другая идея заключается в том, чтобы хранить общую длину пути и полностью реорганизовывать дерево, когда оиа превьппаст, например, 5А( 18 Н. Тем не менее при таком подходе потребовалось бы порядка,/Й72 реорганизаций дерева в процессе его построения.
Очень красивое решение проблемы поддержания дерева поиска в хорошем состоянии было открыто в 1962 году двумя советскими математиками — Г. М. АдельсонВельским и Е. М. Ландисом [ДАН СССР 146 (1962), 263-266: английский перевод Бог!ег МагЬ, 3, 1259-1263). Их метод требует всего лишь двух дополнительных битов на узел и никогда не использует более О(!ойдо) операций для поиска по дереву нли вставки элемента. Предложенный подход также дает общую технологию представления линейных списков длиной Х таким образом, что любая из следующих операций может быть выполнена за время О(!ой Х): !) поиск элемента по заданному ключу; й) поиск к-го элемента по заданному Й; й!) вставка элемента в определенное место; 1у) удаление определенного элемента.
При последовательном расположении элементов линейных списков операции (1) и (й) выполняются очень эффективно, в то время как операции (ш) и (!х) требуют порядка Х шагов. С другой стороны, при использовании связанных элементов эффективво будут выполняться операции (ш) и (1т), а операции (!) и (и) потребуют порядка Х шагов. Представление линейных списков в виде дерева позволяет выполнить есе чегпыре операции за О(1ойХ) шагов. При этом можно более или менее эффективно выполнять и другие операции, например сцепление списка из М элементов со списком из Ф элементов за О[)ой(М + Ю)) шагов. Метод, предоставляющий все эти преимущества, будем называть сбалансированными деревьями (многие авторы ишкиьзуют термин А гз -деревья — по первым буквам фамилий авторов).
Предыдущий абзац служит рекламой сбалансированных деревьев — эдакой панацеи от всех бед. Имея в руках такой мощный метод, ьюжно смело выбросить на помойку все прочие методы! Однако яе торопитесь - — сначала сбалансируйте свое отношение к сбалансированным деревьям. Ведь, например, если все четыре операции не нужны, нас может удовлетворить менее универсальный, но более быстрый (для данного конкретного случая) и проще программируемый метод.
Кроме того, сбалансированные деревья хороши при наличии большого количества элементов. Судите сами: если есть эффективный метод, который требует 64 18 Х единиц времени, и неэффективный, которому необходимо 2Х единиц, то прн Х < 266 следует использовать неэффективный метод, который прн этом становится более эффективным... С другой стороны, при очень больших Х хранение данных во внушренней памяти становится невозможным, а при использовании внешних файлов с прямым доступом более эффективны другие методы, о которых речь пойдет в разделе 6.2.4. Впрочем, оперативная память становится все дешевле, а значит, сбалансированные деревья становятся все более и более важным орудием в Руках программиста, Высота дерева определяется как его максимальный уровень, длина самого длинного пути от корня к внешнему узлу.
Бинарное дерево называется сбалансированным, еглн высота левого поддерева любого узла отличается не более чем на х1 от высоты правого поддерева. На рис. 20 показано сбалансированное дерево высотой 5 с 17 внутренними узлами; факгпор сбалансированности обозначен внутри каждого узла знаками "+", 'ч" и "—" в соответствии с величиной разности между высотами правого и левого поддеревьев (+1, 0 или -1). Дерево Фибоначчи на рнс.
8 Рис. 20. Сбаланснровашше бинарное дерево. в разделе 6.2.1 служит еще одним примером сбалансированного бинарного дерева высотой 5 с 12 внутренними узлами; большинство факторов сбалансированности в этом дереве равны — 1. Дерево знаков зодиака на рис. 10 в разделе 6,2.2 не сбалансировано, поскольку лля узлов А00АЕ1УЯ и СЕИ1И1 нарушено условие для величины разности высот поддеревьев.
Такое определение сбалансированности представляет собой компромисс между оюиимальнм ии бинарными деревьями (все внешние узлы которых должны размещаться на двух соседних уровнях) и произвольными бинарными деревьями. Отсюда естественным образом возникает вопрос "Насколько далеко от оптимального может оказаться сбалансированное дерево?". Ответ на него гласит, что путь поиска по сбалансированному дереву не превышает пути поиска по оптимальному дереву более чем на 45%. Теорема А (Лдельсон-Вельский и Ланднс).
Высота сбалансированного дерев~ с Л! онутрепнлмп узламл ограничена значснлтт 1я(Х + 1) а 1.4405!Е(Ф + 2) — 0.3277. Доказаглельсгпео. Бинарное дерево высотой Ь, очевидно, не может иметь более 2" внешних узлов; таким образом, 1т'+1 < 2", т, е. Ь > ~!Е(%+1)1 для любого бинарного дерева. Для поиска максимального значения Ь рассмотрим проблему с другой стороны и зададимся вопросом о минимальном количестве узлов в сбалансированном дереве высотой Ь. Пусть Ть — такое дерево с наименьшим возможным количеством узлов, тогда одно из поддеревьев корня, например левое, имеет высоту Ь вЂ” 1, а правое —- Ь вЂ” 1 или Ь вЂ” 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
