樹簡(jiǎn)介

笛卡爾樹是平衡二叉樹的一種，他和我們之前學(xué)習(xí)的AVL樹一樣通過旋轉(zhuǎn)來調(diào)整，使平衡樹達(dá)到平衡態(tài)。不過，不同的是：笛卡爾樹除了用于決定節(jié)點(diǎn)向左/右分布的key外，還有個(gè)value，用來決定節(jié)點(diǎn)的層級(jí)先后。

笛卡爾樹的分布存在以下特點(diǎn)：

key:分布遵循BST的規(guī)律，即左子樹key<根key<右子樹key

value:分布遵循堆的規(guī)律，即父value < 子value/子value < 父value

父value < 子value: 最小堆

子value < 父value：最大堆

樹操作算法概述

笛卡爾樹我們只介紹建樹的過程。忽略樹的修改操作。

建樹

笛卡爾樹的key遵循二叉搜索樹的特點(diǎn)。value遵循堆的特點(diǎn)。所以我們先把數(shù)據(jù)按照key從小到大進(jìn)行排序?！疽源藶槔?，如果你硬要從大到小也是一樣的道理】

接下來我們只需要從第一個(gè)節(jié)點(diǎn)開始串下去就行了，后面的肯定比前面的大，所以在前面節(jié)點(diǎn)的右子樹或者父節(jié)點(diǎn)，而是右子樹還是父節(jié)點(diǎn)，通過value判定。

一個(gè)二叉樹大概長(zhǎng)下面這樣【網(wǎng)上盜的圖，不是搜索樹，大概看個(gè)結(jié)構(gòu)就行】：

1.png

既然不是當(dāng)右兒子就是當(dāng)爸爸，我們?cè)跇?gòu)建過程中直接把根節(jié)點(diǎn)到最右子樹存下來，方便為新來的節(jié)點(diǎn)找到進(jìn)入的位置。

存儲(chǔ)的東西如下：

2.png

每新來一個(gè)節(jié)點(diǎn)，我們拿著value一個(gè)一個(gè)比較，因?yàn)楦?code>value要比子value大。而且有一個(gè)特點(diǎn)，新插入一個(gè)點(diǎn)后，原來他右下位置的點(diǎn)就變成他的左子樹了，右鏈砍掉了一部分。所以有兩種思路：

每次從根往右遍歷

和當(dāng)前的節(jié)點(diǎn)比較，當(dāng)前節(jié)點(diǎn)比插入值大就繼續(xù)向后遍歷，直到遇到一個(gè)比他小的，然后插到他的前面，他后面的節(jié)點(diǎn)做插入點(diǎn)的左子樹

每次從右下角遍歷

和當(dāng)前的節(jié)點(diǎn)比較，當(dāng)前節(jié)點(diǎn)比插入值小就過，繼續(xù)向前遍歷，找到對(duì)應(yīng)位置，插進(jìn)去

兩種方法其實(shí)都是一個(gè)思路：遍歷，直到找到合適位置，然后插入。

在網(wǎng)上找到的很多源碼都提到了O(n)時(shí)間復(fù)雜度的笛卡爾樹構(gòu)造方法，說是借助棧，他們一般用的是我介紹的第二種思路：和棧頂比較，不行就扔掉，插進(jìn)去后入站，然后新的右鏈就又在棧中了。

如果你思路清晰了，完全可以不借助棧，直接從根節(jié)點(diǎn)右子樹右子樹的遍歷就行，都不用維護(hù)棧了。

源碼

直接放項(xiàng)目的地址了，我是用的java寫的增刪操作，沒有用C。還有就是沒有專門為這個(gè)建git，源碼在com.gateway.learn.tree下面。github地址：https://github.com/LiPengcheng1995/gateway-parent.git

樹應(yīng)用場(chǎng)景

官方話：

笛卡爾樹是一種特定的二叉樹數(shù)據(jù)結(jié)構(gòu)，可由數(shù)列構(gòu)造，在范圍最值查詢、范圍top k查詢（range top k queries）等問題上有廣泛應(yīng)用。它具有堆的有序性，中序遍歷可以輸出原數(shù)列。

（用數(shù)組下標(biāo)當(dāng)key）

自己的話：

笛卡爾樹我認(rèn)為其實(shí)最重要的并不是key，而是value：

key存在的意義是為了讓數(shù)列中相鄰的節(jié)點(diǎn)繼續(xù)相鄰，比較形象一點(diǎn)的形容就是只看key的話可以把key當(dāng)作數(shù)列的下標(biāo)，然后從中間把這個(gè)數(shù)列拎起來，就形成了樹結(jié)構(gòu)。

value存在的意義你可以看作數(shù)組中存的值，你給整個(gè)數(shù)列做了一個(gè)排序后的存儲(chǔ)，只不過你把排序結(jié)果放在了樹的上下結(jié)構(gòu)中，節(jié)點(diǎn)下標(biāo)沒變。

問題一

