Программирование: теоремы и задачи (стр. 29 )

"сбалансированности" дерева. Об этом см. в следующем пункте.

12.1.8. Предположим, что необходимо уметь также отыскивать

k-ый элемент множества (в порядке возрастания), причем коли-

чество действий должно быть не более C*(высота дерева). Какую

дополнительную информацию надо хранить в вершинах дерева?

Решение. В каждой вершине будем хранить число всех ее по-

томков. Добавление и исключение вершины требует коррекции лишь

на пути от корня к этой вершине. В процессе поиска k-ой вершины

поддерживается такой инвариант: искомая вершина является s-ой

вершиной поддерева с корнем в x (здесь s и x - переменные).)

12.2. Сбалансированные деревья.

Дерево называется сбалансированным (или АВЛ-деревом в честь

изобретателей этого метода -Вельского и -

са), если для любой его вершины высоты левого и правого подде-

ревьев этой вершины отличаются не более чем на 1. (В частности,

когда одного из сыновей нет, другой - если он есть - обязан быть

листом.)

12.2.1. Найти минимальное и максимальное возможное коли-

чество вершин в сбалансированном дереве высоты n.

Решение. Максимальное число вершин равно (2 в степени n) -

1. Если m (n) - минимальное число вершин, то, как легко видеть,

m (n + 2) = 1 + m (n) + m (n+1),

откуда

m (n) = fib (n+1) - 1

(fib(n) - n-ое число Фибоначчи, fib(0)=1, fib(1)=1, fib(n+2) =

fib(n) + fib(n+1)).

12.2.2. Доказать, что сбалансированное дерево с n вершинами

имеет высоту не больше C * (log n) для некоторой константы C, не

зависящей от n.

Решение. Индукцией по n легко доказать, что fib [n+1] >= (a

в степени n), где a - больший корень квадратного уравнения a*a =

1 + a, то есть a = (sqrt(5) + 1)/2. Остается воспользоваться

предыдущей задачей.

Вращения.

Мы хотим восстанавливать сбалансированность дерева после

включения и удаления элементов. Для этого необходимы какие-то

преобразования дерева, не меняющие множества пометок на его вер-

шинах и не нарушающие упорядоченности, но способствующие лучшей

сбалансированности. Опишем несколько таких преобразований.

Пусть вершина a имеет правого сына b. Обозначим через P ле-

вое поддерево вершины a, через Q и R - левое и правое поддеревья

вершины b.

Упорядоченность дерева требует, чтобы P < a < Q < b < R

(точнее следовало бы сказать "любая пометка на P меньше пометки

на a", "пометка на a меньше любой пометки на Q" и т. д., но мы

позволим себе этого не делать). Точно того же требует упорядо-

ченность дерева с корнем b, его левым сыном a, в котором P и Q -

левое и правое поддеревья a, R - правое поддерево b. Поэтому

первое дерево можно преобразовать во второе, не нарушая упорядо-

ченности. Такое преобразование назовем малым правым вращением

(правым - поскольку существует симметричное, левое, малым - пос-

кольку есть и большое, которое мы сейчас опишем).

Пусть b - правый сын a, c - левый сын b, P - левое поддерево

a, Q и R - левое и правое поддеревья c, S - правое поддерево b.

Тогда P < a < Q < c < R < b < S.

Такой же порядок соответствует дереву с корнем c, имеющим левого

сына a и правого сына b, для которого P и Q - поддеревья вершины

a, а R и S - поддеревья вершины b. Соответствующее преобразова-

ние будем называть большим правым вращением. (Аналогично опреде-

ляется симметричное ему большое левое вращение.)

12.2.3. Дано дерево, сбалансированное всюду, кроме корня, в

котором разница высот равна 2 (т. е. левое и правое поддеревья

корня сбалансированы и их высоты отличаются на 2). Доказать, что

оно может быть превращено в сбалансированное одним из четырех

описанных преобразований, причем высота его останется прежней

или уменьшится на 1.

Решение. Пусть более низким является, например, левое под-

дерево, и его высота равна k. Тогда высота правого поддерева

равна k+2. Обозначим корень через a, а его правого сына (он обя-

зательно есть) через b. Рассмотрим левое и правое поддеревья

вершины b. Одно из них обязательно имеет высоту k+1, а другое

может иметь высоту k или k+1 (меньше k быть не может, так как

поддеревья сбалансированы). Если высота левого поддерева равна

k+1, а правого - k, до потребуется большое правое вращение; в

остальных случаях помогает малое.

------------------------------------

------------------------------------

------------------------------------

высота уменьшилась на 1

------------------------------------

------------------------------------

------------------------------------

высота не изменилась

k-1 или k (в одном из случаев k)

------------------------------------

------------------------------------

------------------------------------

высота уменьшилась на 1

Три случая балансировки дерева.

12.2.4. В сбалансированное дерево добавили или из него уда-

лили лист. Доказать, что можно восстановить сбалансированность с

помощью нескольких вращений, причем их число не больше высоты

дерева.

Решение. Будем доказывать более общий факт:

Лемма. Если в сбалансированном дереве X одно из его подде-

ревьев Y заменили на сбалансированное дерево Z, причем высота Z

отличается от высоты Y не более чем на 1, то полученное такой

