Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Асимптотика времени его работы будет все так же O(log(log(U))), она оценивается аналогично предыдущей версии функции insert. Необходимо лишь заметить, что если мы выполним вставку в aux, то следующий за ним insert будет работать за O(1), так как это поддерево будет пустым.
if T.children[high(x)].is_empty():
insert(T.aux, high(x))
if T.is_empty():
T.min = T.max = x
high(x) = x >> (k / 2)
low(x) = x & (~(1 << (k / 2)))
shl eax, 1
shl eax, 8
Дерево ван Эмде Боаса