? ? ? ? 之前說過的，來寫個樹專題，我會把我想到的與樹有關的知識點都寫一下，當然得是我會的……
????????這里講的東西有些是一筆帶過，以后可能會獨立寫一篇來描述相關算法。
????????樹，就是不存在環的聯通圖，通常來說樹的邊數=點數-1，順便提一句，還有種叫仙人掌的東西，就是所有邊至多在一個環上的圖。一棵有根樹，就應該有一個樹根，除根外每個節點都有父親節點，除葉子節點外每個節點都有兒子節點。樹的深度定義為樹根深度為1，其他節點深度為其父節點+1。
????????二叉樹，就是每個節點最多有兩個兒子的樹，如果一棵二叉樹除葉子節點外每個節點都有兩個兒子，且每個葉子節點深度都一樣，那它就是滿二叉樹（或者說一棵深度為k，且有2k-1個節點的二叉樹），至于完全二叉樹，就是由滿二叉樹在最深一層從右向左地刪除節點的方式生成的二叉樹（或者說每一個結點都與同深度的滿二叉樹中編號從1至n的結點一一對應的二叉樹），路徑什么的我就不費力解釋了……
????????樹的遍歷：
????????先序遍歷：按樹根，左子樹，右子樹的順序遞歸遍歷。????????中序遍歷：按左子樹，樹根，右子樹的順序遞歸遍歷。
????????后序遍歷：按左子樹，右子樹，樹根的順序遞歸遍歷。
????????①樹狀數組：
????????我把它歸進來，僅僅是因為它名字里帶“樹”，我并不認為它跟樹有什么太大關系……
????????這個數據結構用一個附加數組c來實現對原數組的區間求和，區間求極值，單點修改什么的。我們設一個函數f(x)=(-x)&x，這里-x表示x的補碼，&表示與運算，其實表示的是x二進制數碼中從右開始的第一個1的位置。對于附加數組中下標為y的位置記錄的是從原數組中下標為y-x+1到y的值。例如1號點管轄[1,1]，2號管轄[1,2]，3號管轄[3,3]，4號管轄[1,4]……
????????然后，假如我們要查詢下標為p的節點的前綴記錄值，則ans(p)=ans(p-f(p))∪c[p]，可以用循環來處理，直到p=0，這里∪要根據實際需要決定（求和就是+，最大值就是max等），區間求值的話，其實就是兩個前綴值的“差”。
????????單點修改的時候，對于下標p，同樣是循環，先修改附加數組中的p，每次修改后將p加上f(p)，直到p越界，也是挺好理解的。
????????每種操作復雜度都是O(log?n)。
????????②線段樹：
????????用一顆樹中的節點來覆蓋原數組的區間，根節點覆蓋[1,n]，根節點的左兒子覆蓋[1,(n+1)/2]，右兒子覆蓋[(n+1)/2+1,n]……對于覆蓋區間[l,r]的點，記mid=(l+r)/2，其左兒子覆蓋[l,mid]，右兒子覆蓋[mid+1,r]。
????????當我們要查詢的時候，從根節點開始，一層一層向下傳就是了，比如查詢[a,b]，如果當前節點的mid不在[a,b]中，就直接傳遞給左兒子或右兒子，否則分別傳遞[a,mid]，[mid+1,b]給左右兒子。當然，如果[a,b]已經是本區間的[l,r]了，那就直接返回當前記錄值了。
????????插入區間（即區間修改），我們要么可以一層層傳遞，暴力修改到葉子節點，然后更新整棵樹，但這樣復雜度較高。如果當前修改區間恰好是當前節點的覆蓋區間，我們可以打一個標記，表示這個節點被修改過，等下次查詢時，如果查到這個點，就將標記下傳，并進行合并（多標記合并時注意考慮優先級），然后復雜度會大幅降低。同時，多種多樣的標記然線段樹可以做很多很多事情，很多時候是可以取代樹狀數組的。
????????線段樹可以進行持久化處理。持久化，簡單的說就是你可以訪問以前的，或說某次修改之前的線段樹，而不一定得是當前得線段樹。最簡單的思路就是在每一個時間都建一顆樹，但是考慮到每修改一個點，產生影響的只有log?n個點，我們可以只新建這log?n個點，并連接原樹中未被修改的兒子。由于每次會產生一個新的根，所以用一個數組來記錄每次的根節點，就能實現持久化的查找。
????????③二叉搜索樹：
????????二叉搜索樹是相對于鏈表的一種優化的查詢方法，把整個原數組變成一棵二叉搜索樹，樹的中序遍歷構成原數組的單調數列，每次查詢就從根節點出發，判斷其與根節點的大小關系，向其左或右子樹查詢，以此類推。二叉搜索樹在數據較特殊時會退化成一條鏈（當然，可以用隨機化），最壞復雜度仍是O(n)，這時需要對其進行旋轉操作，使之平衡，于是誕生了平衡二叉樹。
????????④平衡二叉樹：
????????平衡二叉樹，即在二叉搜索樹的基礎上，用各種方式使樹盡可能平衡的數據結構，它主要依賴于旋轉操作：
????????左旋：將根節點的右兒子變成新根，原根變成新根的左兒子，新根的原左兒子變成原根的新右兒子，并作相應調整。
????????右旋：與左旋相反就是了。?
????????treap（樹堆）：treap的主要思想是給樹上的每個節點隨機一個優先級，在維護二叉樹性質的同時，按優先級維護堆性質（至于堆，我們待會再說）。這樣一來這顆樹能盡可能保持平衡，以保障復雜度。
????????Splay（伸展樹）：Splay主要依賴于其把一個點旋轉至根的操作。每對一個點進行一次修改，查詢等操作，就需要將其旋轉至根，這樣可以保障均攤復雜度控制在O(log?n)，相關證明這里不加詳述。有一點必須注意，旋轉操作應采用雙旋而非單旋。即假如當前節點與其父節點同為左子樹或同為右子樹時，應先將以祖父節點為根的樹進行旋轉，再將當前節點旋轉至根，這樣可以使盡可能多的點被移動，使樹更加平衡。同時，Splay還有劃分，合并，翻轉等諸多拓展應用，還被用于LCT中的Auxiliary?Tree的維護。
????????AVL樹：這個樹的話，我覺得是最“正宗”的平衡樹了。它會時時檢測樹中是否有某節點左右子樹的深度差大于1，一旦大于1，先找到最先發生不平衡的節點，進行旋轉，好像也最好理解。
????????SBT：其實它和AVL樹有些類似，只不過AVL樹用深度維護平衡，SBT用size域，即子樹大小來維護平衡，它要求每顆子樹大小不小于其兄弟節點的兒子為根的子樹大小。維護的size域事實上在查詢時也有一定用處，每個操作復雜度都是O(log?n)。
????????紅黑樹：樹上每個節點都有一個顏色，紅或黑，根和葉子節點都為黑色，每個紅色節點的兩個子節點都是黑色，從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。通過對節點的調整和顏色修改維護以上性質，使紅黑樹的復雜度同樣只有O(log?n)。
??⑤堆：
????????堆是一種完全二叉樹結構，以小根堆為例，每個節點擁有一個key值，我們必須維護每個節點的key值小于其兩個兒子的key值，這樣一來，根節點就是整棵樹中key值最小的，從而可以實現動態修改和查詢極值。利用對數組堆進行排序，可得到復雜度與快排相當的O(nlog?n)的堆排序算法，也可用于最短路迪杰斯特拉算法的優化。
????????左偏樹，亦稱可合并堆，此時它是普通的二叉樹，而非完全二叉樹，我們在堆的基礎上定義一個右深度：無右兒子的點右深度為0，否則為其右兒子的右深度+1，左偏樹要求一個點的左兒子右深度不小于其右兒子的右深度，從而整棵樹大部分點集中在左邊，亦稱左偏樹。左偏樹支持合并操作，將根的key較小的樹作為被插入樹，較大為插入樹，把插入樹的極右鏈（從根一直向右走的鏈）上的點依次在被插入樹的極右鏈上找到自己的位置，插入并維護左偏樹的性質。可以看出，左偏樹并不是一種很平衡的樹，有時它甚至很不平衡，因為左偏樹本身就不是為了快速查找設計的，它僅僅為了快速對堆進行合并，從而實現一些普通堆難以做到的功能。
????????此外，堆還有斐波那契堆，配對堆等拓展，這里不加詳述。
?⑥樹上倍增
????????樹上倍增可以用來快速查詢兩個節點之間的最近公共祖先，查詢路徑和或極值等。對于每個點，我們需要維護該點（設為p點）向上2^k條邊的祖先f[p][k]，預處理時可以利用f[p][k]=f[f[p][k-1]][k-1]這一公式，同時維護該路徑上的和、極值等數據。在查詢時，對于兩個節點，先把它們提到同一高度，再利用循環移動到它們最近公共祖先的兩個子節點，就可以完成查詢。????????⑦最小生成樹：
????????最小生成樹，即在一個給定圖上，找出一棵生成樹，使其邊權和最小，相關算法我在另一篇日志已經寫過，這里不加詳述。????????⑧最優比率生成樹：
????????與最小生成樹相似，但要求是使邊權和除以邊花費和的比值最大，詳見我的另一篇日志。????????⑨樹形DP：????????樹形動態規劃，其實就是以樹為基礎，按樹的特定遍歷順序（拓撲序，DFS序等）進行動態規劃，亦不難理解。
????????⑩并查集：
????????這是一種類似動態鏈表的結構，它可以實現兩棵樹的快速合并和兩點是否在同一樹上的查詢。每個點維護其父親節點的位置，查找時只需遞歸計算出當前點所在樹的根，判斷兩個根是否相等。合并時以同樣的方式，連接這兩棵樹的根節點。合并時采用啟發式合并（較小的樹合并到較大的樹上面），查詢時采用路徑壓縮（即不記錄父親節點，直接記錄樹根），可以使效率有所提升。
????????可持久化并查集，就是用可持久化線段樹維護可持久化樹組，實現可持久化的并查集……這話很溜，慢慢品味……
?????????trie（字典樹）：
????????trie主要用于字符串查詢，或有關二進制碼的運算。對于字符串，建一個樹根，不帶任何信息，對每個字符串，我們從根出發，看看根的兒子中是否包含該字符串的第一個字符，如果有，遞歸到這個子節點處理下一個字符，否則建立一個新的子節點，同樣進行處理。對于二進制運算，尤其以異或操作為例，將原數的01串以與字符串相同的方式插入，查詢時，就可以從樹根出發，尋找與當前數字01位置相反或相同的子節點，就可以得出原樹所有數字中與待查詢數字異或后的極值。
????????PS：trie在字符串匹配算法——AC自動機中有重要作用。
?????????樹鏈剖分：
????????顧名思義，就是把樹鏈進行分解，每個點的兒子中子樹較大的點稱為重兒子，重兒子與父節點的連邊稱為重邊，由重邊連成的鏈稱為重鏈。樹鏈剖分其實就是維護每條重鏈的記錄數據，在查詢時優先對查詢路徑利用重鏈進行“跳步”，從而達到降低復雜度的目的。其實它和樹上倍增很類似，解決的問題也有相同點，個人來說，倍增可能比樹鏈剖分好寫一些。
??????????最近公共祖先查詢：
????????剛才說過的樹上倍增就可以用于最近公共祖先查詢，這里介紹一種離線的方法：從樹根開始，對于每個點，依次遞歸其子樹，遞歸完畢后，利用并查集把它的子樹的集合的父親設為當前節點。然后找一下每一個與當前節點有關的詢問，如果這個詢問的另一個節點已經被遞歸查詢過了，那么答案就是另一節點所在集合的父節點。這個方法非常巧妙，但由于是離線，比較麻煩，實際使用較多的還是倍增。
??????????K-d樹：
?????????K-d樹主要可以用于解決k近鄰查詢問題，我們以二維中的最近鄰（就是在二維平面的點集上，與給定點的歐氏距離最小）為例。首先對于點集，我們先算出它們x，y坐標的方差，取較大的方差（這是為了使點盡可能分散開），以x軸為例，按橫坐標排序，取中位數，作一條與x軸垂直的直線，把所有點分成兩個部分，左空間，和右空間，再遞歸處理這兩個空間，將點集建成了一棵樹。查詢時，遞歸找出給定點所在的空間，從葉子節點開始，實時更新最小的歐氏距離，查詢該點以這個距離為半徑畫圓是否與當前節點作出的直線相交，如果不相交，則最近鄰不可能在另一空間，否則再遞歸處理另一空間，最后得到的距離即是最小距離。擴展到k近鄰也很容易，只需維護一個距離數組就行了。
??????????Link-Cut?Tree（動態樹）：
?????????動態樹（LCT）是用于維護森林中樹的合并，分離等等操作，與樹鏈剖分相同，它也有重邊，重鏈之分，但重兒子的定義為該子樹中最后訪問的節點。每一條重鏈用一個Splay來維護（這是為了快速進行合并，刪除等操作）。
????????Access(x)?操作是動態樹的最基本操作，即依次訪問樹根到點x路徑上的所有點。這時，我們需要先Splay(x)，除去x的右兒子（從而除去比x更深的樹鏈，因為我們訪問了x，那么x就沒有重兒子了）。然后依次對訪問到的點進行Splay操作，將其右兒子更換為其后繼，直到樹根。
????????find-root(x)?操作要求找到x的所在根，先Access(x)，然后需要Splay(x)，查詢其極右節點就好了
????????Cut(x)?斷掉x與其父親的邊，先Access(x)，Splay(x)，再斷掉x與其左兒子的邊就行。
????????Link(x,y)?連接x，y點分別對x，y進行Access和Splay操作，對x所在樹進行reverse（翻轉）操作，再連接x與y。
????????以后想到什么再補充吧……

轉載于:https://www.cnblogs.com/Enceladus/p/4979048.html

總結

以上是生活随笔為你收集整理的树专题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。