數據結構與演算法中，樹一般會應用在哪些方面？為什麼？

01-14

DOM, AST 等應用都是對人腦分層分類認知的建模, 都是樹, 不過其中沒多少演算法可以講...

------

樹的一個大類是自平衡二叉搜索樹 (self-balanced BST), 變種特別多:

RB 樹是每個節點是紅色或者黑色, 顏色隔代遺傳
AVL 樹是每個節點包含平衡因子, 等於左高-右高
Splay 樹是每個節點帶個父節點的指針
Treap 是每個節點都帶個隨機的 priority number, parent priority &>= child priority

... (其實說白了都是為了方便平衡操作給節點附加一個欄位)

自平衡二叉搜索樹在面試中經常出現, 但做網頁的互聯網碼農卻很少用得上... 如果是當 Map 用, 往往還不如直接上哈希表. 如果是當排序用, 不如直接用排序演算法... 不過也有有用的時候, 例如查找一個數字的上下界.

------

樹的另一個大類是 Trie, 特點是能保證字典序, 存儲詞典的空間壓縮率高, 能做前綴搜索. 在正則匹配, 數據壓縮, 構建索引都可能用到. Trie 也有不少變種:

Double Array - trie 的一個經典實現 (這實現其實不算樹, 也不適合處理非 ascii 字元的情況)
Patricia Trie (Radix-Tree) - 每個節點可以存一段字元串而不限於一個字元
Judy Array - 基於 256-ary radix tree, 用了 20 種壓縮方式, 極其複雜...
Burst Trie - 如果一個子樹足夠小, 就用 binary 堆的方式存儲, 不過壓縮效果一般
HAT Trie - 壓縮率高而且不容易出現 CPU cache miss, 查速接近哈希表而耗內存少得多. 節點可以是以下三種之一: Array Hash, 序列化的 Bucket, 傳統 Trie node
MARISA Trie - 壓縮率最高, 支持 mmap 載入, 也是用了很多壓縮技巧的複雜實現, 就是構建比較花時間, 也不能動態更新

------

Clojure 是伴隨著不少 persistent (immutable) data structure 而出現的, 尤其是考慮到 Immutable 的數據結構的時候, 樹好像就變成了你的唯一選擇... immutable 的樹也是天生方便並行操作的.

HAMT 的技巧是利用 CPU 指令 popcnt 做快速的小表查詢, 實現了 immutable 哈希表/動態數組
RRB tree 實現了 immutable 的動態數組, 實現更複雜一點, 去掉了 n-way 的限制

------

還有各種各樣的樹, 例如空間索引就有幾十種變種, 舉不動了...

抽象地說，基本上有序列的地方就可以應用樹，因為樹結構即是一種序列索引結構。

（我在這裡提到的序列是一個廣義的概念，一堆東西排在一起就叫序列。）

序列的核心介面就是三個cha：插、查、X（增查刪）。

對於這個三個介面，我們要解決的核心問題是：

①效率：怎麼查得快

②穩定：如果不支持增刪，那麼序列就是靜態結構，用處不大。而支持增刪之後，需要考慮如何保證序列內部結構不會被增刪操作破壞，導致查詢效率受到影響。

那麼樹是如何解決這兩個問題的呢？

效率

對於效率問題，樹相當於對序列建立了一個索引：

（截圖自學堂在線-最大的中文慕課(MOOC)平台里鄧俊輝老師《數據結構》課程課件）

這個索引可以把原本O(n)的查找操作變為O(logn)，可以簡單地理解為在數據結構的層面上構造了一個二分查找演算法。

而通過對某些對象建模，可以把原先直觀上不存在樹狀結構的對象序列轉化為樹狀，從而能夠利用樹的索引功能進行查找，比如空間劃分樹。

（三維k-d樹對空間的劃分，圖來自wiki）

總之，樹通過其結構來表達了一種劃分查找方法，這一方法相比於遍歷搜索的複雜度O(n)，一般情況下複雜度僅有O(logn)。

穩定

如果我們僅僅考慮效率問題，那散列比樹要屌的多。查找複雜度為O(1)。之所以不能用散列來取代樹，是因為散列需要預先開闢大量空間，並不是所有場景下都可以這麼做；而如果空間不夠，則會出現散列衝突（索引結構被破壞）。樹則可以動態改變存儲空間，且運用一些手段來保護自身索引結構。

自平衡二叉搜索樹 (self-balanced BST)的精髓，便在於其維護自身穩定（平衡）的能力。當樹不平衡時，其搜索複雜度便不再是O(logn)了——考慮一個極端情況：一棵樹每個節點都只有右子節點，那麼樹就退化為了鏈表，查找複雜度也和鏈表一樣是O(n)：

（一棵退化的樹）

