Изменения

Операция добавления вставки элемента <tex>x</tex> - эта задача делится на несколько состоит из трех частей частей

*Если дерево пустообновление полей <tex>min</tex> и <tex>max</tex> текущего дерева, то меняем значения минимума и максимума на x;если это требуется*Если вставка во вспомогательное дерево <tex>aux</tex> числа <tex>high(x)<T.min тогда мы кладем T.min в поддерево i /tex>, если соответствующее T.min и ставим T.min = x. Если поддерево<tex>children[ihigh(x)] </tex> до этого было пусто то мы также добавляем i в вспомогательное дерево.Аналогично если x>T.max.*Если T.minвставка числа < tex>low(x )< T.max тогда кладем x /tex> в поддерево i соответствующее <tex>children[high(x )]</tex>, за исключением ситуации, когда текущее дерево {{---}} это 1-дерево, и меняем вспомогательное дерево.дальнейшая вставка не требуется

Insertinsert(T, x) if empty(T.min > T.max) // T is emptyпроверка на пустоту текущего дерева T.min = x; T.max = x; return if (T.min = T.max)> x if (x < T.min) T.min = x; // релаксация минимума if (x > T.max)< x T.max = x; return // релаксация максимума if (x < T.min)k != 1 swapif empty(x, T.min) if children[high(x > T.max)]) swap insert(aux, high(x, T.max) i = x); //sqrtвставка high(Mx)во вспомогательно дерево aux Insert insert(T.children[ihigh(x)], low(x % sqrt(M)) if ; // вставка low(T.x) в поддерево children[i].min = T.children[i].max) Inserthigh(T.aux, ix) (с)wikipedia.org]