n-D樹 - 計算超立方體的座標

Question

我想實現一個通用的n維樹，它將保存n維數據。對於n維數據，我是指具有6-7座標的數據點。這裏是樹節點（複合數據類型）和樹類：

#data = data points (i.e. [x,y,z,k,m,n]) 
#hypercube = set of tuples; coordinates [(x0,x1),(y0,y1)...] 
class _Node: 
    def __init__(self, data, hypercube): 
     self.data = data 
     self.hypercube = hypercube 

class _nTree: 
    def __init__(self, hypercube, depth = 0): 
     self.node = [] 
     self.children = [] 
     self.depth = depth 
     self.hypercube = hypercube 

    def __insert__(self, data): 
     if not self.node: 
      self.node = _Node(data, self.hypercube) 
      if (len(self.node.data) != 1): 
       self.__split__() 

對我來說，每一個孩子將包含被包含在其父節點中的數據 - 這就是後面檢查，如果LEN的原因（自我.node.data）不等於1.如果我們只有一個數據點包含在超立方體中，那麼我們停止並且有一個葉節點。如果我們有多個，我們會進一步分裂。只有當數據點位於由超立方體的座標定義的邊界內時，數據點纔會放置在超立方體中。

例如，假設您有一個座標爲[（0,1），（0,1）]的二維平面 - 我們的根節點。我們想用數據點[（0.5,0.1），（0.2,0.3）]填充它。由於我們有兩個數據點，因此我們將該平面劃分爲2^n個新的超立方體（在這種情況下爲正方形），其中n是維數 - 在這種情況下爲2。從1×1的根部平方得到4個較小的座標[[（0,0.5），（0,0.5）]，[（0.5,1），（0.5,1）]，[（0.5,1）， 0,0.5）]，[（0,0.5），（0.5,1）] - 這基本上是根節點的孩子。這是一個可以在這裏可視化的四叉樹的例子：https://en.wikipedia.org/wiki/Quadtree

我想要做同樣的事情，但有多個維度。現在

，我試圖解釋什麼，我試圖做的，我的問題是：

超立方體變量包含當前節點的座標。我怎樣才能實現我的拆分功能，它會正確地生成座標？例如，如果我有6個維度，則必須爲每個節點生成64個座標（2^n; n =維度數）。作爲一個頭，它不是一棵K-D樹。

編輯：我想我應該張貼我目前的分裂功能：

def __split__(self): 
    n_of_children = 2**(len(self.node.hypercube[0])) 
    vector = self.__get_vector__() #returns the coordinates of all 64 hypercubes/trees 
    self.children = [_nTree(vector, self.depth+1) for i in range(n_of_children)[ 
    self.__insert_children__(self.data) 

我宣佈每一個孩子作爲一個樹狀結構，然後我打電話insert_children決定進入哪個孩子每個數據點進入。如果一個孩子有一個以上的數據點，我們重複整個分裂和插入的過程。

Answer 1

我曾經寫過Java中的K維四叉樹，這裏是代碼：

NodeKD(double[] min, double[] max, int maxDepth, NodeKD parent) { 
    this.min = min; 
    this.max = max; 
    this.center = new double[min.length]; 
    for (int i = 0; i < min.length; i++) { 
     this.center[i] = (max[i]+min[i])/2; 
    } 
    this.maxDepth = maxDepth == -1 ? 4 : maxDepth; 
    this.children = new ArrayList<>(); 
    qA = new NodeKD[1 << min.length]; 
    this.parent = parent; 
} 

private void subdivide() { 
    int dim = min.length; 
    double[] min = new double[dim]; 
    double[] max = new double[dim]; 
    for (int i = 0; i < qA.length; i++) { 
     long mask = 1L; 
     for (int j = 0; j < dim; j++) { 
      if ((j & mask) == 0) { 
       min[j] = this.min[j]; 
       max[j] = this.center[j]; 
      } else { 
       min[j] = this.center[j]; 
       max[j] = this.max[j]; 
      } 
      mask <<= 1; 
     } 
     qA[i] = new NodeKD(min, max, maxDepth-1, this); 
    } 
} 

然而，據我所知，四叉樹（2D）和八叉樹（3D）是不是很有效更高的尺寸。取決於你想做什麼（範圍查詢，最近鄰居查詢，簡單的查找，大量的插入......），我會選擇一個不同的結構。 KD-Trees非常簡單，可以插入/刪除。 R-Trees（R +樹，R *樹，X-tree）對於範圍查詢和最近鄰居查詢非常有用。然而，原來的R-Tree對於稍後修改添加/刪除數據是相當不利的。

我個人最喜歡的是我自己的PH-Tree。它類似於一個k維四叉樹，但有一些區別：

• 它實質上是一個'trie'，或者是critbit樹。這意味着只要一個值爲'0'而另一個值爲'1'，它就會查看分割值的位表示。由於我在比特級上進行操作，因此節點內的導航和尋址非常有效，因爲我可以簡單地使用k比特字符串（對於k維）來遍歷本地孩子，並檢查它們對查詢的適用性。這避免了具有高維度的可伸縮性帶來的許多問題。
• 它使用前綴共享來減少內存要求（每個節點僅存儲本地值彼此不同的位）。
• 由於靜態性質（根據比特分割），不會有任何修改影響兩個以上的節點，因此永遠不會需要重新平衡。
• 雖然沒有重新平衡，但樹的深度限制爲64（假設爲64位值），因此它不會嚴重退化。

一些更多的細節可以發現here和here。缺點是當前的open-source version僅在Java（不是python）中，而且非常複雜。我有一個相當大的改進版本（更簡單的代碼），但可能需要一段時間才能發佈。