Представление множеств. Деревья. Сбалансированные деревья.

Хранение деревьев в программе

Можно было бы сопоставить вершины полного двоичного дерева С числами $$1,2,3,\ldots$$ (считая, что левый сын $$n$$ есть $$2n$$, правый сын $$n$$ есть $$2n + 1$$ ) и хранить пометки в массиве val [1...]. Однако этот способ неэкономен, поскольку тратится место на хранение пустых вакансий в полном двоичном дереве.

Более экономен такой способ. Введем три массива

val: array [1..n] of T;
left, right: array [1..n] of 0..n;

( n - максимальное возможное число вершин дерева) И переменную root:0..n. Каждая вершина хранимого $$T$$ -дерева будет иметь номер - число от 1 до n. Разные вершины будут иметь разные номера. Пометка в вершине с номером x равна val[x]. Корень имеет номер root. Если вершина с номером i имеет сыновей, то их номера равны left[i] и right[i]. Отсутствующим сыновьям соответствует число 0. Аналогичным образом значение root=0 соответствует пустому дереву.

Для хранения дерева используется лишь часть массива; для тех i, которые свободны (не являются номерами вершин), значения val[i] безразличны. Нам будет удобно, чтобы все свободные числа были "связаны в список": первое хранится в специальной переменной free:0..n, а следующее за i свободное число хранится в left[i], так что свободны числа$${free, left[free], left[left[free]],...}$$ Для последнего свободного числа i значение left[i] равно 0. Равенство free=0 означает, что свободных чисел больше нет.

Замечание.Мы использовали для связывания свободных вершин массив left, но, конечно, с тем же успехом можно было использовать массив right.

Вместо значения 0 (обозначающего отсутствие вершины) можно было бы воспользоваться любым другим числом вне 1..n. Чтобы подчеркнуть это, будем вместо 0 использовать константу null=0.

14.1.2. Составить программу, определяющую, содержится ли элемент t:T в упорядоченном дереве (хранимом так, как только что описано).

Решение.

if root = null then begin
| ..не принадлежит
end else begin
| x := root;
| {инвариант: остается проверить наличие t в непустом
|   поддереве с корнем x}
| while ((t < val [x]) and (left [x] <> null)) or
| |     ((t > val [x]) and (right [x] <> null)) do begin
| | if t < val [x] then begin {left [x] <> null}
| | | x := left [x];
| | end else begin {t > val [x], right [x] <> null}
| | | x := right [x];
| | end;
| end;
| {либо t = val [x], либо t отсутствует в дереве}
| ..ответ = (t = val [x])
end;

14.1.3. Упростить решение, используя следующий трюк. Расширим область определения массива val, добавив ячейку с номером null и положим val[null]=t.

Решение.

val [null] := t;
x := root;
while t <> val [x] do begin
| if t < val [x] then begin
| | x := left [x];
| end else begin
| | x := right [x];
| end;
end;
..ответ: (x <> null).

14.1.4. Составить программу добавления элемента t в множество, представленное упорядоченным деревом (если элемент t уже есть, ничего делать не надо).

Решение. Определим процедуру get_free (var i:integer), дающую свободное (не являющееся номером) число i и соответствующим образом корректирующую список свободных чисел.

procedure get_free (var i: integer);
begin
| {free <> null}
| i := free;
| free := left [free];
end;

С ее использованием программа приобретает такой вид:

if root = null then begin
| get_free (root);
| left [root] := null; right [root] := null;
| val [root] := t;
end else begin
| x := root;
| {инвариант: осталось добавить t к непустому поддереву с
|  корнем в x}
| while ((t < val [x]) and (left [x] <> null)) or
| |     ((t > val [x]) and (right [x] <> null)) do begin
| | if t < val [x] then begin
| | | x := left [x];
| | end else begin {t > val [x]}
| | | x := right [x];
| | end;
| end;
| if t <> val [x] then begin {t нет в дереве}
| | get_free (i);
| | left [i] := null; right [i] := null;
| | val [i] := t;
| | if t < val [x] then begin
| | | left [x] := i;
| | end else begin {t > val [x]}
| | | right [x] := i;
| | end;
| end;
end;

