90
правок
Изменения
→Устройство HAT
HAT состоит из главного массива указателей <tex>top</tex> и ряда листьев <tex>leaf</tex> (так же одномерные массивы), в которых хранятся элементы.
Возможное число указателей в главном массиве и возможное число элементов в каждом листе равны между собой и являются степенями двойки.
===Добавление элементовПолучение элемента по номеру===
Благодаря использованию степеней двойки, мы можем эффективно находить элементы в HAT, используя поразрядные операции.
topIndex(j)
// Вернуть элемент HAT. Нет проверки на выход за пределы массива.
return top[topIndex(j)][leafIndex(j)];
===Добавление элементов===
[[Файл:AlgoF2.gif|400px|left]]
Чаще всего при добавлении элемента в одном из листьев (последнем незаполненном на данный момент) найдется свободное место, что позволит осуществить быструю вставку(<math>O(1)</math>).