這個(gè)樣一個(gè)問題：求[a,b]范圍中的最大值，你只需要找到a,b節(jié)點(diǎn)的LCA(Lowest Common Ancestor)，即最近公共祖先。

思路分析

構(gòu)建笛卡爾樹
依靠二叉排序樹的特點(diǎn)快速定位LCA
返回查到的LCA的value值

本文算法時(shí)間復(fù)雜度分析

構(gòu)建笛卡爾樹 O(n)。（因?yàn)橐韵聵?biāo)為key，不需要重新排序了，用棧來輔助理解就是每個(gè)元素只會(huì)有一次進(jìn)棧）
依靠二叉排序樹特點(diǎn)快速定位LCA O(log2(n))【平衡二叉樹樹深，雖然笛卡爾樹的平衡不一定有VAL樹那么平，但是大概還是平的】
- this.key < a-->右邊走
- this.key > b --->左邊走
- 遇到的第一個(gè)a<this.key<b，this.value就是結(jié)果
return this.value

所以時(shí)間復(fù)雜度為O(n)。當(dāng)然，如果多次查詢只需要一次建樹，這就很爽了，時(shí)間復(fù)雜度為O(log2(n))。

傳統(tǒng)算法時(shí)間復(fù)雜度分析

順序遍歷一遍，記一下最大就行，時(shí)間復(fù)雜度為O(n)。

比較

本文算法優(yōu)點(diǎn)：

多次查詢只需一次建樹

查詢效率穩(wěn)定，（已經(jīng)構(gòu)建笛卡爾樹后，區(qū)間范圍越大查詢效果往往越快）

本文算法缺點(diǎn)：

存儲(chǔ)樹結(jié)構(gòu)有一一定開銷

不穩(wěn)定，存在極度變態(tài)數(shù)列情況下整棵樹被拉成一個(gè)鏈的可能

問題二

這樣一個(gè)問題：已知一個(gè)無序數(shù)組，我給你其中一個(gè)下標(biāo)，你要告訴我這個(gè)下標(biāo)對(duì)應(yīng)的值是多大范圍內(nèi)的最大/小值

思路分析

構(gòu)建笛卡爾樹，如果求最大值，就按照最大堆構(gòu)建【后面都按照最大來講，最小也是同理】
笛卡爾樹看下標(biāo)是樹，看值是堆，找到對(duì)應(yīng)的點(diǎn)，它下面的值都比它小，找到他的子樹中的最左邊點(diǎn)、最右邊點(diǎn)即可

本文算法時(shí)間復(fù)雜度

構(gòu)建樹，需要 $O(n)$
找節(jié)點(diǎn)對(duì)應(yīng)子樹的最大最小，即是兩個(gè)范圍點(diǎn)【找最左/最右子樹即可】，復(fù)雜度為樹深度，都是 $O(log_2(n))$

綜上，復(fù)雜度為 $O(n)$

問題三

這個(gè)樣一個(gè)問題：求[a,b]范圍中的第n大的值。

思路分析

構(gòu)建笛卡爾樹
依靠二叉排序樹的特點(diǎn)快速定位LCA
看LCA下面一層夠不夠數(shù)
- 夠就找到第n-1大的
- 不夠就從再下一層找，設(shè)本層有m個(gè)點(diǎn)
  - 這一層夠就找第n-m-1大的
  - 不夠再去下一層。。。。。。

時(shí)間復(fù)雜度分析

構(gòu)建笛卡爾樹 O(n)
找LCA O(log2(n))
找第n大的，由于樹每靠上一層，本曾的節(jié)點(diǎn)數(shù)以指數(shù)倍減少，所以我們可以近似看成常數(shù)（可以。。。吧，總之需要比較的很少了）、

所以時(shí)間復(fù)雜度為O(n)。當(dāng)然，如果多次查詢只需要一次建樹，這就很爽了，時(shí)間復(fù)雜度為O(log2(n))。

傳統(tǒng)算法時(shí)間復(fù)雜度分析

得對(duì)這一段區(qū)間進(jìn)行排序，時(shí)間復(fù)雜度為O(nlog2(n))

比較

如果區(qū)間隨便給，這么查的話，還是本文的算法好。缺點(diǎn)和上一個(gè)問題一樣就不提了。

還有一個(gè)明顯的缺點(diǎn)，就是如果對(duì)同一個(gè)區(qū)間你經(jīng)常查top k 。直接用傳統(tǒng)方法排個(gè)序反而比較快?？醋约盒枰裁戳恕?/p>

問題四

給出n個(gè)非負(fù)的整數(shù)，表示直方圖中每個(gè)條的高度，且每個(gè)條的寬度均為1，找出這些條覆蓋的最大面積的矩形。

3.png

思路分析

構(gòu)建笛卡爾樹，（最小堆）
后序遍歷，將每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)數(shù)目存在這個(gè)節(jié)點(diǎn)里，并求出子節(jié)點(diǎn)數(shù)目和此節(jié)點(diǎn)value的乘積。找到乘積最大的那個(gè)結(jié)果