14.1.5. Составить программу удаления элемента t из множества, представленного упорядоченным деревом (если его там нет, ничего делать не надо).

Решение.

if root = null then begin
| {дерево пусто, ничего делать не надо}
end else begin
| x := root;
| {осталось удалить t из поддерева с корнем в x; поскольку
|  это может потребовать изменений в отце x, введем
|  переменные  father: 1..n и direction: (l, r);
|  поддерживаем такой инвариант: если x не корень, то father
|  - его отец, а direction равно l или r в зависимости от
|  того, левым или правым сыном является x}
| while ((t < val [x]) and (left [x] <> null)) or
| |     ((t > val [x]) and (right [x] <> null)) do begin
| | if t < val [x] then begin
| | | father := x; direction := l;
| | | x := left [x];
| | end else begin {t > val [x]}
| | | father := x; direction := r;
| | | x := right [x];
| | end;
| end;
| {t = val [x] или t нет в дереве}
| if t = val [x] then begin
| | ..удаление вершины x с отцом father и
| |   направлением direction
| end;
end;

Удаление вершины использует процедуру

procedure make_free (i: integer);
begin
| left [i] := free;
| free := i;
end;

Она включает число i в список свободных. При удалении различаются 4 случая в зависимости от наличия или отсутствия сыновей у удаляемой вершины.

if (left [x] = null) and (right [x] = null) then begin
| {x - лист, т.е. не имеет сыновей}
| make_free (x);
| if x = root then begin
| | root := null;
| end else if direction = l then begin
| | left [father] := null;
| end else begin {direction = r}
| | right [father] := null;
| end;
end else if (left[x]=null) and (right[x] <> null) then begin
| {x удаляется, а right [x] занимает место x}
| make_free (x);
| if x = root then begin
| | root := right [x];
| end else if direction = l then begin
| | left [father] := right [x];
| end else begin {direction = r}
| | right [father] := right [x];
| end;
end else if (left[x] <> null) and (right[x]=null) then begin
| ..симметрично
end else begin {left [x] <> null, right [x] <> null}
| ..удалить вершину с двумя сыновьями
end;

Удаление вершины с двумя сыновьями нельзя сделать просто так, но ее можно предварительно поменять с вершиной, пометка на которой является непосредственно следующим (в порядке возрастания) элементом за пометкой на x.

y := right [x];
father := x; direction := r;
{теперь father и direction относятся к вершине y}
while left [y] <> null do begin
| father := y; direction := l;
| y := left [y];
end;
{val [y] - минимальная из пометок, больших val [x],
 y не имеет левого сына}
val [x] := val [y];
..удалить вершину y (как удалять вершину, у которой нет
  левого сына, мы уже знаем)

14.1.6. Упростить программу удаления, заметив, что некоторые случаи (например, первые два из четырех) можно объединить.

14.1.7. Использовать упорядоченные деревья для представления функций, область определения которых - конечные множества значений типа T, а значения имеют некоторый тип U. Операции: вычисление значения на данном аргументе, изменение значения на данном аргументе, доопределение функции на данном аргументе, исключение элемента из области определения функции.

Решение. Делаем как раньше, добавив еще один массив

func\_val: array [1..n] of U;

если val[x] = t, func\_val[x] = u, то значение хранимой функции на t равно u.

14.1.8. Предположим, что необходимо уметь также отыскивать k -ый элемент множества (в порядке возрастания), причем количество действий должно быть не более $$C\cdot(\text{высота дерева})$$. Какую дополнительную информацию надо хранить в вершинах дерева?

Решение. В каждой вершине будем хранить число всех ее потомков. Добавление и исключение вершины требует коррекции лишь на пути от корня к этой вершине. В процессе поиска k -ой вершины поддерживается такой инвариант: искомая вершина является s -ой вершиной поддерева с корнем в x (здесь s и x - переменные).

