по отдельности, а H{XY) = H{rii,... ,Гтп) - энтропия их совместного распределения. Докажите, что

ЩХ) < Н(ХУ) < Н(Х) + Н{¥). {Указание. Если / - вогнутая функция, то Е/(Х) < f{EX).)

37. [НМ26] (П. Дж. Байер (Р. J. Bayer), 1975.) Предположим, что (Pi,...,P„) представляет собой случайное распределение вероятностей, а именно - случайную точку в (п - 1)-мерном симплексе, определенную величинами Ра- > О, 1 < А; < п, где Pi + + Рп = I (или, что то же самое, (Pi,...,P„) представляют собой множество случайных промежутков, о которых говорилось в упр. 3.3.2-26). Чему равно ожидаемое значение

энтропии Я(Р1,...,Р„)?

38. [М20] Поясните, почему теорема М справедлива в общем случае, хотя мы доказали ее только для случая «о < si < S2 < < «п.

► 39. [М25] Пусть W1, ..., w„ представляют собой неотрицательные веса (wi + +w„ = 1). Докажите, что взвещенная длина пути дерева Хаффмана, построенного в разделе 2,3.4.5, меньше, чем H{wi,.. . ,w„) + 1. {Указание. Обратитесь к доказательству теоремы М.)

40. [М2б] Завершите доказательство леммы Z.

41. [21] На рис. 18 показано строение весьма запутанного бинарного дерева. Перечислите его листья в порядке слева направо.

42. [23] Объясните, почему в подпрограмме С сохранаяется справедливость условия (31).

43. [20] Поясните, как эффективно реализовать фазу 2 алгоритма Гарсия-Воча.

► 44. [25] Поясните, как эффективно реализовать фазу 3 алгоритма Гарсия-Воча: постройте бинарное дерево с уровнями lo, h, ..., 1„ листьев в симметричном порядке.

► 45. [30] Поясните, как реализовать подпрограмму С так, чтобы общее время работы алгоритма Гарсия-Воча не превышало 0(пlogn).

46. [МЗО] (Ч. К. Вонг (С. К. Wong) и Ши-Куо Чанг (Shi-Kuo Chang).) Рассмотрим схему, в которой бинарное дерево поиска строится согласно алгоритму Т, но, когда количество узлов достигает значений вида 2" - 1, дерево реорганизуется в идеально сбалансированное дерево с 2* узлами на уровне к, О < к < п. Докажите, что общее количество сравнений, выполненных при построении такого дерева, в среднем равно NlgN + 0{N). (Нетрудно показать, что время, необходимое для реорганизации дерева, составляет 0{N).)

47. [М40] Обобщите теоремы В и М для <-арных деревьев. По возможности рассмотрите случай, когда цены ветвей неодинаковы, как в упр. 33.

48. [М47] Проведите точный анализ устойчивого состояния бинарного дерева поиска при случайных вставках и удалениях.

49. [НМ42] Проанализируйте среднюю высоту бинарного дерева поиска. 6.2.3. Сбалансированные деревья

Алгоритм вставки в дерево, который мы только что изучили, дает хорошие результаты при использовании случайных входных данных, но все же существует неприятная возможность того, что при этом будет построено вырожденное дерево. Можно было бы разработать алгоритм, поддерживающий дерево в оптимальном состоянии все время, однако это, к сожалению, очень сложная задача. Другая идея заключается в том, чтобы хранить обш;ую длину пути и полностью реорганизовывать дерево, когда она превышает, например, ojVlgiV. Тем не менее при таком подходе потребовалось бы порядка /N/2 реорганизаций дерева в процессе его построения.

Очень красивое решение проблемы поддержания дерева поиска в хорошем состоянии было открыто в 1962 году двумя советскими математиками - Г. М. Адельсон-Вельским и Е. М. Ландисом [ДЛЯ СССР 146 (1962), 263-266; английский перевод Soviet Math. 3, 1259-1263]. Их метод требует всего лишь двух дополнительных битов на узел и никогда не использует более O(logiV) операций для поиска по дереву или вставки элемента. Предложенный подход также дает обшую технологию представления линейных списков длиной N таким образом, что любая из следующих операций может быть выполнена за время O(logiV):

i) поиск элемента по заданному ключу;

ii) поиск к-го элемента по заданному к;

iii) вставка элемента в определенное место;

iv) удаление определенного элемента.

