標籤：

樹型結構

09-23
樹型結構

樹型結構的基本概念

對大量的輸入數據，鏈表的線性訪問時間太慢，不宜使用。本文探討另外一種重要的數據結構----樹，其大部分時間可以保證操作的運行平均時間複雜度為O(logN)，第一部分先來看一下樹的一些預備知識。

首先看一下樹形結構的樣子，下圖代表的是樹型結構的一般形態：

由上圖看得出樹是一些節點的集合，總結一下樹的一些基本概念：

1、結點：樹中的數據元素都稱之為結點

2、根：最上面的結點稱之為根，一顆樹只有一個根且由根發展而來，從另外一個角度來說，每個結點都可以認為是其子樹的根

3、父親：結點的上層結點，如圖中，結點K的父親是E、結點L的父親是G

4、兄弟：具有相同父親的結點稱為兄弟，圖中F、G、H互為兄弟

5、結點的度：結點所擁有的子樹的個數稱之為結點的度，如結點B的度為3

6、樹葉：度為0的結點，也叫作終端結點，圖中D、K、F、L、H、I、J都是樹葉

7、分支結點：度不為0的結點，也叫作非終端結點或內部結點，圖中根、A、B、C、E、G都是分支結點

8、結點的層次：從根節點到樹中某結點所經路徑上的分支樹稱為該結點的層次，根節點的層次規定為1，其餘結點的層次等於其父親結點的層次+1

9、樹的深度：樹中結點的最大層次數，圖中樹的深度為4

二叉樹

上面的是樹的一般形態，下面看一下二叉樹。二叉樹是一棵樹，其中每個結點都不能有多於兩個子樹。

下圖展示了一顆二叉樹：

二叉樹的一個性質是一顆平均二叉樹的深度要比及結點個數N小得多，這個性質很重要，尤其對於特殊類型的二叉樹即二叉查找樹而言，其深度的平均值是O(logN)，這將大大降低查找時的時間複雜度。

當然，二叉樹在運用得不好的情況下的情況下是有嚴重的問題的，即：

樹的深度大到了N-1，這樣的情況是絕對不允許的，這種樹也被稱為不平衡樹。在下一部分的二叉查找樹說明完之後，會講讓二叉樹帶有自平衡條件，成為平衡樹。

二叉查找樹

二叉樹的一個重要應用是在它們查找中的使用。假設樹中的每個結點存儲一項數據，使得二叉樹成為二叉查找樹的性質是：對於樹中的每個結點X，它的左子樹中所有項的值小於X，而它的右子樹中所有項的值大於X，這意味著該樹所有的元素可以用某種一致的方式排序。

如下圖：

這就是一個二叉查找樹。但是如果我這麼修改一下：

這就不是一個二叉查找樹了，因為在根節點的左子樹中，有一個節點是11。

AVL樹

前面已經講到過了，在生成二叉樹/二叉查找樹的時候是非常容易失衡的，造成的最壞的情況就是一邊倒（只有左子樹/右子樹），這樣將會導致樹的檢索效率大大降低，所以為了維持二叉樹的平衡，大牛們提出了各種實現的演算法，如：AVL樹、節點大小平衡樹（SBT）、伸展樹、樹堆（Treap）、紅黑樹等等。

這裡講AVL樹----一種帶有平衡條件的二叉查找樹，這種平衡條件必須要容易保持，而且它保證樹的深度必須是O(logN)。

對於AVL樹來說，它的平衡必須滿足以下特徵之一：

1、空樹

2、每個結點的左子樹和右子樹深度最多差1

可以看一下下圖：

圖中，左邊的樹是AVL樹，右邊的樹不是。因為很顯然，從根結點7看起，右子樹的深度為1，而左子樹7-->2-->4-->5(3)這條路徑深度為3，不滿足每個結點的左子樹和右子樹深度最多差1的條件。

可以證明，一顆AVL樹的高度最多為1.44 * log(N + 2) - 1.328，但是實際上的高度只略大於logN。

紅黑樹

紅黑樹是對AVL樹的另一種變種。紅黑樹顧名思義就是結點是紅色或者黑色的平衡二叉樹，它通過顏色的約束來維持著二叉樹的平衡。下圖為一顆典型的二叉樹：

對於一顆有效的紅黑樹而言我們必須增加如下規則：

1、每個結點都只能是紅色或者黑色

2、根節點是黑色

3、每片葉子都是黑色的

4、如果一個結點是紅色的，則它的兩個子節點都是黑色的，也就是說在一條路徑上不能出現相鄰的兩個紅色結點

5、從任意一個結點到其每個葉子的所有路徑都包含著相同數目的黑色結點

這些約束強制了紅黑樹的關鍵性質：從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長。結果就是這棵樹大致上是平衡的，因為插入、刪除和查找某個值得最壞情況時間都要求與樹的高度成比例，這個高度理論上限允許紅黑樹只在最壞情況下都是高效的。

再具體就不說了，可以參看cnblogs.com/yangecnu/p/，對紅黑樹的講解寫得非常好。

對了，TreeMap和TreeSet就是紅黑樹的典型實現。


推薦閱讀：

TAG:數據結構 | 樹數據結構 |