樹狀結構算法的介紹及其在生活中的應用

王維燁

摘要：本文主要介紹了數據結構中的各種樹狀結構，重點介紹了二叉搜索樹，其他還包括平衡二叉樹，紅黑樹，霍夫曼樹以及堆。此外，本文詳細解釋了二叉搜索樹的操作的時間復雜度。同時，我們將介紹各種樹形結構在生活中的應用。

關鍵詞：算法；樹狀結構；應用

中圖分類號：TP312 文獻標識碼：A 文章編號：1007-9416（2017）05-0147-02

在計算機世界中，有各種各樣的抽象數據結構，包括數組，隊列，堆棧，鏈表等。這些數據結構都可以轉換到現實生活中的各種問題中去，以此能夠高效的解決一些問題。在這些數據結構中，被使用的較為廣泛的無疑是樹狀結構。本文就將詳細介紹一下樹狀結構。

所謂樹狀結構，就是將信息存貯在節點之中，節點與節點之間用邊鏈接起來的結構。一顆二叉樹由結點的有限集合組成。這個集合可以由一個根節點和兩個不相交的二叉樹組成，這兩顆二叉樹分別成為這個根節點的左子樹和右子樹。關于樹狀結構其他種類更多的結構介紹，我們將在下文中一一闡述。

樹狀結構在現實生活中的使用也相當廣泛。從計算機網絡到數據庫實現，樹狀結構無時無刻的在提高我們的工作效率。本文也會介紹其在生活中的應用，以引發讀者對計算機科學的興趣。

1 二叉檢索樹

我們首先介紹一下樹狀結構中最為簡單也是最為常見的一種樹：二叉檢索樹（Binary Search Tree）。

1.1 定義

首先我們介紹一下二叉檢索樹，明確一下它的定義。

所謂二叉檢索樹，就是滿足一下條件的一棵二叉樹：任意一個結點，設其值為K，則該節點的左子樹中任意一個結點的值都小于K；該結點右子樹種任意一個結點的值都大于或等于K。如圖1所示。

同時，任意一個結點都有其深度，我們定義為根節點到該節點的路徑長度。而BST的高度就是最深深度加1。

1.2 二叉檢索樹的搜索

對于一棵二叉檢索樹而言，其最重要的功能就是能夠快速的找到某一個節點的值。假設我們從根節點開始，在BST中檢索K值。如果根節點存儲的值為K，則檢索結束。如果不是K，則必須檢索樹的更深一層。BST檢索的優勢在于只需要檢索兩棵子樹的其中之一。如果K小于根節點的值，則只需要檢索左子樹，反之則檢索右子樹。這個過程將會一直持續到K被找到，或者到一個葉節點（沒有子樹）為止。如果到了一個葉節點，依然沒有發現K，則表示K不在該BST中。

搜索所消耗的時間取決于該結點被找到的深度。我們思考一下在一般的情況下，我們需要往下尋找直到一個最深葉節點才能夠停下。那么這時候，我們的時間代價就是該BST的高度。對于有n個結點的二叉樹，如果它是平衡的，那么他的高度就為logn。因此在平均情況下，我們搜索功能的時間復雜度為O（logn）。

1.3 二叉檢索樹的插入

這里我們先做一個簡單的假設，我們要插入的節點的值K與BST中任意一個節點的值不重復。我們插入一個節點的時候，我們需要找出它必須放在樹結構的什么地方。這就會把它帶到一個葉節點（子樹數量為0的節點）或者一個在待插入的方向上沒有子節點的分支節點（子樹數量為1的節點）。我們記錄該節點為R，然后我們將包含值K的新節點作為R的子節點加上去，就完成了插入操作。

與搜索類似，插入操作的時間代價依賴于R的深度。因此，在平均情況下，插入操作的時間復雜度為O（logn）。

1.4 應用

二叉檢索樹在生活中應用相當廣泛。首先，二叉檢索樹是其他平衡二叉樹的基礎，例如AVL樹，紅黑樹等。此外，就其本身而言，也在日常生活中體現了自己的價值。其中最典型的就是路由器中的路由搜索引擎，查找一條指定的路由最壞情況下最多只需要查找31次。

雖然二叉檢索樹在樹中的地位相當的高，但是其更大的用處在于衍生了很多的平衡二叉樹，這些樹在我們現實生活中大發光彩。下面我們也會介紹到，但在介紹的過程中，我們不再詳細說明其各種操作的原理以及時間代價了。一方面其復雜程序不是本文可以說明清楚的，另一方面我也希望將文章的重點放在應用這一角度。

2 堆

2.1 定義

