詳解C語言實現(xiàn)空間索引四叉樹

更新時間：2021年05月26日 10:46:38 作者：枕邊書

本文主要介紹了用C語言實現(xiàn)四叉樹，對算法感興趣的同學，可以參考下，并且試驗一下。

前言

作為程序員，應該都對二叉樹都不陌生，我們都知道二叉樹的變體二叉查找樹，非常適合用來進行對一維數(shù)列的存儲和查找，可以達到 O(logn) 的效率；我們在用二叉查找樹進行插入數(shù)據(jù)時，根據(jù)一個數(shù)據(jù)的值和樹結點值的對比，選擇二叉樹的兩個叉之一向下，直到葉子結點，查找時使用二分法也可以迅速找到需要的數(shù)據(jù)。

但二叉樹只支持一維數(shù)據(jù)，如一個標量數(shù)值，對地圖上的位置點這種有xy兩個方向上的信息卻無能為力，那么是否有一種樹能夠支持二維數(shù)據(jù)的快速查詢呢？

四叉樹

介紹

四元樹又稱四叉樹是一種樹狀數(shù)據(jù)結構，在每一個節(jié)點上會有四個子區(qū)塊。四元樹常應用于二維空間數(shù)據(jù)的分析與分類。它將數(shù)據(jù)區(qū)分成為四個象限。

今天要介紹的四叉樹可以認為是二叉查找樹的高維變體，它適合對有二維屬性的數(shù)據(jù)進行存儲和查詢，當然四叉樹存儲的也不一定是二維數(shù)據(jù)，而是有著二維屬性的數(shù)據(jù)，如有著 x,y 信息的點，用它還可以用來存儲線和面數(shù)據(jù)。它有四個叉，在數(shù)據(jù)插入時，我們通過其二維屬性（一般是 x,y）選擇四個叉之一繼續(xù)向下，直至葉子結點，同樣使用“四分法”來迅速查找數(shù)據(jù)。四叉樹的一般圖形結構如下：

聰明的小伙伴一定想到了適合存儲和查詢三維數(shù)據(jù)的八叉樹，它們原理是一致的，不過我們暫不討論。

分類

四叉樹常見的應用有圖像處理、空間數(shù)據(jù)索引、2D中的快速碰撞檢測、稀疏數(shù)據(jù)等，今天我們很純粹地只介紹它在空間索引方面的應用。

根據(jù)其存儲內容，四叉樹可以分為點四叉樹、邊四叉樹和塊四叉樹，今天我們實現(xiàn)的是點四叉樹。

根據(jù)其結構，四叉樹分為滿四叉樹和非滿四叉樹。

對于滿四叉樹，每個節(jié)點都有四個子結點，它有著固定的深度，數(shù)據(jù)全都存在最底層的子結點中，進行數(shù)據(jù)插入時不需要分裂。

滿四叉樹在確定好深度后，進行插入操作很快，可是如果用它來存儲下圖所示數(shù)據(jù)，我們會發(fā)現(xiàn)，四叉樹的好多叉都是空的，當然它們會造成內存空間的大量浪費。

非滿四叉樹解決了此問題，它為每個結點添加一個“容量”的屬性，在四叉樹初始化時只有一個根結點，在插入數(shù)據(jù)時，如果一個結點內的數(shù)據(jù)量大于了結點“容量”，再將結點進行分裂。如此，可以保證每個結點內都存儲著數(shù)據(jù)，避免了內存空間的浪費。

在查詢時，只有找到了位置對應的結點，那么結點下的所有點都會是此位置的附近點，更小的“容量”意味著每個結點內點越少，也就意味著查詢的精度會越高。

代碼實現(xiàn)

首先是數(shù)據(jù)結構的定義：

樹結點：

struct QuadTreeNode {
    int depth; // 結點深度
    int is_leaf; // 是否是葉子結點
    struct Region region; // 區(qū)域范圍
    struct QuadTreeNode *LU; // 左上子結點指針
    struct QuadTreeNode *LB; // 左下子結點指針
    struct QuadTreeNode *RU; // 右上子結點指針
    struct QuadTreeNode *RB; // 右下子結點指針
    int ele_num; // 位置點數(shù)
    struct ElePoint *ele_list[MAX_ELE_NUM]; // 位置點列表
};

