Изменения

Особенностью этой структуры является то, что все операции выполняются за <tex>O(\log k)</tex>, что асимптотически лучше, чем <tex>O(\log n)</tex> в большинстве других деревьев поиска, где <tex>n</tex> {{---}} количество элементов в дереве.

Пусть есть множество <tex>m[0 \dots M-1]</tex> мы хотим записать эти данный в дерево.

[[Файл:Boas.jpg.jpg|right|380px|thumb|корень дерева]]

В вспомогательном дереве хранится информация о том, какие клетки уже заняты. То есть значение <tex>i</tex> хранится в вспомогательном дереве только если занят элемент с индексом <tex>i</tex> в массиве детей.

Рассмотрим две опeрации

Insert(x)

Delete(T, x)

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

</pre>

Удаление из дерева T также делится на несколько подзадач:

*Если T.min = T.max = x, значит в дереве один элемент, мы его удалим и как-нибудь пометим, что дерево пусто(на будущее).

(с)wikipedia.org

</pre>