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