堆由兩條性質來定義：首先，它是一棵完全二叉樹。其次，堆中存儲的數據是局部有序的，也就是說，節點存儲的值與其子節點存儲的值存在著某種關系。這種關系可以分成兩類，這兩類關系也決定了兩種不同的堆。

最大堆：任意一個節點的值都大于或者等于任意一個子節點的值。根節點存儲著該樹中所有節點的最大值。

最小堆：任意一個節點的值都小于或者等于任意一個子節點的值。根節點存儲了該樹中所有節點的最小值。

這里我們需要弄清楚他和BST的區別。BST是定義了一組完全排序的節點，左邊節點的值都比右邊節點的值小。而堆僅僅實現了局部排序，當一個節點是另一個節點的子節點時，才可以確定這兩個節點的相對關系。

2.2 應用

堆在生活中的應用非常廣泛，最為常見的兩個就是排序和優先隊列。

我們將一組無序的數列從小到大進行排列，就需要使用最大堆。我們知道根節點存儲著該樹中所有節點的最大值，因此我們不停的取出堆樹的根，就能夠得到一個有序的數列。在取出根之后，我們根據最大堆的性質，對這個堆進行轉換（使其有一個新的根），這個操作的耗時非常少，因此堆排的效率還是非常高的。

優先隊列的應用更為廣泛。比如，我們工作時通常會先選擇那些最為重要最為緊急的事件來先做，而不是那些很早就安排下來的任務。我們可以將這些任務建立起一個堆的模型，使用最大堆，節點存儲的值就是任務的緊急程序。每一次做完一個任務，我們都能馬上知道下一個緊急的任務是什么，這就是堆的用處。

3 Huffman編碼樹endprint

3.1 定義

首先我們要知道一個叫做Huffman編碼的東西。他將會為字母分配代碼，代碼長度取決于字幕的相對使用頻率或者“權重”。每個字母的Huffman編碼是從Huffman樹的滿二叉樹種得到的。Huffman編碼樹的每個葉節點對應一個字幕，葉節點的權重就是它對應字幕的出現頻率，具體如圖2。

我們在為每一個字母編碼時，從根節點開始，到某一個葉節點結束經過的路徑就是其編碼，往左則為0，往右則為1。上圖中，D的編碼就是101，K的編碼就是111101?？梢钥吹?，使用頻率越小的字母編碼越長，而使用頻率較大的字母編碼也較短。這是符合我們平時的生活規律的，越是常見的東西，我們就越是希望能夠用簡單的名字來稱呼它。

3.2 應用

Huffman樹以及Huffman編碼已經被廣泛的運用在計算機通信以及解壓縮這方面。在計算機通信中，我們需要節約通信的成本。對于使用頻繁的字母以及單詞來說，我們希望將其轉換成簡單編碼，這樣整個傳輸數據的大小就會有明顯的減少，也能夠提高傳輸的速度以及穩定性。

同時，在壓縮這方面，其本身就希望將復雜的內容用簡單的編碼來表示。應用的原理和計算機通信是類似的，目前市面上較為常見的解壓縮軟件都應用了Huffman編碼來實現。

4 平衡二叉樹

對于平衡二叉樹，最為常見的是AVL樹和紅黑數。兩者在定義上都是比較類似的，區別就在于為了保持“平衡”而采用的操作。

4.1 定義

所謂平衡二叉樹，顧名思義，就是平衡的二叉樹。其可以看成是帶有如下特性的BST：對于樹結構中的每一個節點，其左右子樹的高度最多相差一層。只要維持這個特性，如果樹中一共包含有n個節點，那么它的深度最大為logn（如果不是平衡的，那么深度有可能是n）。這樣一來，我們在最糟糕情況下的時間復雜度也是O（logn）了。而如果僅僅是BST的話，最糟糕情況下的時間復雜度為0（n）。

當然，為了保持平衡，我們在插入和刪除一些節點之后必須更新這棵平衡二叉樹。AVL樹和紅黑數的更新方法是不同的，感興趣的讀者可以自行研究。

4.2 應用

平衡二叉樹一般用在開發環境中的各種庫函數中以及操作系統中。在Java中，集合TreeSet和TreeMap，C++ STL中的set，map都是通過紅黑樹來進行管理的。除此之外，紅黑書在操作系統中虛擬內存的管理這方面也有所作為。

5 其他的樹狀結構

除了上述的幾種比較常見的樹狀結構之外，生活中還有許許多多其他的樹被應用著。比如伸展樹，B+樹等。這些樹的定義，結構和操作都相對而言比較復雜，因此不在本文中闡述。

參考文獻

[1]Clifford A.Shaffer. Data Structures and Algorithm Analysis in C++ Third Edition[M].電子工業出版社，2013.endprint