"прививкой" дерево можно превратить в сбалансированное вращени-

ями (причем количество вращений не превосходит высоты, на кото-

рой делается прививка).

Частным случаем прививки является замена пустого поддерева

на лист или наоборот, так что достаточно доказать эту лемму.

Доказательство леммы. Индукция по высоте, на которой дела-

ется прививка. Если она происходит в корне (заменяется все дере-

во целиком), то все очевидно ("привой" сбалансирован по усло-

вию). Пусть заменяется некоторое поддерево, например, левое под-

дерево некоторой вершины x. Возможны два случая.

(1) После прививки сбалансированность в вершине x не нару-

шилась (хотя, возможно, нарушилась сбалансированность в предках

x: высота поддерева с корнем в x могла измениться). Тогда можно

сослаться на предположение индукции, считая, что мы прививали

целиком поддерево с корнем в x.

(2) Сбалансированность в x нарушилась. При этом разница вы-

сот равна 2 (больше она быть не может, так как высота Z отлича-

ется от высоты Y не более чем на 1). Разберем два варианта.

(2а) Выше правое (не заменявшееся) поддерево вершины x.

Пусть высота левого (т. е. Z) равна k, правого - k+2. Высота ста-

рого левого поддерева вершины x (т. е. Y) была равна k+1. Подде-

рево с корнем x имело в исходном дереве высоту k+3, и эта высота

не изменилась после прививки.

По предыдущей задаче вращение преобразует поддерево с кор-

нем в x в сбалансированное поддерево высоты k+2 или k+3. То есть

высота поддерева с корнем x - в сравнении с его прежней высотой

- не изменилась или уменьшилась на 1, и мы можем воспользоваться

предположением индукции.

------------- ----------------

------------- ----------------

-------------k ----------------k

2а 2б

(2б) Выше левое поддерево вершины x. Пусть высота левого

(т. е. Z) равна k+2, правого - k. Высота старого левого поддерева

(т. е. Y) была равна k+1. Поддерево с корнем x в исходном дереве

X имело высоту k+2, после прививки она стала равна k+3. После

подходящего вращения (см. предыдущую задачу) поддерево с корнем

в x станет сбалансированным, его высота будет равна k+2 или k+3,

так что изменение высоты по сравнению с высотой поддерева с кор-

нем x в дереве X не превосходит 1 и можно сослаться на предполо-

жение индукции.

12.2.5. Составить программы добавления и удаления элемен-

тов, сохраняющие сбалансированность. Число действий не должно

превосходить C*(высота дерева). Разрешается хранить в вершинах

дерева дополнительную информацию, необходимую при балансировке.

Решение. Будем хранить для каждой вершины разницу между

высотой ее правого и левого поддеревьев:

diff [i] = (высота правого поддерева вершины с номером i) -

(высота левого поддерева вершины с номером i).

Нам потребуются четыре процедуры, соответствующие большим и ма-

лым правым и левым вращениями. Но вначале два замечания.

(1) Нам нужно, чтобы при вращении поддерева номер его корня

не менялся. (В противном случае потребовалось бы корректировать

информацию в отце корня, что нежелательно.) Этого можно достичь,

так как номера вершин дерева можно выбирать независимо от их

значений. (На картинках номер указан сбоку от вершины, а значе-

ние - внутри.)

Малое правое вращение

Большое правое вращение

(2) После преобразований мы должны также изменить соот-

ветственно значения в массиве diff. Для этого достаточно знать

высоты деревьев P, Q, ... с точностью до константы, поэтому мож-

но предполагать, что одна из высот равна нулю.

Вот процедуры вращений:

procedure SR (a:integer); {малое правое вращение с корнем a}

| var b: 1..n; val_a, val_b: T; h_P, h_Q, h_R: integer;

begin

| b := right [a]; {b <> null}

| val_a := val [a]; val_b := val [b];

| h_Q := 0; h_R := diff[b]; h_P := (max(h_Q, h_R)+1)-diff[a];

| val [a] := val_b; val [b] := val_a;

| right [a] := right [b] {поддерево R}

| right [b] := left [b] {поддерево Q}

| left [b] := left [a] {поддерево P}

| left [a] := b;

| diff [b] := h_Q - h_P;

| diff [a] := h_R - (max (h_P, h_Q) + 1);

end;

procedure BR (a:integer);{большое правое вращение с корнем a}

| var b, c: 1..n; val_a, val_b, val_c: T;

| h_P, h_Q, h_R, h_S: integer;

begin

| b := right [a]; c := left [b]; {b, c <> null}

| val_a := val [a]; val_b := val [b]; val_c := val [c];

| h_Q := 0; h_R := diff[c]; h_S := (max(h_Q, h_R)+1)+diff[b];

| h_P := 1 + max (h_S, h_S-diff[b]) - diff [a];

| val [a] := val_c; val [c] := val_a;

| left [b] := right [c] {поддерево R}

| right [c] := left [c] {поддерево Q}

| left [c] := left [a] {поддерево P}

| left [a] := c;

| diff [b] := h_S - h_R;

| diff [c] := h_Q - h_P;

| diff [a] := max (h_S, h_R) - max (h_P, h_Q);

end;

Левые вращения (большое и малое) записываются симметрично.