问一个QuadTree neighbor grid的问题

grokking the system design interview里yelp/uber题用了quadtree，在做query的时候，因为最邻近的location/car并不一定都落在最user location相同的grid里，一个user query需要同时query临近的几个grid。
当grid是被动态分化的时候，相邻grid的邻居就会变多或变少。grokkings里说用doubly linked list把叶节点连起来，可是一个大的grid，上下左右可能都会有好几个邻居呀，这到底是怎么实现的...楼主唯一想到的相似的解决方法就是每个叶节点存一个list of neighbors...


原文：
How will we find neighboring grids of a given grid?

Since only leaf nodes contain a list of locations, we can connect all leaf nodes with a doubly linked list. This way we can iterate forward or backward among the neighboring leaf nodes to find out our desired locations. We can keep a pointer in each node to access its parent, and since each parent node has pointers to all of its children, we can easily find siblings of a node. We can keep expanding our search for neighboring grids by going up through the parent pointers.

Once we have nearby LocationIDs, we can query the backend database to find details about those places.

一个grid很明显应该有四个邻居，⬆️⬇️⬅️➡️

如果需要考虑对角的话，那么总共有八个邻居。↖️↗️↙️↘️

如果有四个doubly linked lists，那么可以轻松的以K为半径找到所有的邻居grid。然后再在每个grid里进行单独搜索。

因为有些grid是大一些的，具体实现的时候还有些变更。

14417335 发表于 2019-7-3 22:55
一个grid很明显应该有四个邻居，⬆️⬇️⬅️➡️

如 ...

初始状态确实一个grid有8个neighbor，假如三横三纵9个grid，编码1，2，3，4，5，6，7，8，9，当第五个grid（正中间的那个）划分成4个的时候，他上下左右四个grid（2，4，6，8）就会分别多出一个neighbor呀，这时候用linkedlist不是就没有办法连接到多个新的小neighbor了么

HanBurger 发表于 2019-7-4 00:58
初始状态确实一个grid有8个neighbor，假如三横三纵9个grid，编码1，2，3，4，5，6，7，8，9，当第五个gri ...

是的。需要bfs来找k为半径的所有邻居（的邻居的邻居。。。）的grid