自平衡二叉搜索樹通過不同的方式來保持平衡：AVL靠記錄平衡因子，伸展樹靠把節點轉到樹根，紅黑樹靠紅黑規則（其實就是通過這個規則來讓自身等價於(2,4)樹）……總之就是在增刪之後又加入一個自平衡步驟，來保證自身的穩定。

總之，當我們看到一個樹形數據結構，主要應該考察以上兩個方面：

①它是如何建立索引的？

②它是如何維持穩定的？

TreeView 類 (System.Windows.Forms)

TreeNode 類 (System.Windows.Forms)

至於TreeView設計成樹結構有什麼用呢？因為計算機的文件系統就是一個典型的樹結構……

數據結構就不多說了，樹以遞歸性質這一對計算機而言最普遍的描述結構簡直貫穿始終。查找樹字典樹四叉樹哪個都是樹的實際應用。除了低維結構不用樹描述（其實一維結構也可以看成是退化後的樹）。

演算法層面，樹基本上到處都是（當然有些時候是隱性的）。計算機執行指令是線性的，程序代碼也是順序的，是個一維結構，一旦需要解決高維問題，利用棧、隊列等一維基礎結構所能做到的只有樹，而樹則可以用來描述高維邏輯，起到了個橋樑作用。

演算法舉例如下。

狀態空間遍歷類：DFS、BFS

決策類：各種自動機（特例還有退化為一位情況的KMP）、貪心、分治、動態規劃（同屬狀態空間遍歷）、匹配

圖與流：尋路（最短路）、生成樹

應用舉例就更多了，例如XML、DOM樹、編譯器中的模式識別和語法樹、JSON數據傳遞、磁碟路徑結構……

樹的普遍取決於它的結構與通常解決問題的演算法的一致性和結構簡單嚴謹：遞歸定義、拓撲有序（無環）、實現簡單。當面臨高維狀態時，其它結構的處理方式幾乎一定不如轉化為樹來的簡單，所以就成為了組織一維實現與高維邏輯中的橋樑。

一個最常見的例子，就是文件系統的目錄結構。

樹這個貨還是很有用的。

首先，很多東西本身的結構就是樹形的，如xml，html等，那麼編寫這些東西的解析器的時候，不可避免用到樹。
再者，樹有個好處，就是當節點有序的時候（即有序樹），那麼在這個樹上搜索一個節點是很快的（log級別），所以，現在的索引一般都是用各種樹（資料庫如mysql大多用B+樹）。
另外，在處理語法解析的時候，樹也是不可或缺的數據結構，各種語言解析之後都是得到語法樹，再做後續處理。

ps.通常這種遞歸定義的東西在計算機技術中的地位都蠻高的。也蠻優美的。

看了一下似乎沒有人提到Heap

Heap在實現中經常會利用樹的概念和數組的結構來完成，這東西在內存管理中使用的非常廣泛

大數據大文件吧，tree能大大降低演算法複雜度

最常用的不是當樹用，而是當映射型容器裡面的映射裝置。比如C++標準庫的map。

人類對未來事件的預測和規劃是樹狀的，走左或走右，買進或賣出，所以很多經典的AI演算法其實都是樹搜索，此外機器學習中的decision tree也是樹結構。

應該主要用於，索引+ 查找：

一維空間：各種平衡樹,包括紅黑樹，AVL

高維空間： KD-tree R-tree PST等

外存索引： B-tree String B-tree, 等

字元串索引： patricia tree, trie , suffix tree, wavelet tree等

搜索：可以採用樹實現各種搜索策略，其各種遍歷方法。

表示：很多事物可以用一棵樹來表示，堆，語法樹等。

計算機網路中

路由協議就是使用了樹的演算法，

由各個路由器的路由表得到一棵樹找到兩個路由器之間最短路徑。

哈夫曼樹也用於編碼

所謂哈夫曼編碼。

編碼效率還是不錯。

說一個在機器人領域的應用吧。一個二維空間可以表示成一顆四叉樹，每個節點代表一個空間，子樹代表四個相限的子空間。用來檢索空間，遊戲里的很多檢測碰撞都依賴於四叉樹實現。當然，對於三維環境，還有八叉樹。

騰訊學長親述，英雄聯盟匹配系統

請看這篇文章：多叉樹及其應用：多叉樹結合JavaScript樹形控制項實現無限級樹形結構（一種構建多級有序樹形結構JSON（或XML）數據源的方法） - 企業應用,多叉樹,樹形結構JSON - Java - ITeye論壇

C++的STL的一些類型用了紅黑樹

分散式系統中很多用到了B樹或B+樹。

Random Forest

加上rank當排行榜用

樹結構是使用廣泛的～二叉、 (紅黑)平衡葉子樹，B+-樹(參考mysql)，多叉等～

用於保持數據有序的同時也能有對數級的查詢性能

矩陣申請空間時候需要提前設定大小，動態申請代價比較大，用樹的話比較合適。

b樹，各種資料庫，不能更常用

搜索。

兩個字就能回答的問題，不知道你們在寫什麼。