王維燁

摘要：本文主要介紹了數(shù)據(jù)結(jié)構(gòu)中的各種樹(shù)狀結(jié)構(gòu)，重點(diǎn)介紹了二叉搜索樹(shù)，其他還包括平衡二叉樹(shù)，紅黑樹(shù)，霍夫曼樹(shù)以及堆。此外，本文詳細(xì)解釋了二叉搜索樹(shù)的操作的時(shí)間復(fù)雜度。同時(shí)，我們將介紹各種樹(shù)形結(jié)構(gòu)在生活中的應(yīng)用。

關(guān)鍵詞：算法；樹(shù)狀結(jié)構(gòu)；應(yīng)用

中圖分類(lèi)號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2017）05-0147-02

在計(jì)算機(jī)世界中，有各種各樣的抽象數(shù)據(jù)結(jié)構(gòu)，包括數(shù)組，隊(duì)列，堆棧，鏈表等。這些數(shù)據(jù)結(jié)構(gòu)都可以轉(zhuǎn)換到現(xiàn)實(shí)生活中的各種問(wèn)題中去，以此能夠高效的解決一些問(wèn)題。在這些數(shù)據(jù)結(jié)構(gòu)中，被使用的較為廣泛的無(wú)疑是樹(shù)狀結(jié)構(gòu)。本文就將詳細(xì)介紹一下樹(shù)狀結(jié)構(gòu)。

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

樹(shù)狀結(jié)構(gòu)在現(xiàn)實(shí)生活中的使用也相當(dāng)廣泛。從計(jì)算機(jī)網(wǎng)絡(luò)到數(shù)據(jù)庫(kù)實(shí)現(xiàn)，樹(shù)狀結(jié)構(gòu)無(wú)時(shí)無(wú)刻的在提高我們的工作效率。本文也會(huì)介紹其在生活中的應(yīng)用，以引發(fā)讀者對(duì)計(jì)算機(jī)科學(xué)的興趣。

1 二叉檢索樹(shù)

我們首先介紹一下樹(shù)狀結(jié)構(gòu)中最為簡(jiǎn)單也是最為常見(jiàn)的一種樹(shù)：二叉檢索樹(shù)（Binary Search Tree）。

1.1 定義

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

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

同時(shí)，任意一個(gè)結(jié)點(diǎn)都有其深度，我們定義為根節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑長(zhǎng)度。而B(niǎo)ST的高度就是最深深度加1。

1.2 二叉檢索樹(shù)的搜索

對(duì)于一棵二叉檢索樹(shù)而言，其最重要的功能就是能夠快速的找到某一個(gè)節(jié)點(diǎn)的值。假設(shè)我們從根節(jié)點(diǎn)開(kāi)始，在BST中檢索K值。如果根節(jié)點(diǎn)存儲(chǔ)的值為K，則檢索結(jié)束。如果不是K，則必須檢索樹(shù)的更深一層。BST檢索的優(yōu)勢(shì)在于只需要檢索兩棵子樹(shù)的其中之一。如果K小于根節(jié)點(diǎn)的值，則只需要檢索左子樹(shù)，反之則檢索右子樹(shù)。這個(gè)過(guò)程將會(huì)一直持續(xù)到K被找到，或者到一個(gè)葉節(jié)點(diǎn)（沒(méi)有子樹(shù)）為止。如果到了一個(gè)葉節(jié)點(diǎn)，依然沒(méi)有發(fā)現(xiàn)K，則表示K不在該BST中。

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

1.3 二叉檢索樹(shù)的插入

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

與搜索類(lèi)似，插入操作的時(shí)間代價(jià)依賴(lài)于R的深度。因此，在平均情況下，插入操作的時(shí)間復(fù)雜度為O（logn）。

1.4 應(yīng)用

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

