Изменения

Затраты дополнительной памяти (уже выделенной, но еще не используемой) в самом плохом случае {{---}} <math>(top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})</math> (этот случай при пустой HAT {{---}} в <tex>top</tex> один указатель на единственный пустой лист). Если в листе будет <tex>power/2</tex> элементов, то ожидаемая трата дополнительной памяти уменьшается до <math>(top + leaf/2) \approx 1.5\sqrt{N}</math>, а это все еще . Таким образом HAT использует <mathtex>O\Theta(\sqrt{N})</mathtex>дополнительной памяти. Сравним с другими структурамиЭто лучше [[wikipedia:ru:Динамический массив |динамического массива]], добавляющими элементы за который использует <mathtex>O(1N)</mathtex>дополнительней памяти сразу после перекопирования элементов. Например, отдельно связанные списки требуют O(N) дополнительной памяти И лучше [[wikipedia:ru:Список (один указатель для каждого элементаинформатика)|списка]].