Изменения

*другим серьезным недостатком является количество занимаемой памяти. Дерево, хранящее <tex> k </tex>-битные числа, занимает <tex> O\Theta(2^k) </tex> памяти, что несложно доказывается индукцией, учитывая, что <tex> S(2^k)=(2^{k/2} + 1) \cdot S(2^{k/2}) + O(2^{k/2})</tex>, где <tex> S(2^i) </tex> {{---}} количество памяти, занимаемое деревом, в котором хранятся <tex> i </tex>-битные числа. Впрочем, можно попытаться частично избежать огромного расхода памяти, создавая необходимые поддеревья «лениво», то есть только тогда, когда они нам потребуются. Это делает дерево достаточно компактным, если оно содержит много элементов, потому что новые поддеревья поддерево не создаются создатся пока что-то не будет добавлено к нему. Первоначально каждый добавленный элемент, создает <tex> O(\log k)</tex> новых деревьев, содержащих около <tex>k/2</tex> элементов всего. По мере роста дерева, все больше и больше поддеревьев используются повторно, особенно крупные. В среднем это даёт заметное снижение потребления, памяти, например для для <tex>k = 16</tex> массив из <tex>4000</tex> элементов будет занимать примерно в 16 раз меньше памяти. В полном дереве из <tex>2^k</tex> элементов, используется только <tex> O(2^k)</tex> памяти. Кроме того, в отличие от двоичного дерева поиска, большинство из этой памяти используется для хранения данных.