Применение бинарных поисковых деревьев для поиска соседей Мур

Question

Предполагая, что у меня есть большой набор координат, например us (3,4), (5,-6) и т. Д., Где x и y - целые числа; Можно ли заказать их, используя BST?

Как определить, что должно быть на левом против правом узле?

Причина, по которой я смотрю на BST вместо простого использования списка координат, заключается в том, что я могу более эффективно (по сравнению с линейным поиском) определять те координаты, которые будут в окрестности Мура (расстояние Чебышева 1) другой.

Я думал о чередовании сравнений со значениями x и y; это хороший подход?

Как еще я могу применить BST к этой ситуации? Или использование BST несостоятельно?

Answer 1

Несмотря на простоту подхода aioobe для создания сетки ячеек (двумерного массива), было немного тяжело / неэффективно хранить состояние всех возможных ячеек / координат, особенно когда у меня могут быть случаи, когда естьиметь только несколько фактических координат в очень большом пространстве (разреженный массив).

В конечном итоге я понял, что использование BST возможно (есть и другие подходы), и это то, что я сделал, чтобы найти соседей Мур эффективно, используясбалансированный BST:

1. навязать порядковое отношение к координатам, т. е. (x1, y1)> (x2, y2) => (x1> x2) ||(x1 == x2 && y1> y2)
2. Сортировать список координат по этому отношению (для создания сбалансированного дерева)
3. Рекурсивно сгенерировать BST из отсортированного списка: вставить медианный элемент как узел, срезсписок ниже и выше медианы и передачи в качестве параметра для рекурсивного вызова для генерации левого и правого поддеревьев

Затем, чтобы найти соседей Мура координаты, я могу затем просто посмотреть вверх / поискдля 8 возможных соседних координат в дереве (как предполагает aioobe) в O (log n).

Answer 2

Я предлагаю вам создать сетку ячеек.Каждая ячейка (которая на самом деле является списком) содержит все координаты, которые нравятся внутри нее.

Если вам нужно найти соседей по координате, вы просто смотрите на координаты, которые находятся в той же ячейке (или в соседних ячейках).).