228
правок
Изменения
→Структура
==Структура==
Пусть есть множество <tex>m[0 .. M-1]</tex> мы хотим записать эти данный в дерево.
[[Файл:Boas.jpg.jpg|right|380px|thumb|корень дерева]]
Будем называть наше дерево <tex>T</tex>.
В корне(root) будут храниться:
*вспомогательный массив (T.aux)
Элемент массива из детей с индексом <tex>i=\lfloor x/M^{1/2}\rfloor</tex> является также деревом для множества <tex>[iMi<tex>sqrt{M^1/2 }</tex> .. (i+1)<tex>sqrt{M^1/2 }</tex> - 1]</tex>
В вспомогательном дереве хранится информация о том, какие клетки уже заняты. То есть значение <tex>i</tex> хранится в вспомогательном дереве только если занят элемент с индексом <tex>i</tex> в массиве детей.
