403
правки
Изменения
→insert
Операция вставки элемента <tex>x</tex> состоит из нескольких частей:
*если дерево пусто, то присвоим полям или в нем содержится единственный элемент (<tex>min</tex> и = <tex>max</tex> значение ), то присвоим полям <tex>xmin</tex>и <tex>max</tex> соответствующие значения. Делать что-то еще бессмысленно, так как информация записанная в <tex>min</tex> и <tex>max</tex> полностью описывает состояние текущего дерева и удовлетворяет структуре нашего дерева.
*иначе:
**обновим поля если элемент <tex>minx</tex> и больше <tex>max</tex> или меньше <tex>min</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 > == T.max // проверка, что в дереве один элемент if T.min < x T.max = x; else T.min = x; else if T.min > x swap(T.min, x); // релаксация минимума if T.max < x swap(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>