幫助理解：

子節(jié)點(diǎn)數(shù)目 = 這個(gè)節(jié)點(diǎn)的value是多少個(gè)節(jié)點(diǎn)中最小的 = 涂色長(zhǎng)方形的底邊寬是多少

此節(jié)點(diǎn)value = 這n個(gè)節(jié)點(diǎn)的高度最小值 = 涂色長(zhǎng)方形的高

注意：

因?yàn)槭前凑障聵?biāo)為key進(jìn)行排的，原來相鄰的長(zhǎng)條現(xiàn)在還是相鄰，所以才能這么等效

時(shí)間復(fù)雜度分析

構(gòu)建笛卡爾樹 O(n)
后續(xù)遍歷、計(jì)算、存儲(chǔ)，因?yàn)橹槐闅v一遍，所以時(shí)間復(fù)雜度是 O(n)

思路分析（基礎(chǔ)）

上面的雖然說著通順，但是正常人的思路并不是這樣的。你可以這樣想，底和高都變化，我們需要先找兩者的關(guān)聯(lián)，先構(gòu)建出一個(gè)合適的計(jì)算公式：

從底入手

我們需要遍歷底邊的所有匹配段情況，并算出區(qū)域內(nèi)的最低點(diǎn)【數(shù)組一端區(qū)間內(nèi)的最小值】，這樣需要構(gòu)建笛卡爾樹，因?yàn)槠ヅ涞牟淮_定性，我們需要枚舉底邊的(1+2+...+n)種情況，復(fù)雜度是 $O(n^2)$ 。當(dāng)然，如果你硬要把每次確定最小值的操作算到求高的操作中去的話，就是 $O(n^2log2(n))$ 。

從高入手

前面一個(gè)思路，我們解決的最大的問題是把范圍確定后的定高問題解決了，但是確定底邊取值范圍開銷太大了，達(dá)到了 $O(n^2log2(n))$ 級(jí)別。

遇到了這么亂的思路，一般有兩個(gè)可能：

問題就是挺亂的。就像我們某些不合理的需求一樣，屎一樣的需求，再怎么捋代碼也是亂七八糟
我們抽象的不對(duì)

我們抽象出了底邊x和高y,然后求xy的乘積最大值。我們求x時(shí)即使使用普通的排序方法，不用笛卡爾樹也還有 $O(n)$ ，但是找底邊時(shí)我們直接就沖著 $O(n^2)$ 去了，這就給人不協(xié)調(diào)的感覺了。

所以我們進(jìn)行更近一步的抽象，設(shè)從x到y(tǒng)，取這范圍內(nèi)的長(zhǎng)方形，設(shè)高的最小值為z，這樣x,y,z的判斷就都是 $O(n)$ 了，當(dāng)然，直接一下，復(fù)雜度直接就是 $O(n^3)$ 了。

我們需要找到三個(gè)變量之間的關(guān)系。

如果我們確定一個(gè)x,后面y每個(gè)取值對(duì)應(yīng)的高度都有可能變化，變化根據(jù)數(shù)組來變，沒有規(guī)律，而沒有規(guī)律就意味著遍歷，意味著低效。

如果確定y，是一樣的道理。

如果我們確定z，那就無所謂了，x和y往開的撐就行了。撐的越開，面積越大。

所以我們從z入手，算出每個(gè)z的值都能對(duì)應(yīng)最大多大的(y-x)，也就是z值都是多大區(qū)間內(nèi)的最小值。此處回到問題二。只需要遍歷即可，所以時(shí)間復(fù)雜度是：

構(gòu)建笛卡爾樹 $O(n)$
一一求出每個(gè)高度對(duì)應(yīng)的底邊最大值【對(duì)應(yīng)的最大最小的范圍】(n個(gè)，每個(gè) $O(log_2(n))$ ，也就是 $O(n)*2O(log_2(n))=O(2nlog_2(n))$
n個(gè)方案，在一一計(jì)算時(shí)順手存下最小的值以及計(jì)算方案即可，無需多余的時(shí)間復(fù)雜度

所以時(shí)間復(fù)雜度降低到了 $O(2nlog_2(n))$ 。

文獻(xiàn)參考

https://www.cnblogs.com/pushing-my-way/archive/2012/08/24/2653709.html
https://blog.csdn.net/pipisorry/article/details/39033269
https://baike.baidu.com/item/%E7%AC%9B%E5%8D%A1%E5%B0%94%E6%A0%91
https://agatelee.cn/2016/07/%E6%A0%91%E7%B1%BB%E9%97%AE%E9%A2%98%E7%AC%9B%E5%8D%A1%E5%B0%94%E6%A0%91/
https://zh.wikipedia.org/wiki/%E7%AC%9B%E5%8D%A1%E5%B0%94%E6%A0%91

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

樹——笛卡爾樹

樹——笛卡爾樹

樹簡(jiǎn)介

樹操作算法概述

建樹

源碼

樹應(yīng)用場(chǎng)景

問題一