algorithm - 比 BST 更快地找到继任者、前任

Question

我正在寻找具有以下属性的数据结构: 对于整数列表(例如 x > 1，且 x < U，其中 U 是一个大整数)。

它可以执行:predecessor(x), successor(x), insert(x), delete(x) 。

这可以用二叉搜索树来实现，所有操作都是 O(log n)。好吧，据我的教授说，这可以在 O(log log U) 时间内用 successor 和 predecessor 实现，在 O(log log U) 时间内用 insert 和 delete O(log U) 时间。

它需要一个大小为 U 的数组和一个二叉搜索树。谁知道这个算法是什么？

Answer 1

查看 Y-Fast Trie和 X-Fast Trie

我相信这些就是您要找的。

来自维基百科:

Y-快速特里:

In computer science, a y-fast trie is a data structure for storing integers from a bounded > > domain. It supports exact and predecessor or successor queries in time O(log log M), using O(n) > space, where n is the number of stored values and M is the maximum value in the domain.

极速特里:

In computer science, an x-fast trie is a data structure for storing integers from a bounded > domain. It supports exact and predecessor or successor queries in time O(log log M), using O(n > log M) space, where n is the number of stored values and M is the maximum value in the domain.