為了加快插入和查詢速度，數(shù)據(jù)結構設計稍微冗余了一些；

四叉樹位置點的插入流程如下圖所示：

結點的分裂是重點，這里介紹一下：

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--;
    }
}

問題和優(yōu)化

邊界點問題

四叉樹還是面臨著邊界點問題，每個結點內的點必然是相鄰的，但相鄰的點越不一定在同一個結點內，如下圖，A點和B點相鄰的很近，如果A點是我們查找的目標點，那么僅僅取出A點所在結點內的所有位置點是不夠的，我們還需要查找它的周邊結點。

這里我們要介紹四叉樹的另一個特性。

字典樹

字典樹，又稱前綴樹或trie樹，是一種有序樹，用于保存關聯(lián)數(shù)組，其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節(jié)點中，而是由節(jié)點在樹中的位置決定。一個節(jié)點的所有子孫都有相同的前綴，也就是這個節(jié)點對應的字符串，而根節(jié)點對應空字符串。

我們可以類比字典的特性：我們在字典里通過拼音查找晃(huang)這個字的時候，我們會發(fā)現(xiàn)它的附近都是讀音為huang的，可能是聲調有區(qū)別，再往前翻，我們會看到讀音前綴為huan的字，再往前，是讀音前綴為hua的字... 取它們的讀音前綴分別為 h qu hua huan huang。我們在查找時，根據(jù) abc...xyz 的順序找到h前綴的部分，再根據(jù) ha he hu 找到 hu 前綴的部分...最后找到 huang，我們會發(fā)現(xiàn)，越往后其讀音前綴越長，查找也越精確，這種類似于字典的樹結構就是字典樹，也是前綴樹。

四叉樹也有此特性，我們給每一個子結點都編號，那么每個子結點會繼承父結點的編號為前綴，并在此基礎上有相對其兄弟結點的獨特編號。

與 GeoHash 的相似之處

如果我們給右上、左上、左下、右下四個子結點分別編號為00 01 10 11，那么生成的四叉樹就會像：

我們在查找到目標結點時，根據(jù)其編碼獲取到其周邊八個結點的編碼，再獲取各個周邊結點內的位置點。

嗯，這種通過編碼來確定周邊格子的方式確實跟 GeoHash 是相同的，但不要混淆了他們查找原理上的截然不同：

GeoHash 本質上是通過格子編碼將二維信息用一維來表示，其查找原理從根本上來說是二叉樹（B樹），在查找時會根據(jù)格子編碼選擇兩個方向之一繼續(xù)精確，查詢效率準確來說是 log2N;
四叉樹保留了其二維查找的特性，其查找會根據(jù)其 x,y 選擇四個方向之一繼續(xù)查找，忽略方向選擇時的計算，其查詢效率應該是 log4N;

我們可以使用此方法來繼續(xù)優(yōu)化四叉樹，給結點添加一個“編號”屬性即可，由于時(bo)間(zhu)關(fan)系(lan)，這里不再實現(xiàn)了。

小結

由于 C 語言的高效率，由它實現(xiàn)的四叉樹效率極高。進行十萬數(shù)據(jù)的插入和一次查詢總操作為 7毫秒。在數(shù)據(jù)量更大的插入時，因為要進行結點的多次分裂，效率會有所下降，進行了8百萬數(shù)據(jù)的測試插入需要兩分鐘多一些（16年的 mac pro），至于查詢，都是一些內存尋址操作，時間可以忽略不計了。更大量級的測試就不跑了，跑的時候散熱風扇速轉系統(tǒng)溫度迅速上升

不過這么高的效率是因為這些都是內存操作，真正的數(shù)據(jù)庫中數(shù)據(jù)肯定是要落地的，那時候更多的就是些磁盤和 IO 操作了，效率也會有所下降，但最終的效率和結點數(shù)據(jù)的擴展能力，與 GeoHash 相比，還是四叉樹更好一些。

以上就是詳解C語言實現(xiàn)空間索引四叉樹的詳細內容，更多關于C語言實現(xiàn)空間索引四叉樹的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: