Поиск преемника, предшественника быстрее, чем BST

Question

Я ищу структуру данных со следующими свойствами: Список целых чисел (таких, что x> 1 и x < U, где U - большое целое число).

Может выполнять: predecessor(x), successor(x), insert(x), delete(x).

Это может быть реализовано двоичным деревом поиска, и все операции будут выполняться O (log n). Ну, по словам моего профессора, это может быть реализовано с successor и предшественником в O (log log U) time и insert и delete в O (log U).

Для этого требуется массив размера U и двоичное дерево поиска. Кто-нибудь знает, что это за алгоритм?

Answer 1

Заканчивать Y-Fast Trie и X-Fast Trie

Я считаю, что это то, что вы ищете.

От Википедия:

Y-Fast Trie:

В информатике, у-быстро Trie представляет собой структуру данных для хранения целых чисел от ограниченного>> области. Он поддерживает точные и предшествующие или последующие запросы во времени O (log log M), используя O (n)> пространство, где n - это количество сохраненных значений, а M - максимальное значение в домене.

X-Fast Trie:

В информатике, х-быстро Trie представляет собой структуру данных для хранения целых чисел из ограниченного> области. Он поддерживает точные и предшественники или последующие запросы во времени O (log log M), используя O (n> log M), где n - это количество сохраненных значений, а M - максимальное значение в домене.