雖然二叉檢索樹(shù)在樹(shù)中的地位相當(dāng)?shù)母撸瞧涓蟮挠锰幵谟谘苌撕芏嗟钠胶舛鏄?shù)，這些樹(shù)在我們現(xiàn)實(shí)生活中大發(fā)光彩。下面我們也會(huì)介紹到，但在介紹的過(guò)程中，我們不再詳細(xì)說(shuō)明其各種操作的原理以及時(shí)間代價(jià)了。一方面其復(fù)雜程序不是本文可以說(shuō)明清楚的，另一方面我也希望將文章的重點(diǎn)放在應(yīng)用這一角度。

2 堆

2.1 定義

堆由兩條性質(zhì)來(lái)定義：首先，它是一棵完全二叉樹(shù)。其次，堆中存儲(chǔ)的數(shù)據(jù)是局部有序的，也就是說(shuō)，節(jié)點(diǎn)存儲(chǔ)的值與其子節(jié)點(diǎn)存儲(chǔ)的值存在著某種關(guān)系。這種關(guān)系可以分成兩類(lèi)，這兩類(lèi)關(guān)系也決定了兩種不同的堆。

最大堆：任意一個(gè)節(jié)點(diǎn)的值都大于或者等于任意一個(gè)子節(jié)點(diǎn)的值。根節(jié)點(diǎn)存儲(chǔ)著該樹(shù)中所有節(jié)點(diǎn)的最大值。

最小堆：任意一個(gè)節(jié)點(diǎn)的值都小于或者等于任意一個(gè)子節(jié)點(diǎn)的值。根節(jié)點(diǎn)存儲(chǔ)了該樹(shù)中所有節(jié)點(diǎn)的最小值。

這里我們需要弄清楚他和BST的區(qū)別。BST是定義了一組完全排序的節(jié)點(diǎn)，左邊節(jié)點(diǎn)的值都比右邊節(jié)點(diǎn)的值小。而堆僅僅實(shí)現(xiàn)了局部排序，當(dāng)一個(gè)節(jié)點(diǎn)是另一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)時(shí)，才可以確定這兩個(gè)節(jié)點(diǎn)的相對(duì)關(guān)系。

2.2 應(yīng)用

堆在生活中的應(yīng)用非常廣泛，最為常見(jiàn)的兩個(gè)就是排序和優(yōu)先隊(duì)列。

我們將一組無(wú)序的數(shù)列從小到大進(jìn)行排列，就需要使用最大堆。我們知道根節(jié)點(diǎn)存儲(chǔ)著該樹(shù)中所有節(jié)點(diǎn)的最大值，因此我們不停的取出堆樹(shù)的根，就能夠得到一個(gè)有序的數(shù)列。在取出根之后，我們根據(jù)最大堆的性質(zhì)，對(duì)這個(gè)堆進(jìn)行轉(zhuǎn)換（使其有一個(gè)新的根），這個(gè)操作的耗時(shí)非常少，因此堆排的效率還是非常高的。

優(yōu)先隊(duì)列的應(yīng)用更為廣泛。比如，我們工作時(shí)通常會(huì)先選擇那些最為重要最為緊急的事件來(lái)先做，而不是那些很早就安排下來(lái)的任務(wù)。我們可以將這些任務(wù)建立起一個(gè)堆的模型，使用最大堆，節(jié)點(diǎn)存儲(chǔ)的值就是任務(wù)的緊急程序。每一次做完一個(gè)任務(wù)，我們都能馬上知道下一個(gè)緊急的任務(wù)是什么，這就是堆的用處。

3 Huffman編碼樹(shù)endprint

3.1 定義

首先我們要知道一個(gè)叫做Huffman編碼的東西。他將會(huì)為字母分配代碼，代碼長(zhǎng)度取決于字幕的相對(duì)使用頻率或者“權(quán)重”。每個(gè)字母的Huffman編碼是從Huffman樹(shù)的滿(mǎn)二叉樹(shù)種得到的。Huffman編碼樹(shù)的每個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)一個(gè)字幕，葉節(jié)點(diǎn)的權(quán)重就是它對(duì)應(yīng)字幕的出現(xiàn)頻率，具體如圖2。

