82-110]. Вытянутые деревья, подобно другим видам уже упоминавшихся сбалансированных деревьев, подцерживают операции как вставки и удаления, так и конкатенации и разделения, причем достаточно простым образом. Более того, время, необходимое для доступа к данным в вытянутом дереве, не превышает времени доступа в статически оптимальном дереве, умноженного на некоторую небольшую константу (в установившемся режиме после серии операций с деревом). Слитор и Таржан предположили, что общее время доступа в вытянутом дереве не превышает оптимального времени доступа к данным и времени, необходимого для вьшолнения динамических поворотов согласно любому алгоритму работы с бинарными деревьями, умноженного на константу.

Рандомизация позволяет использовать методы, даже более быстрые и простые, чем вытянутые деревья. Жан Вуйлемен (Jean Vuillemin) [САСМ 23 (1980), 229-239] ввел понятие декартовых деревьев (cartesian trees), в которых каждый узел имеет два ключа {х,у). Часть х упорядочена слева направо, как в бинарных деревьях поиска; часть у упорядочена сверху вниз, как в случае приоритетной очереди (см. раздел 5.2.3). С. Р. Арагон (С. R. Aragon) и Р. Г. Зайдель (R. G. Seidel) присвоили таким структурам данных очень цветастое название treap, которое получено в результате комбинирования частей слов trees и heaps. (Видимо, наилучший русский термин должен звучать как дуча - от дерева и кучи. - Прим. перев.) Только одна дуча может быть построена на основе п данных пар ключей {xi,yi), ..., (х„, у„), если все хну различны. Один из путей получения дучи - вставка х согласно алгоритму 6.2.2Т в соответствии с порядком у. Однако имеется еще один простой алгоритм для непосредственной вставки любых новых пар в дучу. Арагон и Зайдель обнаружили [FOCS 30 (1989), 540-546], что, если х представляют собой обычные ключи, а у выбираются случайным образом, можно быть уверенным, что дуча имеет вид случайного бинарного дерева поиска. В частности, дуча со случайными значениями у всегда будет сбалансирована, за исключением случая экспоненциально малой вероятности (см. упр. 5.2.2-42). Арагон и Зайдель также показали, что дучи могут быть легко "скошены", так что, например, ключ х с относительной частотой / будет располагаться вблизи корня в соответствии со своей частотой, если с ним будет ассоциирована величина у = C , где U - случайное число между О и 1. Дучи, в целом, предпочтительнее вытянутых деревьев, как показали некоторые проведенные Д. Э. Кнутом эксперименты, связанные с расчетами выпуклых оболочек [JACM 45 (1998), 288-323].

В следующее издание книги планируется добавить раздел 6.2.5, посвященный рандомизированным структурам данных. В нем будут рассмотрены списки с пропусками [W. Pugh, САСМ 33 (1990), 668-676], рандомизированные бинарные деревья поиска [S. Roura and С. Martinez, JACM 45 (1998), 288-323], а также упомянутые в этом разделе "дучи".

УПРАЖНЕНИЯ

1. [01] Почему в случае 2 в (1) нельзя просто поменять местами левые поддеревья узлов А и В?

2. [16] Объясните, почему, если достигнут шаг А7 с B(S) = О, дерево становится на один уровень выше.

► 3. [М25] Докажите, что сбалансированное дерево с N внутренними узлами не может содержать более {ф-1)М « 0.61803iV узлов с ненулевыми факторами сбалансированности.

4. [М22] Докажите или опровергните следующее утверждение: среди всех сбалансированных деревьев с Fh+i - 1 внутренними узлами дерево Фибоначчи порядка h имеет наибольщую длину внутреннего пути.

► 5. [М25] Докажите или опровергните следующее утверждение: если для последовательной вставки ключей К2, - Kn в дерево, изначально содержащее только ключ К\ (Ki < К2 < < Kn), используется алгоритм А, то полученное дерево всегда оптимально (т. е. имеет минимальную длину внутреннего пути среди всех бинарных деревьев с N узлами).

6. [М21] Докажите, что (5) определяет производящую функцию для сбалансированных деревьев высотой h.

7. [М27] (Н. Дж. А. Слоан (N. J. А. Sloane) и А. В. Ахо (А. V. Aho).) Докажите замечательную формулу (9) для числа сбалансированных деревьев высотой h. (Указание. Положим, что Сп = Вп + Вп~1, к используем тот факт, что log(Сп-ц/С) очень мало при больщих п.)

8. [М24] (Л. А. Хиздер.) Покажите, что существует константа/3, такая, что Bj,(l)/Bh(l) = 2ЧЗ-1 + 0(2VBh i) при /I оо.

9. [НМ44] Чему равно асимптотическое число сбалансированных бинарных деревьев с п внутренними узлами Ylh>o -nh? Чему равна асимптотическая средняя высота Ylh>o hBnh/

► 10. [27] (P. К. Ричарде (R. С. Richards).) Покажите, что сбалансированное дерево может быть единственным образом построено по списку его факторов сбалансированности B(l)B(2)...B(iV) в симметричном порядке.

