которое, может быть, еще не использовалось, сначала нужно проверить, выполняются ли условия О < Vlkl < п и LlV[A:]] = к. Если не выполняются, то необходимо установить Vlkl •(- п, L[n] •(- /г, А[А:] 4- О и п •(- п + 1. В противном случае элемент А [А:] наверняка содержит рабочие данные. (Несколько расширив этот метод, можно сохранить и впоследствии восстановить содержимое всех элементов А и V, которые изменяются во время этих вычислений.)

РАЗДЕЛ 2.3

1. Существует три способа выбора корня. После выбора в качестве корня, например, узла А существует еще три способа подразделения других узлов на поддеревья: {В}, {С}; {С}, {В}; {В, С}. В последнем случае существует также два способа превращения {В, С} в дерево в зависимости от того, какой узел является корнем. Следовательно, получим четыре дерева с узлом А в качестве корня, а всего -12 различных деревьев. Эта задача решается для любого количества узлов п в

упр. 2.3.4.4-23.

2. Первые два дерева в ответе к упр. 1 идентичны, как ориентированные деревья, поэтому получим 9 различных возможностей. Общий случай рассматривается в разделе 2.3.4.4, в котором доказана справедливость формулы п"~.

3. Часть 1. Покажем, что существует по крайней мере одна такая последовательность. Пусть дерево содержит п узлов. Решение в случае, когда п = 1, очевидно, так как А является корнем. Если п > 1, согласно определению предполагается, что существует корень Al и поддеревья Ti, Гг,..., Тщ] либо X = Xi, либо X является членом какого-то единственного поддерева Г,. В последнем случае по индукции существует путь Х2, ,Х, где Аг является корнем поддерева Г,, и, так как Al - родитель Аг. получим путь Al, Аг,..., А.

Часть 2. Покажем, что существует не более одной такой последовательности. Докажем по индукции, что, если X не является корнем дерева, X имеет единственного родителя (так что узел Xk определяет узел Xk-i, который определяет узел Xk-2, и т. д.). Если дерево имеет один узел, доказательство очевидно; иначе А находится в единственном поддереве Г,. Либо X является корнем Г, и по определению узел X имеет единственного родителя, либо X не является корнем Г, и в этом случае узел X по индукции имеет единственного родителя Г,, причем никакой другой узел за пределами поддерева Г, не может быть родителем узла А.

4. Верно (к сожалению).

5. 4.

6. Пусть родитель(А) = А и пусть родитель*"*"(А) = родитель(родитель*(А)), так что родитель(А) является родителем узла X. а родитель(Л)-прародителем узла А. Когда к > 2, родитель(А) является пра*~прародителем А. Искомое условие родства заключается в том, что родитель""*"1(А) = родитель™"""""1-(У), но родитель"(А) / родитель""*""(У). Если п > О, это условие несимметрично по отношению к А и Y, хотя оно считается симметричным в повседневных ситуациях.

7. Используйте несимметричное условие из упр. 6 и учтите тот факт, что родитель(А) ф родитель*(У), если j или к (или оба сразу) равны -1. Чтобы показать, что это отношение всегда истинно для единственного значения т и единственного значения п, рассмотрим десятичную систему обозначений Дьюи для А и Y, а именно-l.ai. • • Mp.bi. \ и l.ai. • • .Op.ci. • .Cr, где р > О, g > О, г > О и bi ф ci (если qr ф 0).

в таком виде можно переписать обозначения для любой пары узлов, а потому, очевидно, следует принять, что т = q - 1 ит--п = г-1

8. Ни одно бинарное дерево не является деревом Это совершенно разные понятия не( мотря на то что схема непустого бинарного дерева очень похожа на дерево

9. Корнем является узел А, поскотьку корень обычно располагается сверху

10. Любой конечный набор вложенных множеств можно сопоставить с лесом, определенным выше Пусть Al ,Ап-множества данного набора, которые не содержатся ни в каких других множествах Для фиксированного j совокупность всех множеств, которые содержатся в Aj, является вложенной, следовательно, можно допустить, что эта совокупность соответствует дереву, не упорядоченному с множеством Aj в качестве корня

11. Пусть во вложенном наборе С отношение X = Y выпотняется, если существует такое Z С что X и У С Z Очевидно, что это отношение рефлексивно и симметрично, а также фактически является отношением эквивалентности, поскольку W = X и X = Y подразумевает, что существуют такие Zi и Z2 в наборе С с W С Zi, X С Zi П Z2 и Y С Z2 Так как Zi П Z2 Ф О, то либо Zi С Z2, либо Z2 С Zi, следовательно, W UY С ZiU Z2 еС Теперь, если С является вложенным набором, определим соответствующий набору С ориентированный тес согласно правилу "X является предком 1, а У-потомком А тогда и тотько тогда, когда X Э У Каждый класс эквивалентности набора С соответствует ориентированному дереву, которое явтяется ориентированным лесом с отношением X = Y для всех А, 1 (Таким образом, мы обобщили определения леса и дерева, которые ранее были даны только дтя конечных наборов ) На основе этих рассуждений можно определить уровень множества А как кардинальное число множества предков (X) .Лналогично степень множества А является кардинальным числом классов эквивалентности во вложенном наборе потомков (Х) Назовем А родителем У, а У - сыном (дочерью) X, если А является предком 1 , но не С} ществует таких Z, что X D Z DY {X может иметь потомков, которые не явтяготея его детьми, или иметь предков, которые не являются его родителями ) Для упорядочения деревьев и леса некоторым специальным образом зададим порядок среди упомянутых выше классов эквивалентности, например, расширив отношение С до понятия линейного порядка, как в упр 2 2 3-14

Пример (а) П>сть Sak = { х \ х = didjds в десятичной системе обозначений, где а = ехРгСз в десятичной системе обозначений и dj = ej, если J mod 2* 0} Набор С = {Sak fc>0,0<q< 1} является вложенным и соответствует дереву с бесконечным количеством уровней и несчетной степенью каждого узла

Примеры (Ь) и (с) В таком случае удобно рассматривать это множество на плоскости, вместо того чтобы использовать действительные числа, к тому же между плоскостью и множеством действительных чисел существует взаимно однозначное соответствие Пусть Samn = {(о, у) I т/2" <у<{т + 1)/2"} и пусть Tq = {{х,у) \ х < а} Легко видеть, что набор С = {Samn I О < а < 1, п > О, О < m < 2"} и {Tq О < q < 1} является вложенным Детьми множества Samn являются Sa(2m){n+i) И Sa{2m+i){n+i), а множество Та имест ребенка 5qoo плюс поддерево {Spmn /3 < а} U {Т \ /3 < а} Таким образом, каждый узел обладает степенью 2 и имеет несчетное множество предков вида Та Это построение предложено Р Г Байглоу (R Bigelow)

Замечание Данное построение можно усовершенствовать, если подходящим образом упорядочить множество действительных чисел и определить Та = {(х, у) \ х у а}, получая в результате вложенный набор, в котором каждый узел имеет несчетный уровень, степень 2 и двоих детей

12. Для того чтобы обеспечить соответствие теса частично упорядоченному множеству, наложим на него дополнительное ограничение (аналогично "вложенным множествам") если х X J/ и х X г, то либо у :< z, либо z -< у Иначе говоря, элементы, которые

больше данного элемента, являются линейно упорядоченными. Для получения дерева также следует предположить существование такого наибольшего элемента г, что х < г для всех X. Доказательство трго факта, что в результате получится определенное выше неупорядоченное дерево, если число узлов конечно, проводится так же, как и для вложенных множеств в упр. 10.

13. ai, 01.02, 01.02. • • .ojfe.

14. Поскольку множество S не является пустым, оно содержит элемент 1 оь • .ojt, где к принимает минимально возможное значение. Если fc > О, выберем в множестве S минимально возможное значение ojt и сразу же получим, что к должно быть равно 0. Иначе говоря, S должно содержать элемент 1. Пусть этот элемент является корнем. Все остальные элементы fc > О, а потому оставшиеся элементы множества S можно разбить на множества 5j = {l.j.02. •.Ojt}, 1 < J < т, для некоторого т > 0. Если m / О и множество Sm не пусто, то по тем же соображениям получим, что l.j принадлежит множеству Sj для каждого Sj Поэтому каждое множество Sj не пусто. Тогда легко видеть, что множества Sj = {1.02. • • .ofc I i.J.02. -ak принадлежит Sj,} удовлетворяют тому же условию, что и множество S. По индукции каждое множество Sj образует дерево.

15. Пусть 1 - корень, а а.О и Q.1 - корни левого и правого поддеревьев дерева а соответственно, если такие корни существуют. Например, на рис. 18, (а) Король Кристиан IX встречается дважды, а именно - в позициях 1.0.0.0.0 и 1.1.0 0.1.0. Для краткости опустим десятичные точки в этих обозначениях и получим 10000 и 110010.

Замечание. Это обозначение предложено Ф. Гальтоном (Francis Galton); см. NatursJ Inheritance (Macmillan, 1889), 249. Для родословных лучше использовать мнемонические обозначения F (father - отец) и М (mother - мать) вместо О и 1 и отбросить начальную единицу. Тогда родственное отношение Кристиана IX по отношению к Чарльзу можно выразить обозначением MFFMF, т. е Кристиан IX является отцом матери отца отца матери Чарльза. Система обозначений на основе О и 1 интересна еще и тем, что она позволяет установить важное соотношение между узлами бинарного дерева и положительными целыми числами в двоичной системе (а именно - между адресами в памяти компьютера).

16. (а) (Ь) или

17. Узел-родитель (F[l]) = А, узел-родитель (F[l,2]) = С; следовательно, узел-родитель (F[l,2,2]) = £;.

18. Z/[5,1,1] = (2). L[3,1] не имеет смысла, так как L[3] является пустым Списком.

19. *[L] L[2] = {L); L[2,l,l] = a.

20. (Интуитивно соответствие между О-2-деревьями и бинарными деревьями можно получить, удалив все концевые узлы в О-2-дереве См. построение в разделе 2.3 4.5.) Пусть О-2-дерево с одним узлом соответствует пустому бинарному дереву, а 0-2-дерево с более чем одним узлом, состоящее из корня г и 0-2-деревьев Ti и Гг, соответствует бинарному дереву с корнем г, левым поддеревом Т[ и правым поддеревом Г где Ti и Гг соответствуют Ti и Гг.