笛卡爾樹

某個數組，及其對應的笛卡爾樹

笛卡爾樹是一種特定的二叉樹數據結構，可由數列構造，在範圍最值查詢、範圍top k查詢（range top k queries）等問題上有廣泛應用。它具有堆的有序性，中序遍歷可以輸出原數列。笛卡爾樹結構由Vuillmin(1980)在解決範圍搜索的幾何數據結構問題時提出。從數列中構造一棵笛卡爾樹可以線性時間完成，需要採用基於棧的算法來找到在該數列中的所有最近小數。

定義

無相同元素的數列構造出的笛卡爾樹具有下列性質：

1. 結點一一對應於數列元素。即數列中的每個元素都對應於樹中某個唯一結點，樹結點也對應於數列中的某個唯一元素
2. 中序遍歷（in-order traverse）笛卡爾樹即可得到原數列。即任意樹結點的左子樹結點所對應的數列元素下標比該結點所對應元素的下標小，右子樹結點所對應數列元素下標比該結點所對應元素下標大。
3. 樹結構存在堆序性質，即任意樹結點所對應數值大／小於其左、右子樹內任意結點對應數值

根據堆序性質，笛卡爾樹根結點為數列中的最大／小值，樹本身也可以通過這一性質遞歸地定義：根結點為序列的最大／小值，左、右子樹則對應於左右兩個子序列，其結點同樣為兩個子序列的最大/小值。因此，上述三條性質唯一地定義了笛卡爾樹。若數列中存在重複值，則可用其它排序原則為數列中相同元素排定序列，例如以下標較小的數為較小，便能為含重複值的數列構造笛卡爾樹。

笛卡爾樹應用

範圍最值查詢與最低公共祖先

三邊範圍查詢問題

笛卡爾樹可以有效地處理範圍最值查詢（range minimum queries），通過將定義在數列上的RMQ問題轉化為定義在樹結構上的最低公共祖先（lowest common ancestor）問題。數列以線性時間構造出笛卡爾樹，笛卡爾樹則能以常數時間處理最低公共祖先查詢，因此在線性時間的預處理後，範圍最值查詢能以常數時間完成。

Bender & Farach-Colton (2000)則提出了RMQ與LCA問題的新聯繫，他們通過不基於樹的算法處理RMQ問題從而有效地解決LCA問題。其使用歐拉路徑的技巧將樹結構轉化為數列，此數列具有特定性質（相鄰數值代表樹中的相鄰頂點，即在樹中高度差為1的頂點），利用這一性質RMQ問題可以很高效地得到解決。通常的數列則不具備此性質，為了將一般的數列轉化為具有上述性質的數列，需要應用到笛卡爾樹，具體過程為在普通數列上構造笛卡爾樹，在笛卡爾樹上使用歐拉路徑轉化的方法將樹轉化為具有上述性質的新數列。

範圍最值查詢問題也可以解釋為二維範圍查詢問題，或者三邊範圍查詢問題（three sided range queries），笛卡爾平面上的有限點集可以用來構造笛卡爾樹，首先將這些點按照x取值排序，然後將y值作為數列中元素的值，以此數列建立笛卡爾樹。若 S 為有限點集中滿足 $L\leq x\leq R$條件的點集，設 p 是 S 中x值最小的點，q 是 S 中 x 值最大的點，則笛卡爾樹中 p 與 q的最低公共祖先即為該點集中處於該x值範圍內y值最高／低的點 b。三邊範圍查詢問題，即給定條件 $L\leq x\leq R,y\leq T$，取出所有滿足條件的點。其解決是以笛卡爾樹找到b 點，若b點的y 值滿足條件，則遞歸地在 p, b 所約束的子樹以及b, q 所約束的子樹內重複這一過程，這一查詢可以使每個被報告的點都在常數時間內找到，總體的時間複雜度為 $O(k)$，k即為滿足條件的點數。

笛卡爾樹同樣可以應用於以常數時間查詢超度量空間內點對的距離。超度量空間內距離的定義與最寬路徑問題中的權重相同。從最小生成樹上可以構造一個笛卡爾樹，根結點表示最小生成樹中的權值最大的邊，撤去此邊會將最小生成樹分割為兩個子樹，笛卡爾樹遞歸地從這兩棵子樹上構造。笛卡爾樹的葉結點表示度量空間內的點，兩個葉結點的最低公共祖先則是這兩個點在最小生成樹中最重的邊，代表這兩點間的距離。獲得了最小生成樹及將邊按照權值排序後，笛卡爾樹即可在線性時間內構造出來。

Treap

笛卡爾樹是二叉樹，對於數列而言將其作為二叉搜索樹是自然的。若將二叉搜索樹結點關聯上一個權值，並且保證此權值在樹結構中遵循堆中的序關係，即父結點權值比子結點權值大，則此二叉搜索樹又被稱為Treap. 其名稱來源於樹與堆兩英文詞的組合（tree ＋ heap -> treap）。Treap與笛卡爾樹在結構上是相同的，只是兩者的應用不同。