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)
Свойства, которые мне требуются в структуре данных:
- Быстрая вставка в уже отсортированные данные (предпочтительно log n)
- Произвольный доступ
- Сортировка x и y отдельно, без потери свойства пары
Изначально я думал об использовании простого 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 структура данных.Я думаю, что реализация этого в деревьях усложнит это.Есть ли комбинация структуры данных, которая может достичь этого?Я пишу это на Python (если это может помочь)