Оценка количества действий

Для каждой из операций (проверки, добавления и исключения) количество действий не превосходит $$C\cdot(\text{высота дерева})$$. Для "ровно подстриженного" дерева (когда все листья на одной высоте) высота по порядку величины равна логарифму числа вершин. Однако для кривобокого дерева все может быть гораздо хуже: в наихудшем случае все вершины образуют цепь и высота равна числу вершин. Так случится, если элементы множества добавляются в возрастающем или убывающем порядке. Можно доказать, однако, что при добавлении элементов "в случайном порядке" средняя высота дерева будет не больше $$C\log(\text{число вершин})$$. Если этой оценки "в среднем" мало, необходимы дополнительные действия по поддержанию "сбалансированности" дерева. Об этом смотри в следующем пункте.

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

Дерево называется сбалансированным (или АВЛ-деревом в честь изобретателей этого метода Г.М. Адельсона-Вельского и E.М. Ландиса), если для любой его вершины высоты левого и правого поддеревьев этой вершины отличаются не более чем на $$1$$. (В частности, когда одного из сыновей нет, другой - если он есть - обязан быть листом.)

14.2.1. Найти минимальное и максимальное возможное количество вершин в сбалансированном дереве высоты $$n$$.

Решение. Максимальное число вершин равно $$2^n-1$$. Если $$m_n$$ - минимальное число вершин, то, как легко видеть, $$m_{n + 2} = 1 + m_n + m_{n+1}$$, откуда $$m_n =\Phi_{n+2} - 1$$ ( $$\Phi_n$$ - $$n$$ -ое число Фибоначчи, $$\Phi_1=1$$, $$\Phi_2=1$$, $$\Phi_{n+2} = \Phi_n +\Phi_{n+1}$$ ).

14.2.2. Доказать, что сбалансированное дерево с $$n$$ вершинами имеет высоту не больше $$C \log n$$ для некоторой константы $$C$$, не зависящей от $$n$$.

Решение. Индукцией по $$n$$ легко доказать, что $$\Phi_{n+2}\ge a^n$$, где $$a$$ - больший корень квадратного уравнения $$a^2=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$$. Соответствующее преобразование будем называть большим правым вращением. (Аналогично определяется симметричное ему большое левое вращение.)

14.2.3. Дано дерево, сбалансированное всюду, кроме корня, в котором разница высот равна $$2$$ (т.е. левое и правое поддеревья корня сбалансированы и их высоты отличаются на $$2$$ ). Доказать, что оно может быть превращено в сбалансированное одним из четырех описанных преобразований, причем высота его останется прежней или уменьшится на $$1$$.

Решение. Пусть более низким является, например, левое поддерево, и его высота равна $$k$$. Тогда высота правого поддерева равна $$k+2$$. Обозначим корень через $$a$$, а его правого сына (он обязательно есть) через $$b$$. Рассмотрим левое и правое поддеревья вершины $$b$$. Одно из них обязательно имеет высоту $$k+1$$, а другое может иметь высоту $$k$$ или $$k+1$$ (меньше $$k$$ быть не может, так как поддеревья сбалансированы). Если высота левого поддерева равна $$k+1$$, а правого - $$k$$, то потребуется большое правое вращение; в остальных случаях помогает малое. Вот как выглядят три случая балансировки дерева:

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

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

Лемма. Если в сбалансированном дереве $$X$$ одно из его поддеревьев $$Y$$ заменили на сбалансированное дерево $$Z$$, причем высота $$Z$$ отличается от высоты $$Y$$ не более чем на $$1$$, то полученное такой "прививкой" дерево можно превратить в сбалансированное вращениями (причем количество вращений не превосходит высоты, на которой делается прививка).

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

Доказательство леммы. Индукция по высоте, на которой делается прививка. Если она происходит в корне (заменяется все дерево целиком), то все очевидно ("привой" сбалансирован по условию). Пусть заменяется некоторое поддерево, например, левое поддерево некоторой вершины $$x$$. Возможны два случая.

