四叉樹

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

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

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

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

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

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

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

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

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

點四元樹的節點類似於二叉樹的節點，它們之間的主要差別在於點四元樹有4個指針(每一個象限一個指針)、而一般二叉樹只有2個指針(左指針及右指針)。點四元樹的鍵值也是經常被分解為兩部分，如在直角座標上的 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.線性可排序四叉樹索引

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