Изменения
Нет описания правки
==Структура==Пусть есть множество <tex>m[0 .. M-1]</tex> мы хотим записать эти данный в дерево.В корне будут храниться: массив детей размером sqrt(M), значение текущего минимума и максимума в дерево, а также вспомогательный массив.Элемент массива из детей с индексом <tex>i=\lfloor x/M^{1/2}\rfloor</tex> является также деревом для элементов <tex>[i*M^1/2 .. (i+1)M^1/2 - 1]</tex>В вспомогательном дереве хранится информация о том какие клетки уже заняты. То есть значение о хранится в вспомогательном дереве только если занят элемент с индексом j в массиве детей.
Рассмотрим две опeрации
Insert(x)
Delete(x)
==Insert==
операция добавления(insert)пусть добавляем мы элемент <tex>x</tex>
Если дерево пусто, то меняем значения минимума и максимума на x;
Если x<T.min тогда мы кладем T.min в поддерево i соответствующее T.min и ставим T.min = x. Если поддерево[i] до этого было пусто то мы также добавляем i в вспомогательное дерево.
Аналогично если x>T.max.
Если T.min< x < T.max тогда кладем x в поддерево i соответствующее x и меняем вспомогательное дерево.
<pre>
Insert(T, x)
if (T.min > T.max) // T is empty
T.min = T.max = x;
return
if (T.min = T.max)
if (x < T.min)
T.min = x;
if (x > T.max)
T.max = x;
return
if (x < T.min)
swap(x, T.min)
if (x > T.max)
swap(x, T.max)
i = x/sqrt(M)
Insert(T.children[i], x % sqrt(M))
if (T.children[i].min = T.children[i].max)
Insert(T.aux, i)
</pre>
==Delete==
Если T.min = T.max = x, значит в дереве один элемент, мы его удалим и как-нибудь пометим, что дерево пусто(на будущее).
Если x = T.min,то мы должны найти следующий второй минимум удалить его из того места где он находится и поставить в T.min Второй минимум - это либо T.max, либо T.children[T.aux.min].min.
Аналогично для случая x = T.max
Если же x = T.min и x = T.max, то мы должны удалить x из поддерева i отвечающего x.
Важно, что Delete реализован рекурсивно от дерева в котором идет удаления.
Так же нельзя забывать, что если мы удаляем последнее вхождение x, то мы должны удалить i из вспомогательного дерева.
