本文通過C語言的四叉樹執行個體，介紹了四叉樹的實作過程（主要是插入和查詢），另外介紹了四叉樹的邊界點問題及解決方案，并将四叉樹和GeoHash在實作空間索引的原理上做了對比。
前言
作為程式員，應該都對二叉樹都不陌生，我們都知道二叉樹的變體二叉查找樹，非常适合用來進行對一維數列的存儲和查找，可以達到 O(logn) 的效率；我們在用二叉查找樹進行插入資料時，根據一個資料的值和樹結點值的對比，選擇二叉樹的兩個叉之一向下，直到葉子結點，查找時使用二分法也可以迅速找到需要的資料。
但二叉樹隻支援一維資料，如一個标量數值，對地圖上的位置點這種有xy兩個方向上的資訊卻無能為力，那麼是否有一種樹能夠支援二維資料的快速查詢呢？
四叉樹
介紹
四元樹又稱四叉樹是一種樹狀資料結構，在每一個節點上會有四個子區塊。四元樹常應用于二維空間資料的分析與分類。它将資料區分成為四個象限。
今天要介紹的四叉樹可以認為是二叉查找樹的高維變體，它适合對有二維屬性的資料進行存儲和查詢，當然四叉樹存儲的也不一定是二維資料，而是有着二維屬性的資料，如有着 x,y 資訊的點，用它還可以用來存儲線和面資料。它有四個
叉
，在資料插入時，我們通過其二維屬性（一般是 x,y）選擇四個叉之一繼續向下，直至葉子結點，同樣使用“四分法”來迅速查找資料。四叉樹的一般圖形結構如下：
聰明的小夥伴一定想到了适合存儲和查詢三維資料的八叉樹，它們原理是一緻的，不過我們暫不讨論。
分類
四叉樹常見的應用有圖像處理、空間資料索引、2D中的快速碰撞檢測、稀疏資料等，今天我們很純粹地隻介紹它在空間索引方面的應用。
根據其存儲内容，四叉樹可以分為點四叉樹、邊四叉樹和塊四叉樹，今天我們實作的是點四叉樹。
根據其結構，四叉樹分為滿四叉樹和非滿四叉樹。
對于滿四叉樹，每個節點都有四個子結點，它有着固定的深度，資料全都存在最底層的子結點中，進行資料插入時不需要分裂。
滿四叉樹在确定好深度後，進行插入操作很快，可是如果用它來存儲下圖所示資料，我們會發現，四叉樹的好多叉都是空的，當然它們會造成記憶體空間的大量浪費。
非滿四叉樹解決了此問題，它為每個結點添加一個“容量”的屬性，在四叉樹初始化時隻有一個根結點，在插入資料時，如果一個結點内的資料量大于了結點“容量”，再将結點進行分裂。如此，可以保證每個結點内都存儲着資料，避免了記憶體空間的浪費。
在查詢時，隻有找到了位置對應的結點，那麼結點下的所有點都會是此位置的附近點，更小的“容量”意味着每個結點内點越少，也就意味着查詢的精度會越高。
以下是一個非滿點四叉樹的實作：
附上 GitHub 倉庫位址：枕邊書-空間索引
代碼實作
首先是資料結構的定義：
樹結點：
struct QuadTreeNode {
int depth; // 結點深度
int is_leaf; // 是否是葉子結點
struct Region region; // 區域範圍
struct QuadTreeNode *LU; // 左上子結點指針
struct QuadTreeNode *LB; // 左下子結點指針
struct QuadTreeNode *RU; // 右上子結點指針
struct QuadTreeNode *RB; // 右下子結點指針
int ele_num; // 位置點數
struct ElePoint *ele_list[MAX_ELE_NUM]; // 位置點清單
}; 為了加快插入和查詢速度，資料結構設計稍微備援了一些；
四叉樹位置點的插入流程如下圖所示：
結點的分裂是重點，這裡介紹一下：
void splitNode(struct QuadTreeNode *node) {
// 擷取xy方向上的中間點，用來初始化子結點的範圍
double mid_vertical = (node->region.up + node->region.bottom) / 2;
double mid_horizontal = (node->region.left + node->region.right) / 2;
node->is_leaf = 0; // 将是否為葉子結點置為否
// 填充四個子結點
node->RU = createChildNode(node, mid_vertical, node->region.up, mid_horizontal, node->region.right);
node->LU = createChildNode(node, mid_vertical, node->region.up, node->region.left, mid_horizontal);
node->RB = createChildNode(node, node->region.bottom, mid_vertical, mid_horizontal, node->region.right);
node->LB = createChildNode(node, node->region.bottom, mid_vertical, node->region.left, mid_horizontal);
// 周遊結點下的位置點，将其插入到子結點中
for (int i = 0; i < node->ele_num; i++) {
insertEle(node, *node->ele_list[i]);
free(node->ele_list[i]);
node->ele_num--;
}
} 更具體的代碼見 GitHub 吧，我覺得我代碼品質還看得過去，另外方法上面還有詳細些的注釋。
問題和優化
邊界點問題
四叉樹還是面臨着邊界點問題，每個結點内的點必然是相鄰的，但相鄰的點越不一定在同一個結點内，如下圖，A點和B點相鄰的很近，如果A點是我們查找的目标點，那麼僅僅取出A點所在結點内的所有位置點是不夠的，我們還需要查找它的周邊結點。
這裡我們要介紹四叉樹的另一個特性。
字典樹
字典樹，又稱字首樹或trie樹，是一種有序樹，用于儲存關聯數組，其中的鍵通常是字元串。與二叉查找樹不同，鍵不是直接儲存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的字首，也就是這個節點對應的字元串，而根節點對應空字元串。
我們可以類比字典的特性：我們在字典裡通過拼音查找
晃(huang)
這個字的時候，我們會發現它的附近都是讀音為
huang
的，可能是聲調有差別，再往前翻，我們會看到讀音字首為
huan
的字，再往前，是讀音字首為
hua
的字... 取它們的讀音字首分别為
h qu hua huan huang
。我們在查找時，根據 abc...xyz 的順序找到h字首的部分，再根據 ha he hu 找到 hu 字首的部分...最後找到 huang，我們會發現，越往後其讀音字首越長，查找也越精确，這種類似于字典的樹結構就是字典樹，也是字首樹。
四叉樹也有此特性，我們給每一個子結點都編号，那麼每個子結點會繼承父結點的編号為字首，并在此基礎上有相對其兄弟結點的獨特編号。
與 GeoHash 的相似之處
如果我們給右上、左上、左下、右下四個子結點分别編号為
00 01 10 11
，那麼生成的四叉樹就會像：
我們在查找到目标結點時，根據其編碼擷取到其周邊八個結點的編碼，再擷取各個周邊結點内的位置點。
看過我上一篇空間索引（詳見：空間索引 - GeoHash算法及其實作優化）文章的小夥伴可能會說，這不就是 GeoHash 麼？
嗯，這種通過編碼來确定周邊格子的方式确實跟 GeoHash 是相同的，但不要混淆了他們查找原理上的截然不同：
- GeoHash 本質上是通過格子編碼将二維資訊用一維來表示，其查找原理從根本上來說是二叉樹（B樹），在查找時會根據格子編碼選擇兩個方向之一繼續精确，查詢效率準确來說是
log2N
- 四叉樹保留了其二維查找的特性，其查找會根據其 x,y 選擇四個方向之一繼續查找，忽略方向選擇時的計算，其查詢效率應該是
log4N
我們可以使用此方法來繼續優化四叉樹，給結點添加一個“編号”屬性即可，由于時(bo)間(zhu)關(fan)系(lan)，這裡不再實作了。
小結
由于 C 語言的高效率，由它實作的四叉樹效率極高。 進行十萬資料的插入和一次查詢總操作為 7毫秒。在資料量更大的插入時，因為要進行結點的多次分裂，效率會有所下降，進行了8百萬資料的測試插入需要兩分鐘多一些（16年的 mac pro），至于查詢，都是一些記憶體尋址操作，時間可以忽略不計了。 更大量級的測試就不跑了，跑的時候散熱風扇速轉系統溫度迅速上升。。。
不過這麼高的效率是因為這些都是記憶體操作，真正的資料庫中資料肯定是要落地的，那時候更多的就是些磁盤和 IO 操作了，效率也會有所下降，但最終的效率和結點資料的擴充能力，與 GeoHash 相比，還是四叉樹更好一些。
最後，部分圖檔來源于網絡，侵删。
如果您覺得本文對您有幫助，可以點選下面的 推薦 支援一下我。部落格一直在更新，歡迎 關注 。