資料結構中的點四叉樹

點四叉樹是二叉樹的一種變體，用於表示二維點資料。所有四叉樹的特徵都為點四叉樹所共享。

它在比較二維有序資料點方面通常非常高效，通常在 O(log n) 時間內執行。出於完整性考慮，點四叉樹值得一提，但 k-d 樹作為廣義二分搜尋的工具勝過它們。

點四叉樹的構建方式如下。

給定要插入的下一個點，我們計算它所在的單元格並將其新增到樹中。

新點被新增，使得包含它的單元格被穿過該點的垂直線和水平線分成四個象限。因此，單元格是矩形的，但不一定是正方形的。

在這些樹中，每個節點都包含一個輸入點。

由於平面的劃分是由點插入的順序決定的，因此樹的高度對插入順序敏感並依賴於插入順序。以不正確的順序插入會導致樹的高度與輸入點的數量呈線性關係（此時它變成了連結串列）。

如果點集是靜態的，則可以執行預處理以構建高度平衡的樹。

點四叉樹的節點結構

點四叉樹的節點與二叉樹的節點相同，主要區別在於它與四個指標相關聯（每個指標用於每個象限），而不是像普通二叉樹那樣只有兩個（“左”和“右”）。此外，鍵通常被分成兩部分，分別指代 x 和 y 座標。

因此，一個節點包含以下資訊

  • 四個指標：分別是 quad[‘NW’]、quad[‘NE’]、quad[‘SW’] 和 quad[‘SE’]
  • NW-西北，NE-東北，SW-西南，SE-東南
  • 點；依次包含
  • 鍵；通常表示為 x、y 座標
  • 值；例如名稱

更新於: 2020年1月8日

1K+ 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告