我們?cè)跒槊恳粋€(gè)字母編碼時(shí)，從根節(jié)點(diǎn)開(kāi)始，到某一個(gè)葉節(jié)點(diǎn)結(jié)束經(jīng)過(guò)的路徑就是其編碼，往左則為0，往右則為1。上圖中，D的編碼就是101，K的編碼就是111101?？梢钥吹?，使用頻率越小的字母編碼越長(zhǎng)，而使用頻率較大的字母編碼也較短。這是符合我們平時(shí)的生活規(guī)律的，越是常見(jiàn)的東西，我們就越是希望能夠用簡(jiǎn)單的名字來(lái)稱(chēng)呼它。

3.2 應(yīng)用

Huffman樹(shù)以及Huffman編碼已經(jīng)被廣泛的運(yùn)用在計(jì)算機(jī)通信以及解壓縮這方面。在計(jì)算機(jī)通信中，我們需要節(jié)約通信的成本。對(duì)于使用頻繁的字母以及單詞來(lái)說(shuō)，我們希望將其轉(zhuǎn)換成簡(jiǎn)單編碼，這樣整個(gè)傳輸數(shù)據(jù)的大小就會(huì)有明顯的減少，也能夠提高傳輸?shù)乃俣纫约胺€(wěn)定性。

同時(shí)，在壓縮這方面，其本身就希望將復(fù)雜的內(nèi)容用簡(jiǎn)單的編碼來(lái)表示。應(yīng)用的原理和計(jì)算機(jī)通信是類(lèi)似的，目前市面上較為常見(jiàn)的解壓縮軟件都應(yīng)用了Huffman編碼來(lái)實(shí)現(xiàn)。

4 平衡二叉樹(shù)

對(duì)于平衡二叉樹(shù)，最為常見(jiàn)的是AVL樹(shù)和紅黑數(shù)。兩者在定義上都是比較類(lèi)似的，區(qū)別就在于為了保持“平衡”而采用的操作。

4.1 定義

所謂平衡二叉樹(shù)，顧名思義，就是平衡的二叉樹(shù)。其可以看成是帶有如下特性的BST：對(duì)于樹(shù)結(jié)構(gòu)中的每一個(gè)節(jié)點(diǎn)，其左右子樹(shù)的高度最多相差一層。只要維持這個(gè)特性，如果樹(shù)中一共包含有n個(gè)節(jié)點(diǎn)，那么它的深度最大為logn（如果不是平衡的，那么深度有可能是n）。這樣一來(lái)，我們?cè)谧钤愀馇闆r下的時(shí)間復(fù)雜度也是O（logn）了。而如果僅僅是BST的話，最糟糕情況下的時(shí)間復(fù)雜度為0（n）。

當(dāng)然，為了保持平衡，我們?cè)诓迦牒蛣h除一些節(jié)點(diǎn)之后必須更新這棵平衡二叉樹(shù)。AVL樹(shù)和紅黑數(shù)的更新方法是不同的，感興趣的讀者可以自行研究。

4.2 應(yīng)用

平衡二叉樹(shù)一般用在開(kāi)發(fā)環(huán)境中的各種庫(kù)函數(shù)中以及操作系統(tǒng)中。在Java中，集合TreeSet和TreeMap，C++ STL中的set，map都是通過(guò)紅黑樹(shù)來(lái)進(jìn)行管理的。除此之外，紅黑書(shū)在操作系統(tǒng)中虛擬內(nèi)存的管理這方面也有所作為。

5 其他的樹(shù)狀結(jié)構(gòu)

除了上述的幾種比較常見(jiàn)的樹(shù)狀結(jié)構(gòu)之外，生活中還有許許多多其他的樹(shù)被應(yīng)用著。比如伸展樹(shù)，B+樹(shù)等。這些樹(shù)的定義，結(jié)構(gòu)和操作都相對(duì)而言比較復(fù)雜，因此不在本文中闡述。

參考文獻(xiàn)

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