前言

作為程序員，應(yīng)該都對(duì)二叉樹(shù)都不陌生，我們都知道二叉樹(shù)的變體二叉查找樹(shù)，非常適合用來(lái)進(jìn)行對(duì)一維數(shù)列的存儲(chǔ)和查找，可以達(dá)到 O(logn) 的效率；我們?cè)谟枚娌檎覙?shù)進(jìn)行插入數(shù)據(jù)時(shí)，根據(jù)一個(gè)數(shù)據(jù)的值和樹(shù)結(jié)點(diǎn)值的對(duì)比，選擇二叉樹(shù)的兩個(gè)叉之一向下，直到葉子結(jié)點(diǎn)，查找時(shí)使用二分法也可以迅速找到需要的數(shù)據(jù)。

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

四叉樹(shù)

介紹

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

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

聰明的小伙伴一定想到了適合存儲(chǔ)和查詢?nèi)S數(shù)據(jù)的八叉樹(shù)，它們?cè)硎且恢碌?，不過(guò)我們暫不討論。

分類

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

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

根據(jù)其結(jié)構(gòu)，四叉樹(shù)分為滿四叉樹(shù)和非滿四叉樹(shù)。

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

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

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

在查詢時(shí)，只有找到了位置對(duì)應(yīng)的結(jié)點(diǎn)，那么結(jié)點(diǎn)下的所有點(diǎn)都會(huì)是此位置的附近點(diǎn)，更小的“容量”意味著每個(gè)結(jié)點(diǎn)內(nèi)點(diǎn)越少，也就意味著查詢的精度會(huì)越高。

代碼實(shí)現(xiàn)

首先是數(shù)據(jù)結(jié)構(gòu)的定義：

樹(shù)結(jié)點(diǎn)：

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

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

四叉樹(shù)位置點(diǎn)的插入流程如下圖所示：

結(jié)點(diǎn)的分裂是重點(diǎn)，這里介紹一下：

void splitNode(struct QuadTreeNode *node) {
    // 獲取xy方向上的中間點(diǎn)，用來(lái)初始化子結(jié)點(diǎn)的范圍
    double mid_vertical = (node->region.up + node->region.bottom) / 2;
    double mid_horizontal = (node->region.left + node->region.right) / 2;

    node->is_leaf = 0; // 將是否為葉子結(jié)點(diǎn)置為否
    // 填充四個(gè)子結(jié)點(diǎn)
    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);

    // 遍歷結(jié)點(diǎn)下的位置點(diǎn)，將其插入到子結(jié)點(diǎn)中
    for (int i = 0; i < node->ele_num; i++) {
        insertEle(node, *node->ele_list[i]);
        free(node->ele_list[i]);
        node->ele_num--;
    }
}

問(wèn)題和優(yōu)化

邊界點(diǎn)問(wèn)題

四叉樹(shù)還是面臨著邊界點(diǎn)問(wèn)題，每個(gè)結(jié)點(diǎn)內(nèi)的點(diǎn)必然是相鄰的，但相鄰的點(diǎn)越不一定在同一個(gè)結(jié)點(diǎn)內(nèi)，如下圖，A點(diǎn)和B點(diǎn)相鄰的很近，如果A點(diǎn)是我們查找的目標(biāo)點(diǎn)，那么僅僅取出A點(diǎn)所在結(jié)點(diǎn)內(nèi)的所有位置點(diǎn)是不夠的，我們還需要查找它的周邊結(jié)點(diǎn)。

這里我們要介紹四叉樹(shù)的另一個(gè)特性。

字典樹(shù)

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

我們可以類比字典的特性：我們?cè)谧值淅锿ㄟ^(guò)拼音查找晃(huang)這個(gè)字的時(shí)候，我們會(huì)發(fā)現(xiàn)它的附近都是讀音為huang的，可能是聲調(diào)有區(qū)別，再往前翻，我們會(huì)看到讀音前綴為huan的字，再往前，是讀音前綴為hua的字... 取它們的讀音前綴分別為 h qu hua huan huang。我們?cè)诓檎視r(shí)，根據(jù) abc...xyz 的順序找到h前綴的部分，再根據(jù) ha he hu 找到 hu 前綴的部分...最后找到 huang，我們會(huì)發(fā)現(xiàn)，越往后其讀音前綴越長(zhǎng)，查找也越精確，這種類似于字典的樹(shù)結(jié)構(gòu)就是字典樹(shù)，也是前綴樹(shù)。

四叉樹(shù)也有此特性，我們給每一個(gè)子結(jié)點(diǎn)都編號(hào)，那么每個(gè)子結(jié)點(diǎn)會(huì)繼承父結(jié)點(diǎn)的編號(hào)為前綴，并在此基礎(chǔ)上有相對(duì)其兄弟結(jié)點(diǎn)的獨(dú)特編號(hào)。

與 GeoHash 的相似之處

如果我們給右上、左上、左下、右下四個(gè)子結(jié)點(diǎn)分別編號(hào)為00 01 10 11，那么生成的四叉樹(shù)就會(huì)像：

我們?cè)诓檎业侥繕?biāo)結(jié)點(diǎn)時(shí)，根據(jù)其編碼獲取到其周邊八個(gè)結(jié)點(diǎn)的編碼，再獲取各個(gè)周邊結(jié)點(diǎn)內(nèi)的位置點(diǎn)。

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

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

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

小結(jié)

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

不過(guò)這么高的效率是因?yàn)檫@些都是內(nèi)存操作，真正的數(shù)據(jù)庫(kù)中數(shù)據(jù)肯定是要落地的，那時(shí)候更多的就是些磁盤和 IO 操作了，效率也會(huì)有所下降，但最終的效率和結(jié)點(diǎn)數(shù)據(jù)的擴(kuò)展能力，與 GeoHash 相比，還是四叉樹(shù)更好一些。

以上就是詳解C語(yǔ)言實(shí)現(xiàn)空間索引四叉樹(shù)的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言實(shí)現(xiàn)空間索引四叉樹(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論