昨晚看到map 和 hash_map 對其中的紅黑樹概念模糊了。于是晚上翻了下書，以此為記。

1.平衡二叉樹：　當且僅當兩個子樹的高度差不超過1時，這個樹是平衡二叉樹。（同時是排序二叉樹）

?平衡二叉樹，又稱AVL樹。它或者是一棵空樹，或者是具有下列性質的二叉樹：

它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差之差的絕對值不超過1.

常用算法有：紅黑樹、AVL樹、Treap等。

　　平衡二叉樹的調整方法

　　平衡二叉樹是在構造二叉排序樹的過程中，每當插入一個新結點時，首先檢查是否因插入新結點而破壞了二叉排序樹的平衡性，
若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的鏈接關系，進行相應的
旋轉，使之成為新的平衡子樹。具體步驟如下：

　?、?每當插入一個新結點，從該結點開始向上計算各結點的平衡因子，即計算該結點的祖先結點的平衡因子，
?若該結點的祖先結點的平衡因子的絕對值均不超過1，則平衡二叉樹沒有失去平衡，繼續插入結點；
?
　?、?若插入結點的某祖先結點的平衡因子的絕對值大于1，則找出其中最小不平衡子樹的根結點；

　?、?判斷新插入的結點與最小不平衡子樹的根結點的關系，確定是哪種類型的調整；

　?、?如果是LL型或RR型，只需應用扁擔原理旋轉一次，在旋轉過程中，如果出現沖突，應用旋轉優先原則調整沖突；如果是LR型或LR型，
?則需應用扁擔原理旋轉兩次，第一次最小不平衡子樹的根結點先不動，調整插入結點所在子樹，第二次再調整最小不平衡子樹，在旋
?轉過程中，如果出現沖突，應用旋轉優先原則調整沖突；
?
　?、?計算調整后的平衡二叉樹中各結點的平衡因子，檢驗是否因為旋轉而破壞其他結點的平衡因子，
?以及調整后的平衡二叉樹中是否存在平衡因子大于1的結點。
?
?
2.完全二叉樹(Complete Binary Tree)

　　若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層從右向左連續缺若干結點，這就是完全二叉樹。

3.滿二叉樹(Full Binary Tree)

　　一棵深度為h且有 2^h-1個結點的二叉樹。

4.紅黑樹

紅黑樹是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。

?它是在1972年由Rudolf Bayer發明的，他稱之為"對稱二叉B樹"，它現代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年寫的一篇
?論文中獲得的。它是復雜的，但它的操作有著良好的最壞情況運行時間，并且在實踐中是高效的:
?
?它可以在O(log n)時間內做查找，插入和刪除，這里的n 是樹中元素的數目。
?
　紅黑樹是一種很有意思的平衡檢索樹。

?它的統計性能要好于平衡二叉樹(有些書籍根據作者姓名，Adelson-Velskii和Landis，將其稱為AVL-樹)，
?
?因此，紅黑樹在很多地方都有應用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)應用了紅黑樹的變體(SGI STL中的紅黑樹有一些變化，
?
?這些修改提供了更好的性能，以及對set操作的支持)。

?紅黑樹是每個節點都有顏色特性的二叉查找樹，顏色的值是紅色或黑色之一。除了二叉查找樹帶有的一般要求，
?我們對任何有效的紅黑樹加以如下增補要求:
?
　　1.節點是紅色或黑色。

　　2.根是黑色。

　　3.每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

　　4.從每個葉子到根的所有路徑都包含相同數目的黑色節點。

　　這些約束強制了紅黑樹的關鍵屬性:

?從根到葉子的最長的可能路徑不大于最短的可能路徑的兩倍長。
?
?結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值都要求與樹的高度成比例的最壞情況時間，
?
?這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。
?
　在很多樹數據結構的表示中，一個節點有可能只有一個兒子，而葉子節點包含數據。

?用這種范例表示紅黑樹是可能的，但是這會改變一些屬性并使算法復雜。為此，本文中我們使用 "null 葉子"
?
?或"空(null)葉子"，如上圖所示，它不包含數據而只充當樹在此結束的指示。這些節點在繪圖中經常被省略，
?
?導致了這些樹好像同上述原則相矛盾，而實際上不是這樣。與此有關的結論是所有節點都有兩個兒子，盡管其中的一個或兩個可能是空葉子。