90
правок
Изменения
→Получение элемента по номеру
Благодаря использованию степеней двойки, мы можем эффективно находить элементы в HAT, используя поразрядные операции.
topIndex(j)
<font color=green>// Получить номер указателя в основном массиве</font> '''return ''' j >> power;
leafIndex(j)
<font color=green>// Получить номер листа</font> '''return ''' j & ((1<<power)-1);
getHat(j)
<font color=green>// Вернуть элемент HAT. Нет проверки на выход за пределы массива.</font> '''return ''' top[topIndex(j)][leafIndex(j)];[[Файл:fullHAT.png|200px|left]]Рассмотрим как происходит вычисление адреса на примере. Пусть у нас есть HAT с 3-мя используемыми листьями, тогда для нашего случая <tex>power = 3</tex>. Получим значения функций для элемент под номером <tex>5</tex>: *<tex>topIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен опреации деления(взятию по модулю) <tex>j</tex> на <math>2^{3}</math>. То есть получим <tex>1</tex> {{---}} действительно элемент под номером <tex>5</tex> находится в первом листе(нумерация листов с <tex>0</tex>).*<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>).
===Добавление элементов===
[[Файл:AlgoF2.gif|400px|left]]