11. [М24] (Марк Р. Браун (Mark R. Brown).) Докажите, что при п > 6 среднее количество внещних узлов каждого из типов +А, -А, ++В, +-В, -+В, -В составляет в точности (п -f 1)/14 для случайных сбалансированных деревьев с п внутренними узлами, построенных по алгоритму А.

► 12. [24] Чему равно максимально возможное время работы программы А при вставке восьмого узла в сбалансированное дерево? Чему равно минимальное время для этого случая?

13. [05] Почему поле RANK лучше использовать так, как указано в тексте, а не хранить индекс каждого "узла в качестве его ключа (называя первый узел "1", второй - "2" и т. д.)?

14. [11] Можно ли адаптировать алгоритмы 6.2.2Т и 6.2.2D для работы с линейными списками с использованием поля RANK, как это было сделано для алгоритмов работы со сбалансированными деревьями?

15. [18] (К. А. Крейн (С. А. Crane).) Предположим, что упорядоченный линейный список представлен в виде бинарного дерева с полями KEY и RANK в каждом узле. Разработайте алгоритм, который осуществляет поиск в дереве данного ключа К и определяет его положение в списке, т. е. находит число т, такое, что меньше К лишь т - 1 ключей.

► 16. [20] Нарисуйте сбалансированное дерево, которое получается после удаления узла Е и корневого узла F из дерева, показанного на рис. 20, с использованием предложенного в тексте алгоритма.

► 17. [21] Нарисуйте сбалансированное дерево, которое получается после конкатенации дерева Фибоначчи (12): (а) справа и (Ь) слева от дерева, показанного на рис. 20, с помощью предложенного в тексте алгоритма конкатенации.

18. [22] Нарисуйте сбалансированные деревья, которые получаются после разделения дерева, показанного на рис. 20, на две части ({А, ...,1} и {J, ...,Q}) с использованием предложенного в тексте алгоритма.

► 19. [26] Найдите способ преобразования данного сбалансированного дерева так, чтобы фактор сбалансированности в корне не был равным -1. При этом должен сохраняться симметричный порядок узлов и должно порождаться искомое сбалансированное дерево за 0(1) единиц времени независимо от количества узлов в исходном дереве.

20. [40] Рассмотрите идею использования ограниченного класса сбалансированных деревьев с факторами сбалансированности, равными О или -f 1 (в этом случае поле В может свестись к одному биту). Существует ли для таких деревьев процедура вставки с разумной эффективностью?

► 21. [30] {Идеальная балансировка.) Разработайте алгоритм построения бинарных деревьев с N узлами, которые оптимальны в смысле упр. 5. Он должен выполняться за 0{N) шагов и быть "последовательным", т. е. вы должны получать узлы по одному в порядке возрастания и строить частичные деревья по ходу, не зная окончательного значения N (такой алгоритм может пригодиться для перестройки плохо сбалансированного дерева или при слиянии двух деревьев в одно).

22. [М20] Каков аналог теоремы А для взвешенно-сбалансированных деревьев?

23. [М20] (Э. Рейнгольд (Е. Reingold).) Покажите, что между сбалансированными по высоте и взвешенно-сбалансированными деревьями не существует простой взаимосвязи.

a) Докажите, что существуют сбалансированные по высоте деревья со сколь угодно малым отношением (вес левого поддерева)/(вес правого поддерева) в смысле (17).

b) Докажите, что существуют взвешенно-сбалансированные деревья, имеющие сколь угодно большую разность между высотой левого и правого поддеревьев.

24. (Э. Рейнгольд.) Докажите, что если усилить условие (17) до

1 левый вес

2 правый вес

то ему будут удовлетворять только идеально сбалансированные бинарные деревья с 2" - 1 внутренними узлами. (В таких деревьях левые и правые веса в каждом узле равны между собой.)

25. [27] (Ю. Нивергельт (J. Nievergelt), Э. Рейнгольд и Ч. Вонг (С. Wong).) Покажите, что можно разработать алгоритм вставки во взвешенно-сбалансированные деревья с сохранением условия (17), выполняющий не более O(logiV) поворотов на вставку.

26. [40] Исследуйте свойства сбалансированных t-арных деревьев при t > 2.

► 27. [М23] Оцените максимальное количество сравнений, необходимых для поиска в 2-3-дереве с N внутренними узлами.

28. [41] Реализуйте алгоритмы работы с 2-3-деревьями программно с достаточной эффективностью.

29. [М47] Проанализируйте поведение 2-3-деревьев в среднем при случайных вставках.

30. [26] (Э. Мак-Крейт (Е. McCreight).) В разделе 2.5 обсуждался ряд стратегий динамического распределения памяти, включая метод наилучшего подходящего (best-fit) (выбор области наименьшего размера, удовлетворяющей запросу) и метод первого подходящего (first-fit) (выбор области с наименьшим адресом, удовлетворяющей запросу). Покажите, что если свободное пространство связано в сбалансированное дерево, то можно найти как (а) наилучшую подходящую, так и (Ь) первую подходящую области за O(logn) единиц времени, где п - количество доступных областей (алгоритмы из раздела 2.5 выполняют поставленную задачу за 0{п) шагов).