403
правки
Изменения
→insert
== insert ==
Операция вставки элемента <tex>x</tex> состоит из трех частей нескольких частей:
*обновление полей если дерево пусто, то присвоим полям <tex>min</tex> и <tex>max</tex> значение <tex>x</tex>. Делать что-то еще бессмысленно, так как информация записанная в <tex>min</tex> и <tex>max</tex> полностью описывает состояние текущего дерева.*иначе:**обновим поля <tex>min</tex> и <tex>max</tex> текущего дерева, если это требуется*вставка *вставим во вспомогательное дерево <tex>aux</tex> числа число <tex>high(x)</tex>, если соответствующее поддерево <tex>children[high(x)]</tex> до этого было пусто*вставка числа *вставим число <tex>low(x)</tex> в поддерево <tex>children[high(x)]</tex>, за исключением ситуации, когда текущее дерево {{---}} это 1-дерево, и дальнейшая вставка не требуется
<pre>
insert(T, x)
if empty(T) // проверка на пустоту текущего дерева
T.min = x;
T.max = x;
else if T.min > x T.min = x; // релаксация минимума if T.max < x T.max = x; // релаксация максимума if T.k != 1 if empty(T.children[high(x)]) insert(T.aux, high(x)); // вставка high(x) во вспомогательно дерево aux insert(T.children[high(x)], low(x)); // вставка low(x) в поддерево children[high(x)]
</pre>
Нетрудно увидеть, что данная операция работает за время <tex>O(\log k)</tex>. На каждом уровне дерева мы выполняем <tex>O(1)</tex> операций. После этого возможны 2 случая: поддерево <tex>children[high(x)]</tex> пусто, и мы будем производить дальнейшую вставку и в него, и во вспомогательное дерево <tex>aux</tex>, или же поддерево не пусто, и мы просто спустимся на уровень ниже. Но если поддерево <tex>children[high(x)]</tex> пусто, то вставка в него будет выполнена за <tex>O(1)</tex>, так как мы всего лишь обновим поля <tex>min</tex> и <tex>max</tex>. Все остальные операции будут выполнятся уже со вспомогательным деревом <tex>aux</tex>, высота которого на 1 уровень меньше, чем высота текущего. Если же поддерево <tex>children[high(x)]</tex> не пусто, то мы просто перейдем к вставке элемента в это поддерево, высота которого так же на 1 меньше, чем у текущего. В итоге, каждый раз, выполнив <tex>O(1)</tex> операций, мы переходим к дереву, высота которого на 1 меньше, чем у текущего. Следовательно, количество операций пропорционально высоте дерева, которая, как уже было показано, <tex>O(\log k)</tex>. То есть операция вставки займет <tex>O(\log k)</tex> времени.
== remove ==
