论文标题
懒惰的搜索树
Lazy Search Trees
论文作者
论文摘要
我们介绍了懒惰的搜索树数据结构。懒惰搜索树是指针机上基于比较的数据结构，该数据结构支持基于订单的操作，例如等级，选择，成员，前身，后继，最小值和最大值，同时提供动态操作插入，删除，更改，键，拆分和合并。我们根据当前元素的分区分析数据结构的性能，以基于等级的一组间隙$ \ {δ_i\} $。查询会陷入特定的差距，并将差距分为两个与查询操作相关的等级$ r $的新差距。如果我们定义$ b = \ sum_i |δ_i| \ log_2（n/|δ_i|）$，我们对$ n $插入顺序的性能和$ q $ distient的查询为$ o（b + \ min（n \ log \ log \ log \ log n，n \ log q））$。我们显示$ b $是一个下限。 有效地，我们将二进制搜索树的插入时间从$θ（\ log n）$减少到$ o（\ min（\ log（n/|δ_i|） + \ log \ log \ log \ log |δ_i|，\ \ log q））$，其中$Δ_i$是插入元素掉落的空白。在$ n $插入和$ q $ queries的序列上，$ o（n \ log q + q \ log n）$保持的时间限制；当查询分布不均匀时，可以更好地界限。作为一个不均匀性的极端情况，如果所有查询都是针对最小元素的，则懒搜索树以$ o（\ log \ log \ log n）$ time Insert和降低 - 键操作作为优先队列。相同的数据结构支持任何等级的查询，在二进制搜索树之间插值和有效的优先级队列。 可以实现懒惰的搜索树以主要在数组上操作，仅需要$ o（\ min（q，n））$ pointers。通过直接减少，我们的数据结构还支持散布树的有效访问定理，当访问数量较大时，都为非均匀元素访问提供了强大的数据结构。
We introduce the lazy search tree data structure. The lazy search tree is a comparison-based data structure on the pointer machine that supports order-based operations such as rank, select, membership, predecessor, successor, minimum, and maximum while providing dynamic operations insert, delete, change-key, split, and merge. We analyze the performance of our data structure based on a partition of current elements into a set of gaps $\{Δ_i\}$ based on rank. A query falls into a particular gap and splits the gap into two new gaps at a rank $r$ associated with the query operation. If we define $B = \sum_i |Δ_i| \log_2(n/|Δ_i|)$, our performance over a sequence of $n$ insertions and $q$ distinct queries is $O(B + \min(n \log \log n, n \log q))$. We show $B$ is a lower bound. Effectively, we reduce the insertion time of binary search trees from $Θ(\log n)$ to $O(\min(\log(n/|Δ_i|) + \log \log |Δ_i|, \; \log q))$, where $Δ_i$ is the gap in which the inserted element falls. Over a sequence of $n$ insertions and $q$ queries, a time bound of $O(n \log q + q \log n)$ holds; better bounds are possible when queries are non-uniformly distributed. As an extreme case of non-uniformity, if all queries are for the minimum element, the lazy search tree performs as a priority queue with $O(\log \log n)$ time insert and decrease-key operations. The same data structure supports queries for any rank, interpolating between binary search trees and efficient priority queues. Lazy search trees can be implemented to operate mostly on arrays, requiring only $O(\min(q, n))$ pointers. Via direct reduction, our data structure also supports the efficient access theorems of the splay tree, providing a powerful data structure for non-uniform element access, both when the number of accesses is small and large.
