用于在已排序数据中快速插入和随机访问的数据结构

Question

p = random_point(a,b)
#random_point() returns a tuple/named-tuple (x,y)
#0<x<a 0<y<b
if centers.validates(p):
    centers.insert(p)
#centers is the data structure to store points

在centers数据结构中,所有x和y坐标都存储在两个单独的排序(升序)列表中,一个用于x,另一个用于y.每个节点都x指向相应的y,反之亦然,这样它们可以单独排序并仍保持对属性:centers.get_x_of(y)和centers.get_y_of(x)

我在数据结构中需要的属性:

1. 快速插入,已经排序的数据(最好是log n)
2. 随机访问
3. 分别对x和y排序,而不会丢失对属性

最初我想过使用simple Lists,并使用Binary search来获取插入任何新元素的索引.但我发现,使用像AVL或B树这样的自平衡树可以改善它.我可以让每两个树木x和y,与具有额外的指针,可以从X-树节点为y树节点指向每个节点.

但我不知道如何在这些树中构建随机访问功能.该函数centers.validate()尝试插入x&y,并对相邻元素运行一些检查,这需要随机访问:

def validate(p):
    indices = get_index(p)
    #returns a named tuple of indices to insert x and y, Eg: (3,7)
    condition1 =  func(x_list[indices.x-1], p.x) and func(x_list[indices.x+1], p.x)
    condition2 =  func(y_list[indices.y-1], p.y) and func(y_list[indices.y+1], p.y)
    #func is some mathematical condition on neighboring elements of x and y
    return condition1 and condition2

在上面的函数中,我需要访问x&y data结构的相邻元素.我认为在树中实现这一点会使它复杂化.是否有任何数据结构组合可以实现这一目标？我用Python写这个(如果这可以帮助)

Answer 1

具有 2 个字典的类，其中保存值，键是另一个字典的键，该字典包含与该字典中的值相关的值。它需要为每个字典维护一个当前顺序的列表，以便在调用它时调用该字典的元素（该字典值的当前排序）。您将需要二进制或其他有效的排序来对每个字典进行操作以进行插入，尽管它实际上会使用该字典的顺序列表来查找每个中点键，然后检查该键的值。