90
правок
Изменения
Нет описания правки
*<tex>leafIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен умножению <tex>1</tex> на <tex>2^{3}</tex>. Тоесть после вычитания <tex>1</tex> получим число формата <tex>011..11</tex>, в нашем случае {{---}} <tex>011</tex>.
*<tex>5_{10} = 101_2 - 101 \& 011 = 001</tex>, то есть индекс в листе равен <tex>1</tex> (в листах нумерация так же с <tex>0</tex>).
===Добавление элементов===
Реже мы столкнемся со случаем, когда необходимо создать новый лист. Достаточно всего лишь добавить указатель в свободную ячейку главного массива, что также позволит произвести вставку элемента за <math>O(1)</math>.
Самый интересный случай {{---}} когда главный массив и все листья заполнены. Cначала вычислим нужный размер (массивы <tex>top</tex> и <tex>leaf</tex> увеличиваются в 2 раза, то есть <math>power = power \cdot 2 </math>), затем скопируем элементы в новую структуру HAT, освобождая старые листья и распределяя новые листья(размер листа изменился, а значит количество элементов в листе и количество используемых листьев так же изменится).
Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивов переменной длины, потому что увеличения размеров всех массивов происходит редко (как будет видно ниже). Копировать элементы мы будем только тогда, когда главный массив полон(достигли соответствующей степени двойки). Например, для то есть <tex> N=4(2 \cdot 2)^k </tex>(, где <tex>k</tex> {{---}} натуральное число), тогда общая сумма перекопирования будет равна <math>1+4+16+64+256+...+N</math>. Воспользуемся тождеством: <math>(x^{n+1} -1)=(x-1)(1+x+x^2+x^3+... + x^k)</math>, тогда для нашего случая: <math>1 +4+4^2+4^3+...+4^k = (4^{k+1} -1)/(4-1) = (4N-1)/3</math>, или около <math>4N/3</math>. Это означает, что среднее число дополнительных операций копирования {{---}} <math>O(N)</math> для последовательного добавления N элементов, а не <math>O(N^2)</math>. Мы получили <math>4N/3</math> против <math>2N</math> в обычном динамическом массиве, то есть константа уменьшилась.
===Расход памяти===
Сравним с другими структурами, добавляющими элементы за <math>O(1)</math>. Например, отдельно связанные списки требуют O(N) дополнительной памяти (один указатель для каждого элемента).
Благодаря преимуществам, предоставляемыми HAT(так например вычисления адреса происходит приблизительно в 2 раза быстрее, чем в стандартном массиве C++), ее можно использовать в любых программах, требующих работу с массивами переменной длинны, где использование других структур данных (например списков) не удобно. На многих алгоритмах HAT работает значительно быстрее стандартных массивов, дополнительно можно ознакомиться с результатами некоторых тестов<ref>[http://pmg.org.ru/ai/tree_hash.htm Результаты тестов]</ref>.
== Примечания ==
