這兩條性質(zhì)確保該樹的高度為logN，所以是平衡樹。

紅黑樹是每個節(jié)點都帶顏色的樹，節(jié)點顏色或是紅色或是黑色，紅黑樹是一種查找樹。紅黑樹有一個重要的性質(zhì)，從根節(jié)點到葉子節(jié)點的最長的路徑不多于最短的路徑的長度的兩倍。對于紅黑樹，插入，刪除，查找的復(fù)雜度都是O（log N）。

刪除節(jié)點時先要找到頂替的節(jié)點，如果刪去的節(jié)點是黑色則破壞了性質(zhì)2，也需要調(diào)整。調(diào)整的思想也同前面類似，把這個黑色賦予頂替節(jié)點，則頂替節(jié)點相當(dāng)于有兩重黑色，然后將它的兩重黑色向上推，一直推到根，再從根推到外面去了。

平衡二叉樹的調(diào)整算法幾乎所有數(shù)據(jù)結(jié)構(gòu)的書都有呀，根據(jù)破壞平衡性的加入點，將插入操作分為了四種，分別是LL、LR、RR、RL。每種引起不平衡的插入位置，均有相應(yīng)的調(diào)整算法。

AVL樹又稱高度平衡的二叉搜索樹,是1962年由兩位俄羅斯的數(shù)學(xué)家G.M.Adel'son-Vel,sky和E.M.Landis提出 的.引入二叉樹的目的是為了提高二叉樹的搜索的效率,減少樹的平均搜索長度.為此,就必須每向二叉樹插入 一個結(jié)點時調(diào)整樹的結(jié)構(gòu),使得二叉樹搜索保持平衡,從而可能降低樹的高度,減少的平均樹的搜索長度. 

AVL樹的定義:

 一棵AVL樹滿足以下的條件: 

1>它的左子樹和右子樹都是AVL樹 

2>左子樹和右子樹的高度差不能超過1 從條件1可能看出是個遞歸定義,如GNU一樣. 

性質(zhì): 

1>一棵n個結(jié)點的AVL樹的其高度保持在0(log2(n)),不會超過3/2log2(n+1) 

2>一棵n個結(jié)點的AVL樹的平均搜索長度保持在0(log2(n)). 

3>一棵n個結(jié)點的AVL樹刪除一個結(jié)點做平衡化旋轉(zhuǎn)所需要的時間為0(log2(n)).


# 紅黑樹是一種很有意思的平衡檢索樹。它的統(tǒng)計性能要好于平衡二叉樹(有些書籍根據(jù)作者姓名，Adelson- Velskii和Landis，將其稱為AVL-樹)，因此，紅黑樹在很多地方都有應(yīng)用。在C++ STL中，很多部分(目前包括 set, multiset, map, multimap)應(yīng)用了紅黑樹的變體(SGI STL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支持)。  
#   
# 紅黑樹的定義如下：  
#   
#   
# 滿足下列條件的二叉搜索樹是紅黑樹  
#   
#     * 每個結(jié)點要么是“紅色”，要么是“黑色”(后面將說明)  
#     * 所有的葉結(jié)點都是空結(jié)點，并且是“黑色”的  
#     * 如果一個結(jié)點是“紅色”的，那么它的兩個子結(jié)點都是“黑色”的  
#     * (注:也就是說，如果結(jié)點是黑色的，那么它的子節(jié)點可以是紅色或者是黑色的)。  
#     * 結(jié)點到其子孫結(jié)點的每條簡單路徑都包含相同數(shù)目的“黑色”結(jié)點  
#     * 根結(jié)點永遠(yuǎn)是“黑色”的  

AVL 樹是高度平衡的，頻繁的插入和刪除，會引起頻繁的reblance，導(dǎo)致效率下降
紅黑樹不是高度平衡的，算是一種折中，插入最多兩次旋轉(zhuǎn)，刪除最多三次旋轉(zhuǎn)