四叉樹

四元樹又稱四叉樹是一種樹狀數據結構，在每一個節點上會有四個子區塊。四元樹常套用於二維空間數據的分析與分類。 它將數據區分成為四個象限。數據範圍可以是方形或矩形或其他任意形狀。

這種數據結構是由 拉斐爾·芬科爾(Raphael Finkel) 與 J. L. Bentley 在1974年發展出來 。

基本介紹

• 中文名：四叉樹
• 外文名：quad-tree
• 性質：數據結構
• 特點：每個節點最多有四個子樹

概述

四叉樹（quad-tree）是一種數據結構，是一種每個節點最多有四個子樹的數據結構。

四叉樹是在二維圖片中定位像素的唯一適合的算法。因為二維空間（圖經常被描述的方式）中，平面像素可以重複的被分為四部分，樹的深度由圖片、計算機記憶體和圖形的複雜度決定。

四叉樹可以用來在資料庫中放置和定位檔案（稱作記錄或鍵）。這一算法通過不停的把要查找的記錄分成4部分來進行匹配查找直到僅剩下一條記錄為止。

特點

• 可分解成為各自的區塊
• 每個區塊都有節點容量。當節點達到最大容量時，節點分裂
• 樹狀數據結構依造四元樹法加以區分

形態

四元樹可以用他們數據形態的表示法來作分類，數據形態的項目有：區域、點、直線及曲線。四元樹也可以進行分類，不管樹的形態是否獨立於已處理過的排秩數據。一些四元樹的形態如下所示：

四元樹區塊

四元樹區塊表示為空間的分區，即在二維上分區塊為四組相同的象限、次象限等，且每個葉節點包含有關特殊次區塊的數據。樹里的每個節點不是正好有4個子節點，就是沒有子節點(為一個樹葉節點)。四元樹區塊不是嚴格的一顆'樹' - 且位置的次分區與數據無關。他們是比較精確一些稱為'單詞查找樹'.

在一個深度為n的四元樹區塊中可以用來表示一個視頻包含有2× 2的像素，每個像素的值為0或1。根節點表示全部視頻區塊。假如像素在任何區塊不是全部為0或1，那就可以進行畫分。在這個套用中，每個葉節點代表一個段落的像素、段落像素裡面包含全部為零或全部為一的組合。

四元樹區塊也可以用為一種數據區塊上不同變化解析的表達法。比如，溫度在一個區塊中可以存儲為一個四元樹，而樹葉節點存儲著平均溫度涵蓋到它所擁有的次區塊。

假如四元樹區塊被用來表達一組點數據(諸如一組城市的經緯度)，區塊就進行次分區直到每個葉節點包含最多一個單點。

點四元樹

點四元樹修改自二叉樹用來表示二維的點數據。點四元樹與四元樹都有共同的特點，不過於次分區的中心總是在一點時、點四元樹視為一真樹(true tree)。樹的形態根據編過序的數據而定。在比較二維規律數據點上是相當有效率的，經常運作在O(log n)的時間複雜度內。

點四元樹的節點結構

點四元樹的節點類似於二叉樹的節點，它們之間的主要差別在於點四元樹有4個指針(每一個象限一個指針)、而一般二叉樹只有2個指針(左指針及右指針)。點四元樹的鍵值也是經常被分解為兩部分，如在直角坐標上的 x 及 y 值。因此，一個節點包含下列信息：

• 4個指針(Pointer)：quad[‘NW’](西北)、quad[‘NE’](東北)、quad[‘SW’](西南)、及quad[‘SE’](東南)。
• 點；含有如下項目：
• 鍵值；通常以直角作標(x, y)值來表示。
• 值；比如是"名字"。

邊四元樹

邊四元樹是專門用來存儲直線而不是點。曲線能分區每格到很接近精細的解析度。如此能產生極度的不平衡樹，而此不平衡樹可能推翻索引的使用目的。

種類

1.點四叉樹（Point Quadtree）

點四叉樹與KD樹相似，兩者的差別是在點四叉樹中，空間被分割成四個矩形。四個不同的多邊形分別是：SW、NW、SE、NE。其搜尋過程和KD樹相似，當一個點包含在搜尋範圍內時被記錄下來，當一個子樹和搜尋範圍有交疊時它將被穿過。

2.PR四叉樹(Point Region Quadtree)

PR四叉樹是點四叉樹的一個變種，它不使用數據集中的點來分割空間。在PR四叉樹中，每次分割空間時，都是將一個正方形分成四個相等的子正方形，依次進行，直到每個正方形的內容不超過所給定的桶量（比如一個對象）為止。

3.MX四叉樹

空間被分割成四個矩形。四個不同的多邊形分別是：SW、NW、SE、NE。每次分割空間時，都是將一個正方形分成四個相等的子正方形，依次進行，直到每個正方形的內容不超過所給定的桶量（比如一個對象）為止。

所有的數據都處在四叉樹的同一個深度，多個點可以由一個指針聯接。

4.基於固定格線劃分的四叉樹索引

在四叉樹中，空間要素標識記錄在其外包絡矩形所覆蓋的每一個葉結點中，但是，當同一父親的四個兄弟結點都要記錄該空間要素標識時，則只將該空間要素標識記錄在該父親結點上，並按這一規則向上層推進。

5.線性可排序四叉樹索引

首先將四叉樹分解為二叉樹，即在父結點層與子結點層之間插入一層虛結點，虛結點不用來記錄空間要素，然後按照中序遍歷樹的順序對結點進行編碼，包括加入的虛結點。

套用

• 圖像表示法
• 空間索引(Spatial index)。
• 在二維的有效率之碰撞偵測(collision detection)。
• 地形數據的隱藏面決定(Hidden surface determination)。
• 存儲分散數據，諸如電子表格(spreadsheet)、或著一些矩陣計算的格式化信息。
• 多維場的解法。(計算流體力學,電磁學)
• 生命遊戲模擬程式。