基本介紹
- 中文名：笛卡爾樹
- 外文名：Cartesian tree
- 結構：Vuillmin在解決範圍搜尋
- 又稱：笛卡兒樹
- 屬於：二叉樹的一種
簡介,定義,笛卡爾樹套用,範圍最值查詢與最低公共祖先,treap,
簡介
笛卡爾樹是一種特定的二叉樹數據結構，可由數列構造，在範圍最值查詢、範圍top k查詢（range top k queries）等問題上有廣泛套用。它具有堆的有序性，中序遍歷可以輸出原數列。笛卡爾樹結構由Vuillmin(1980)在解決範圍搜尋的幾何數據結構問題時提出。從數列中構造一棵笛卡爾樹可以線性時間完成，需要採用基於棧的算法來找到在該數列中的所有最近小數。
定義
無相同元素的數列構造出的笛卡爾樹具有下列性質：
- 結點一一對應於數列元素。即數列中的每個元素都對應於樹中某個唯一結點，樹結點也對應於數列中的某個唯一元素
- 中序遍歷（in-order traverse）笛卡爾樹即可得到原數列。即任意樹結點的左子樹結點所對應的數列元素下標比該結點所對應元素的下標小，右子樹結點所對應數列元素下標比該結點所對應元素下標大。
- 樹結構存在堆序性質，即任意樹結點所對應數值大/小於其左、右子樹內任意結點對應數值
根據堆序性質，笛卡爾樹根結點為數列中的最大/小值，樹本身也可以通過這一性質遞歸地定義：根結點為序列的最大/小值，左、右子樹則對應於左右兩個子序列，其結點同樣為兩個子序列的最大/小值。因此，上述三條性質唯一地定義了笛卡爾樹。若數列中存在重複值，則可用其它排序原則為數列中相同元素排定序列，例如以下標較小的數為較小，便能為含重複值的數列構造笛卡爾樹。
笛卡爾樹套用
範圍最值查詢與最低公共祖先
笛卡爾樹可以有效地處理範圍最值查詢（range minimum queries），通過將定義在數列上的RMQ問題轉化為定義在樹結構上的最低公共祖先（lowest common ancestor）問題。數列以線性時間構造出笛卡爾樹，笛卡爾樹則能以常數時間處理最低公共祖先查詢，因此線上性時間的預處理後，範圍最值查詢能以常數時間完成。
Bender & Farach-Colton (2000)則提出了RMQ與LCA問題的新聯繫，他們通過不基於樹的算法處理RMQ問題從而有效地解決LCA問題。其使用歐拉路徑的技巧將樹結構轉化為數列，此數列具有特定性質（相鄰數值代表樹中的相鄰頂點，即在樹中高度差為1的頂點），利用這一性質RMQ問題可以很高效地得到解決。通常的數列則不具備此性質，為了將一般的數列轉化為具有上述性質的數列，需要套用到笛卡爾樹，具體過程為在普通數列上構造笛卡爾樹，在笛卡爾樹上使用歐拉路徑轉化的方法將樹轉化為具有上述性質的新數列。
treap
笛卡爾樹是二叉樹，對於數列而言將其作為二叉搜尋樹是自然的。若將二叉搜尋樹結點關聯上一個權值，並且保證此權值在樹結構中遵循堆中的序關係，即父結點權值比子結點權值大，則此二叉搜尋樹又被稱為Treap. 其名稱來源於樹與堆兩英文詞的組合（tree + heap -> treap）。Treap與笛卡爾樹在結構上是相同的，只是兩者的套用不同。