При последовательном расположении элементов линейных списков операции (i) и (ii) выполняются очень эффективно, в то время как операции (iii) и (iv) требуют порядка N шагов. С другой стороны, при использовании связанных элементов эффективно будут выполняться операции (iii) и (iv), а операции (i) и (ii) потребуют порядка N шагов. Представление линейных списков в виде дерева позволяет выполнить все четыре операции за O(logiV) шагов. При этом можно более или менее эффективно выполнять и другие операции, например сцепление списка из М элементов со списком из N элементов за 0(log(M + iV)) шагов.

Метод, предоставляющий все эти преимущества, будем называть сбалансированными деревьями (многие авторы используют термин AVL-деревья - по первым буквам фамилий авторов). Предыдущий абзац служит рекламой сбалансированных деревьев - эдакой панацеи от всех бед. Имея в руках такой мощный метод, можно смело выбросить на помойку все прочие методы! Однако не торопитесь - сначала сбалансируйте свое отношение к сбалансированным деревьям. Ведь, например, если все четыре операции не нужны, нас может удовлетворить менее универсальный, но более быстрый (для данного конкретного случая) и проще программируемый метод. Кроме того, сбалансированные деревья хороши при наличии большого количества элементов. Судите сами: если есть эффективный метод, который требует 64 IgiV единиц времени, и неэффективный, которому необходимо 2iV единиц, то при Л < 256 следует использовать неэффективный метод, который при этом становится более эффективным... С другой стороны, при очень больших N хранение данных во внутренней памяти становится невозможным, а при использовании внешних файлов с прямым доступом более эффективны другие методы, о которых речь пойдет в разделе 6.2.4. Впрочем, оперативная память становится все дешевле, а значит, сбалансированные деревья становятся все более и более важным орудием в руках программиста.

Высота дерева определяется как его максимальный уровень, длина самого длинного пути от корня к внешнему узлу. Бинарное дерево назьшается сбалансированным, если высота левого поддерева любого узла отличается не более чем на ±1 от высоты правого поддерева. На рис. 20 показано сбалансированное дерево высотой 5 с 17 внутренними узлами; фактор сбалансированности обозначен внутри каждого узла знаками "-f-" "•" и "-" в соответствии с величиной разности между высотами правого и левого поддеревьев (-1-1, О или -1). Дерево Фибоначчи на рис. 8

Рис. 20. Сбалансированное бинарное дерево.

в разделе 6.2.1 служит еще одним примером сбалансированного бинарного дерева высотой 5 с 12 внутренними узлами; большинство факторов сбалансированности в этом дереве равны -1. Дерево знаков зодиака на рис. 10 в разделе 6.2.2 не сбалансировано, поскольку для узлов AQUARIUS и GEMINI нарушено условие для величины разности высот поддеревьев.

Такое определение сбалансированности представляет собой компромисс между оптимальными бинарными деревьями (все внешние узлы которых должны размещаться на двух соседних уровнях) и произвольными бинарными деревьями. Отсюда естественным образом возникает вопрос "Насколько далеко от оптимального может оказаться сбалансированное дерево?! Ответ на него гласит, что путь поиска по сбалансированному дереву не превышает пути поиска по оптимальному дереву более чем на 45%.

Теорема А (Адельсон-Вельский и Ландис). Высота сбалансированного дерева с N внутренними узлами ограничена значениями \g{N + 1) я 1.4405 lg(A + 2) - 0.3277.

Доказательство. Бинарное дерево высотой h, очевидно, не может иметь более 2 внешних узлов; таким образом, N+1 < 2, т.е.Н> [ig(iV-l-l) для любого бинарного дерева.

Для поиска максимального значения h рассмотрим проблему с другой стороны и зададимся вопросом о минимальном количестве узлов в сбалансированном дереве высотой h. Пусть - такое дерево с наименьшим возможным количеством узлов, тогда одно из поддеревьев корня, например левое, имеет высоту h - 1, а правое - h - 1 или h - 2. Поскольку дерево Th должно иметь минимальное количество узлов, можно считать, что в силу определения левое поддерево представляет собой дерево Th-i, а правое - Т-2- Таким образом, наименьшее возможное количество узлов среди всех сбалансированных деревьев имеет дерево Фибоначчи (см. определение деревьев Фибоначчи в разделе 6.2.1). Следовательно,

N > Fh+2 - 1 > ф/ - 2 и требуемый результат получается так же, как и следствие из теоремы 4.5.3F.