После прививки сбалансированность в вершине $$x$$ не нарушилась (хотя, возможно, нарушилась сбалансированность в предках $$x$$: высота поддерева с корнем в $$x$$ могла измениться). Тогда можно сослаться на предположение индукции, считая, что мы прививали целиком поддерево с корнем в $$x$$.

Сбалансированность в $$x$$ нарушилась. При этом разница высот равна $$2$$ (больше она быть не может, так как высота $$Z$$ отличается от высоты $$Y$$ не более чем на $$1$$ ). Разберем два варианта.

Выше правое (не заменявшееся) поддерево вершины $$x$$. Пусть высота левого (т.е. $$Z$$ ) равна $$k$$, правого - $$k+2$$. Высота старого левого поддерева вершины $$x$$ (т.е. $$Y$$ была равна $$k+1$$. Поддерево с корнем $$x$$ имело в исходном дереве высоту $$k+3$$, и эта высота не изменилась после прививки.

По предыдущей задаче вращение преобразует поддерево с корнем в $$x$$ в сбалансированное поддерево высоты $$k+2$$ или $$k+3$$. То есть высота поддерева с корнем $$x$$ - в сравнении сего прежней высотой - не изменилась или уменьшилась на $$1$$, и мы можем воспользоваться предположением индукции.

Выше левое поддерево вершины $$x$$. Пусть высота левого (т.е. $$Z$$ ) равна $$k+2$$, правого - $$k$$. Высота старого левого поддерева (т.е. $$Y$$ ) была равна $$k+1$$. Поддерево с корнем $$x$$ в исходном дереве $$X$$ имело высоту $$k+2$$, после прививки она стала равна $$k+3$$. После подходящего вращения (см.предыдущую задачу) поддерево с корнем в $$x$$ станет сбалансированным, его высота будет равна $$k+2$$ или $$k+3$$, так что изменение высоты по сравнению с высотой поддерева с корнем $$x$$ в дереве $$X$$ не превосходит $$1$$ и можно сослаться на предположение индукции.

14.2.5. Составить программы добавления и удаления элементов, сохраняющие сбалансированность. Число действий не должно превосходить $$C\cdot(\text{высота дерева})$$. Разрешается хранить в вершинах дерева дополнительную информацию, необходимую при балансировке.

Решение. Будем хранить для каждой вершины разницу между высотой ее правого и левого поддеревьев:$$\begin{align*} {diff [i]} = \text{(высота правого поддерева вершины {i})} -{}\\ \qquad -\text{(высота левого поддерева вершины {i}).} \end{align*}$$ Нам потребуются четыре процедуры, соответствующие большим и малым правым и левым вращениями. Но вначале два замечания. (1) Нам нужно, чтобы при вращении поддерева номер его корня не менялся. (В противном случае потребовалось бы корректировать информацию в отце корня, что нежелательно.) Этого можно достичь, так как номера вершин дерева можно выбирать независимо от их значений. (На картинках номер указан сбоку от вершины, а значение - внутри.)

(2) После преобразований мы должны также изменить соответственно значения в массиве diff. Для этого достаточно знать высоты деревьев $$P, Q,\ldots$$ с точностью до константы, поэтому можно предполагать, что одна из высот равна нулю.

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

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]; {,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;

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

Процедуры добавления и удаления элементов пишутся как раньше, но только добавление и удаление должно сопровождаться коррекцией массива diff и восстановлением сбалансированности.

При этом используется процедура с такими свойствами:

дано: левое и правое поддеревья вершины с номером a сбалансированы, в самой вершине разница высот не больше 2, в поддереве с корнем a массив diff заполнен правильно;

надо: поддерево с корнем a сбалансировано и массив diff соответственно изменен, d - изменение его высоты (равно 0 или -1); в остальной части все осталось как было - в частности, значения diff

procedure balance (a: integer; var d: integer);
begin {-2 <= diff[a] <= 2}
| if diff [a] = 2 then begin
| | b := right [a];
| | if diff [b] = -1 then begin
| | | BR (a); d := -1;
| | end else if diff [b] = 0 then begin
| | | SR (a); d := 0;
| | end else begin {diff [b] = 1}
| | | SR (a); d := - 1;
| | end;
| end else if diff [a] = -2 then begin
| | b := left [a];
| | if diff [b] = 1 then begin
| | | BL (a); d := -1;
| | end else if diff [b] = 0 then begin
| | | SL (a); d := 0;
| | end else begin {diff [b] = -1}
| | | SL (a); d := - 1;
| | end;
| end else begin {-2 < diff [a] < 2, ничего делать не надо}
| | d := 0;
| end;
end;

Восстановление сбалансированности требует движения от листьев к корню, поэтому будем хранить в стеке путь от корня к рассматриваемой в данный момент вершине. Элементами стека будут пары $$\langle$$ вершина, направление движения из нее $$\rangle$$, т.е. значения типа

record
| vert: 1..n; {вершина}
| direction : (l, r); {l - левое, r - правое}
end;

Программа добавления элемента t теперь выглядит так:

if root = null then begin
| get_free (root);
| left[root] := null; right[root] := null; diff[root] := 0;
| val[root] := t;
end else begin
| x := root; ..сделать стек пустым
| {инвариант: осталось добавить t к непустому поддереву с
|  корнем в x; стек содержит путь к x}
| while ((t < val [x]) and (left [x] <> null)) or
| |     ((t > val [x]) and (right [x] <> null)) do begin
| | if t < val [x] then begin
| | | ..добавить в стек пару <x, l>
| | | x := left [x];
| | end else begin {t > val [x]}
| | | ..добавить в стек пару <x, r>
| | | x := right [x];
| | end;
| end;
| if t <> val [x] then begin {t нет в дереве}
| | get_free (i); val [i] := t;
| | left [i] := null; right [i] := null; diff [i] := 0;
| | if t < val [x] then begin
| | | ..добавить в стек пару <x, l>
| | | left [x] := i;
| | end else begin {t > val [x]}
| | | ..добавить в стек пару <x, r>
| | | right [x] := i;
| | end;
| | d := 1;
| | {инвариант: стек содержит путь к изменившемуся
| |  поддереву, высота  которого увеличилась по
| |  сравнению с высотой в исходном дереве
| |  на d (=0 или 1); это поддерево  сбалансировано;
| |  значения diff для его вершин правильны; в
| |  остальном дереве  все  осталось  как  было -
| |  в частности, значения diff}
| | while (d <> 0) and ..стек непуст do begin {d = 1}
| | | ..взять из стека пару в <v, direct>
| | | if direct = l then begin
| | | | if diff [v] = 1 then begin
| | | | | c := 0;
| | | | end else begin
| | | | | c := 1;
| | | | end;
| | | | diff [v] := diff [v] - 1;
| | | end else begin
| | | {direct = r}
| | | | if diff [v] = -1 then begin
| | | | | c := 0;
| | | | end else begin
| | | | | c := 1;
| | | | end;
| | | | diff [v] := diff [v] + 1;
| | | end;
| | | {c = изменение высоты поддерева с корнем в v по
| | |  сравнению с исходным деревом; массив diff
| | |  содержит правильные значения для этого поддерева;
| | |  возможно нарушение сбалансированности в v}
| | | balance (v, d1); d := c + d1;
| | end;
| end;
end;

Легко проверить, что значение d может быть равно только 0 или 1 (но не -1 ): если c=0, то diff[v]=0 и балансировка не производится.

Программа удаления строится аналогично. Ее основной фрагмент таков:

{инвариант: стек содержит путь к изменившемуся поддереву,
 высота которого изменилась по сравнению с высотой в
 исходном дереве на d (=0 или -1); это поддерево
 сбалансировано; значения diff для его вершин правильны;
 в остальном дереве все осталось как было -
 в частности, значения diff}
while (d <> 0) and ..стек непуст do begin
| {d = -1}
| ..взять из стека пару в <v, direct>
| if direct = l then begin
| | if diff [v] = -1 then begin
| | | c := -1;
| | end else begin
| | | c := 0;
| | end;
| | diff [v] := diff [v] + 1;
| end else begin {direct = r}
| | if diff [v] = 1 then begin
| | | c := -1;
| | end else begin
| | | c := 0;
| | end;
| | diff [v] := diff [v] - 1;
| end;
| {c = изменение высоты поддерева с корнем в v по
|  сравнению с исходным деревом; массив diff содержит
|  правильные значения для этого поддерева;
|  возможно нарушение сбалансированности в v}
| balance (v, d1);
| d := c + d1;
end;

Легко проверить, что значение d может быть равно только 0 или -1 (но не -2 ): если c=-1, то diff[v]=0 и балансировка не производится.

Отметим также, что наличие стека делает излишними переменные father и direction (их роль теперь играет вершина стека).

14.2.6. Доказать, что при добавлении элемента

(а) второй из трех случаев балансировки (см.рисунок к задаче 14.2.3.) невозможен;

(б) полная балансировка требует не более одного вращения (после чего все дерево становится сбалансированным), в то время как при удалении элемента может понадобиться много вращений.

Замечание. Мы старались записать программы добавления и удаления так, чтобы они были как можно более похожими друг на друга. Используя специфику каждой из них, можно многое упростить.

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

До сих пор каждая вершина содержала один элемент хранимого множества. Этот элемент служил границей между левым и правым поддеревом. Будем теперь хранить в вершине $$k\ge1$$ элементов множества (число $$k$$ может меняться от вершины к вершине, а также при добавлении и удалении новых элементов, см.далее). Эти $$k$$ элементов служат разделителями для $$k+1$$ поддерева. Пусть фиксировано некоторое число $$t\ge1$$. Будем рассматривать деревья, обладающие такими свойствами:

Добавление элемента происходит так. Если лист, в который он попадает, неполон (т.е. содержит менее $$2t$$ элементов), то нет проблем. Если он полон, то $$2t+1$$ элемент (все элементы листа и новый элемент) разбиваем на два листа по $$t$$ элементов и разделяющий их серединный элемент. Этот серединный элемент надо добавить в вершину предыдущего уровня. Это возможно, если в ней менее $$2t$$ элементов. Если и она полна, то ее разбивают на две, выделяют серединный элемент и т.д. Если в конце концов мы захотим добавить элемент в корень, а он окажется полным, то корень расщепляется на две вершины, а высота дерева увеличивается на $$1$$.

Удаление элемента, находящегося не в листе, сводится к удалению непосредственно следующего за ним, который находится в листе. Поэтому достаточно научиться удалять элемент из листа. Если лист при этом становится слишком маленьким, то его можно пополнить за счет соседнего листа - если только и он не имеет минимально возможный размер $$t$$. Если же оба листа имеют размер $$t$$, то на них вместе $$2t$$ элементов, вместе с разделителем - $$2t+1$$. После удаления одного элемента остается $$2t$$ элементов - как раз на один лист. Если при этом вершина предыдущего уровня становится меньше нормы, процесс повторяется и т.д.

14.2.7. Реализовать описанную схему хранения множеств, убедившись, что она также позволяет обойтись $$C \log n$$ действий для операций включения, исключения и проверки принадлежности.

14.2.8. Можно определять сбалансированность дерева иначе: требовать, чтобы для каждой вершины ее левое и правое поддеревья имели не слишком сильно отличающиеся количества вершин. (Преимущество такого определения состоит в том, что при вращениях не нарушается сбалансированность в вершинах, находящихся ниже точки вращения.) Реализовать на основе этой идеи способ хранения множеств, гарантирующий оценку в $$C \log n$$ действий для включения, удаления и проверки принадлежности.

Указание. Он также использует большие и малые вращения. Подробности см.в книге Рейнгольда, Нивергельта и Део "Комбинаторные алгоритмы".