紅黑樹插入演算法

A. C++中set的插入和查找 與二分查找對比 效率如何

Set的底層是用的紅黑樹。而數組就是順序表。這兩種數據結構優劣不同。
如果已知數據有序，那麼順序表的二分查找當然最快。但是順序表的插入性能極差，比如我要在頭部插入一個數據，則要吧所有的數據後移一格，開銷極大。紅黑樹則平衡了插入性能和查找性能。所以就有你看到的數據了，set的時間空間性能都比較差。
順序復制數組，不涉及到插入，所以數組很快。但是插入，刪除的話，紅黑樹需要一些時間來調整結構，所以有時間和空間的開銷。
如果你有這樣的一批數據，數量比較大，假設25w左右，他們需要頻繁的發生插入，刪除，以及查找工作，那麼數組就無法處理了，紅黑樹則是更好的選擇。
你可以研究一下紅黑樹的性質，就很容易理解了。

如果有不清楚的地方請追問。

B. 請問java中HashMap是怎麼實現的，還有treeMap的實現原理是紅黑樹，請解釋一下紅黑樹

參考資料的網頁上有比較的代碼,你可以仔細看下~~~

java中HashMap,LinkedHashMap,TreeMap，HashTable的區別
java為數據結構中的映射定義了一個介面java.util.Map;它有四個實現類,分別是HashMap Hashtable LinkedHashMap 和TreeMap
Map主要用於存儲健值對，根據鍵得到值，因此不允許鍵重復(重復了覆蓋了),但允許值重復。
Hashmap 是一個最常用的Map,它根據鍵的HashCode 值存儲數據,根據鍵可以直接獲取它的值，具有很快的訪問速度，遍歷時，取得數據的順序是完全隨機的。HashMap最多隻允許一條記錄的鍵為Null;允許多條記錄的值為 Null;HashMap不支持線程的同步，即任一時刻可以有多個線程同時寫HashMap;可能會導致數據的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。
Hashtable與 HashMap類似,它繼承自Dictionary類，不同的是:它不允許記錄的鍵或者值為空;它支持線程的同步，即任一時刻只有一個線程能寫Hashtable,因此也導致了 Hashtable在寫入時會比較慢。
LinkedHashMap保存了記錄的插入順序，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的.也可以在構造時用帶參數，按照應用次數排序。在遍歷的時候會比HashMap慢，不過有種情況例外，當HashMap容量很大，實際數據較少時，遍歷起來可能會比LinkedHashMap慢，因為LinkedHashMap的遍歷速度只和實際數據有關，和容量無關，而HashMap的遍歷速度和他的容量有關。
TreeMap實現SortMap介面，能夠把它保存的記錄根據鍵排序,默認是按鍵值的升序排序，也可以指定排序的比較器，當用Iterator 遍歷TreeMap時，得到的記錄是排過序的。

一般情況下，我們用的最多的是HashMap,HashMap裡面存入的鍵值對在取出的時候是隨機的,它根據鍵的HashCode值存儲數據,根據鍵可以直接獲取它的值，具有很快的訪問速度。在Map 中插入、刪除和定位元素，HashMap 是最好的選擇。
TreeMap取出來的是排序後的鍵值對。但如果您要按自然順序或自定義順序遍歷鍵，那麼TreeMap會更好。
LinkedHashMap 是HashMap的一個子類，如果需要輸出的順序和輸入的相同,那麼用LinkedHashMap可以實現,它還可以按讀取順序來排列，像連接池中可以應用。

C. 關於演算法導論

概念：

紅黑樹是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。它是在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操作的支持)。

背景和術語：
紅黑樹是一種特定類型的二叉樹，它是在計算機科學中用來組織數據比如數字的塊的一種結構。所有數據塊都存儲在節點中。這些節點中的某一個節點總是擔當啟始位置的功能，它不是任何節點的兒子；我們稱之為根節點或根。它有最多兩個"兒子"，都是它連接到的其他節點。所有這些兒子都可以有自己的兒子，以此類推。這樣根節點就有了把它連接到在樹中任何其他節點的路徑。

如果一個節點沒有兒子，我們稱之為葉子節點，因為在直覺上它是在樹的邊緣上。子樹是從特定節點可以延伸到的樹的某一部分，其自身被當作一個樹。在紅黑樹中，葉子被假定為 null 或空。

由於紅黑樹也是二叉查找樹，它們當中每一個節點都的比較值都必須大於或等於在它的左子樹中的所有節點，並且小於或等於在它的右子樹中的所有節點。這確保紅黑樹運作時能夠快速的在樹中查找給定的值。
用途和好處：
紅黑樹和AVL樹一樣都對插入時間、刪除時間和查找時間提供了最好可能的最壞情況擔保。這不只是使它們在時間敏感的應用如即時應用(real time application)中有價值，而且使它們有在提供最壞情況擔保的其他數據結構中作為建造板塊的價值；例如，在計算幾何中使用的很多數據結構都可以基於紅黑樹。

紅黑樹在函數式編程中也特別有用，在這里它們是最常用的持久數據結構之一，它們用來構造關聯數組和集合，在突變之後它們能保持為以前的版本。除了O(log n)的時間之外，紅黑樹的持久版本對每次插入或刪除需要O(log n)的空間。

紅黑樹是 2-3-4樹的一種等同。換句話說，對於每個 2-3-4 樹，都存在至少一個數據元素是同樣次序的紅黑樹。在 2-3-4 樹上的插入和刪除操作也等同於在紅黑樹中顏色翻轉和旋轉。這使得 2-3-4 樹成為理解紅黑樹背後的邏輯的重要工具，這也是很多介紹演算法的教科書在紅黑樹之前介紹 2-3-4 樹的原因，盡管 2-3-4 樹在實踐中不經常使用。
屬性：
紅黑樹是每個節點都有顏色特性的二叉查找樹，顏色的值是紅色或黑色之一。除了二叉查找樹帶有的一般要求，我們對任何有效的紅黑樹加以如下增補要求:

1.節點是紅色或黑色。

2.根是黑色。

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

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

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

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

操作：
在紅黑樹上只讀操作不需要對用於二叉查找樹的操作做出修改，因為它也二叉查找樹。但是，在插入和刪除之後，紅黑屬性可能變得違規。恢復紅黑屬性需要少量(O(log n))的顏色變更(這在實踐中是非常快速的)並且不超過三次樹旋轉(對於插入是兩次)。這允許插入和刪除保持為 O(log n) 次，但是它導致了非常復雜的操作。

D. 紅黑樹的用途

紅黑樹用在關聯數組、字典的實現上。需要的空間比散列表小。 任何鍵值對應,需要隨機存儲和鍵有序的情況都可以用。

E. 為什麼工程中都用紅黑樹，而不是其他平衡二叉樹

紅黑樹和平衡二叉樹區別如下：
1、紅黑樹放棄了追求完全平衡，追求大致平衡，在與平衡二叉樹的時間復雜度相差不大的情況下，保證每次插入最多隻需要三次旋轉就能達到平衡，實現起來也更為簡單。
2、平衡二叉樹追求絕對平衡，條件比較苛刻，實現起來比較麻煩，每次插入新節點之後需要旋轉的次數不能預知。

平衡二叉樹又被稱為AVL樹（有別於AVL演算法），且具有以下性質：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。構造與調整方法 平衡二叉樹的常用演算法有紅黑樹、AVL、Treap等。 最小二叉平衡樹的節點的公式如下 F(n)=F(n-1)+F(n-2)+1 這個類似於一個遞歸的數列，可以參考Fibonacci數列，1是根節點，F(n-1)是左子樹的節點數量，F(n-2)是右子樹的節點數量。

F. 紅黑樹如何執行修改操作

紅黑樹解釋起來比較麻煩，裡面有一些樹節點的旋轉工作，我有編好的程序，也是搞了n多天才搞定的。你先看看（代碼是C++的）。裡面實現了其節點插入、刪除、遍歷、前驅、後繼等介面。

程序太長，沒法拷貝過來，到我的博客去看吧。

如果程序沒法理解，請查看麻省理工的《演算法導論》中文版關於二叉查找樹和紅黑樹的章節，裡面有詳細介紹和很多偽代碼，我的代碼就是參考偽代碼寫出來的。

=============最新回復==============

不知道你所說的修改是什麼意思，是修改衛星數據還是修改key值？
如果是修改衛星數據，那麼不需要改動樹結構；
如果是修改key值，那麼愚以為，刪除和插入兩個操作相加是最好的辦法，因為即使兩者操作疊加，時間復雜度也不會超過log(n)

麻省理工的《演算法導論》中文版卓越網上有熱賣哦：-）

G. 只有左樹節點是紅樹的紅黑樹與演算法里介紹的紅黑樹有何區別

只有左樹節點是紅樹的紅黑樹與演算法里介紹的紅黑樹有何區別
因為插入之前所有根至外部節點的路徑上黑色節點數目都相同，所以如果插入的節點是黑色肯定錯誤（黑色節點數目不相同），而相對的插入紅節點可能會也可能不會違反「沒有連續兩個節點是紅色」這一條件，所以插入的節點為紅色，如果違反條件再調整
紅黑樹的操作時間跟二叉查找樹的時間復雜度是一樣的，執行查找、插入、刪除等操作的時間復雜度為O（logn）。
紅黑樹是特殊的AVL樹，遵循紅定理和黑定理 紅定理：不能有兩個相連的紅節點 黑定理：根節點必須是黑節點，而且所有節點通向NULL的路徑上，所經過的黑節點的個數必須相等

H. 為什麼像map，set都用紅黑樹來實現

STL中List,Vector,Map,Set的理解2009年07月11日 星期六 21:27List封裝了鏈表,Vector封裝了數組, list和vector得最主要的區別在於vector使用連續內存存儲的，他支持[]運算符，而list是以鏈表形式實現的，不支持[]。Vector對於隨機訪問的速度很快，但是對於插入尤其是在頭部插入元素速度很慢，在尾部插入速度很快。List對於隨機訪問速度慢得多，因為可能要遍歷整個鏈表才能做到，但是對於插入就快的多了，不需要拷貝和移動數據，只需要改變指針的指向就可以了。另外對於新添加的元素，Vector有一套演算法，而List可以任意加入。Map,Set屬於標准關聯容器，使用了非常高效的平衡檢索二叉樹：紅黑樹，他的插入刪除效率比其他序列容器高是因為不需要做內存拷貝和內存移動，而直接替換指向節點的指針即可。Set和Vector的區別在於Set不包含重復的數據。Set和Map的區別在於Set只含有Key，而Map有一個Key和Key所對應的Value兩個元素。Map和Hash_Map的區別是Hash_Map使用了Hash演算法來加快查找過程，但是需要更多的內存來存放這些Hash桶元素，因此可以算得上是採用空間來換取時間策略。

I. 平衡樹的主要演算法

紅黑樹的平衡是在插入和刪除的過程中取得的。對一個要插入的數據項，插入程序要檢查不會破壞樹一定的特徵。如果破壞了，程序就會進行糾正，根據需要更改樹的結構。通過維持樹的特徵，保持了樹的平衡。
紅黑樹有兩個特徵：
(1) 節點都有顏色
(2) 在插入和刪除過程中，要遵循保持這些顏色的不同排列的規則。
紅黑規則：
1. 每一個節點不是紅色的就是黑色的
2. 根總是黑色的
3. 如果節點是紅色的，則它的子節點必須是黑色的（反之不一定成立）
4. 從根到葉節點或空子節點的每條路徑，必須包含相同數目的黑色節點。
（空子節點是指非葉節點可以接子節點的位置。換句話說，就是一個有右子節點的節點可能接左子節點的位置，或是有左子節點的節點可能接右子節點的位置） AVL樹，它或者是一顆空二叉樹，或者是具有下列性質的二叉樹：
(1) 其根的左右子樹高度之差的絕對值不能超過1；
(2) 其根的左右子樹都是二叉平衡樹。
AVL樹查找的時間復雜度為O(logN)，因為樹一定是平衡的。但是由於插入或刪除一個節點時需要掃描兩趟樹，依次向下查找插入點，依次向上平衡樹，AVL樹不如紅黑樹效率高，也不如紅黑樹常用。
AVL樹插入的C++代碼： template<classT>ResultCodeAVLTree<T>::Insert(AVLNode<T>*&p,T&x,bool&unBalanced)...{ResultCoderesult=Success;if(p==null)...{//插入新節點p=newAVLNode<T>(x);unBalanced=true;}elseif(x<p->element)...{//新節點插入左子樹result=Insert(p->lChild,x,unBalanced);if(unBanlanced)...{switch(p->bF)...{case-1:p->bF=0;unBalanced=false;break;case0:p->bF=1;break;case1:LRotation(p,unBalanced);}}}elseif(x==p->element)...{//有重復元素，插入失敗unBalanced=false;x=p->element;result=Duplicate;}else...{//新節點插入右子樹result=Insert(p->rChild,x,unBalanced);if(unBalanced)...{switch(p->bF)...{case1:p->bF=0;unBalanced=false;break;case0:p->bF=-1;break;case-1:RRotation(p,unBalanced);}}}returnresult;}template<classT>voidAVLTree<T>::LRotation(AVLNode<T>*&s,bool&unBalanced)...{AVLNode<T>*u,*r=s->lChild;if(r->bF==1)...{//LL旋轉s->lChild=r->rChild;r->rChild=s;s->bF=0;s=r;//s指示新子樹的根}else...{//LR旋轉u=r->rChild;r->rChild=u->lChild;u->lChild=r;s->lChild=u->rChild;u->rChild=s;switch(u->bF)...{case1:s->bF=-1;r->bF=0;break;case0:s->bF=r->bF=0;break;case-1:s->bF=0;r->bF=1;}s=u;//s指示新子樹的根}s->bF=0;//s的平衡因子為0unBalanced=false;//結束重新平衡操作}通常我們使用二叉樹的原因是它可以用O（logn）的復雜度來查找一個數，刪除一個數，對吧？？可是有時候會發現樹會退化，這個就可能使O（logn）->O（n）的了，那麼還不如用直接搜一次呢！！所以我們就要想辦法使一棵樹平衡。而我僅僅看了（AVL）的那個，所以也僅僅能說（AVL）的那個，至於（TREAP），我還不懂，如果你們知道演算法的話，歡迎告訴我~！謝謝~
首先引入一個變數，叫做平衡因子（r），節點X的r就表示x的左子樹的深度-右子樹的深度。然後我們要保證一棵樹平衡，就是要保證左右子樹的深度差小於等於1.所以r的取值能且僅能取0，-1，1.
其次，我要介紹旋轉，旋轉有兩種方式，就是左旋（順時針旋轉）和右旋（逆時針旋轉）。
左旋（左兒子代替根）：即用左兒子取代根，假設我們要旋轉以X為根，LR分別為X的左右兒子，那麼我們只需要把L的右兒子取代X的左兒子，然後把更新後的X賦值為L的右兒子，就可以了。
右旋（右兒子代替根）：即用右兒子取代根，假設我們要旋轉以X為根，LR分別為X的左右兒子，那麼我們只需要把R的左兒子取代X的右兒子，然後把更新後的X賦值為R的左兒子，就可以了。 Size Balanced Tree(SBT平衡樹）是2007年Winter Camp上由我國著名OI選手陳啟峰發布的他自己創造的數據結構。相比於一般的平衡樹，此平衡樹具有的特點是：快速（遠超Treap，超過AVL)、代碼簡潔、空間小（是線段樹的1/4左右）、便於調試和修改等優勢。
與一般平衡搜索樹相比，該數據結構只靠維護一個Size來保持樹的平衡，通過核心操作Maintain(修復）使得樹的修改平攤時間為O(1)。因而大大簡化代碼實現復雜度、提高運算速度。
參見網路SBT。 平衡樹的一種，每次將待操作節點提到根，每次操作時間復雜度為O(logn)。見伸展樹。 constintSPLAYmaxn=200005;constintSPLAYinf=100000000;structSplay_Node{intl,r,fa,v,sum;};structSplay{Splay_Nodet[SPLAYmaxn];introot,tot;voidcreate(){root=1,tot=2;t[1].v=-SPLAYinf;t[2].v=SPLAYinf;t[1].r=t[1].sum=2;t[2].fa=t[2].sum=1;}voipdate(intnow){t[now].sum=t[t[now].l].sum+t[t[now].r].sum+1;}voidleft(intnow){intfa=t[now].fa;t[now].fa=t[fa].fa;if(t[t[fa].fa].l==fa)t[t[fa].fa].l=now;if(t[t[fa].fa].r==fa)t[t[fa].fa].r=now;t[fa].fa=now;t[fa].r=t[now].l;t[t[now].l].fa=fa;t[now].l=fa;up(fa);}voidright(intnow){intfa=t[now].fa;t[now].fa=t[fa].fa;if(t[t[fa].fa].l==fa)t[t[fa].fa].l=now;if(t[t[fa].fa].r==fa)t[t[fa].fa].r=now;t[fa].fa=now;t[fa].l=t[now].r;t[t[now].r].fa=fa;t[now].r=fa;update(fa);}voidsplay(intnow,intFA=0){while(t[now].fa!=FA){intfa=t[now].fa;if(t[fa].fa==FA)if(t[fa].l==now)right(now);elseleft(now);elseif(t[t[fa].fa].l==fa)if(t[fa].l==now)right(fa),right(now);elseleft(now),right(now);elseif(t[fa].l==now)right(now),left(now);elseleft(fa),left(now);}update(now);if(!FA)root=now;}intlower_bound(intv){intans=0,la=0;for(intnow=root;now;){la=now;if(t[now].v>=v)ans=now,now=t[now].l;elsenow=t[now].r;}splay(la);returnans;}voidinsert(intv){for(intnow=root;;){++t[now].sum;if(t[now].v>=v)if(t[now].l)now=t[now].l;else{t[now].l=++tot;t[tot].sum=1;t[tot].fa=now;t[tot].v=v;splay(tot);return;}elseif(t[now].r)now=t[now].r;else{t[now].r=++tot;t[tot].sum=1;t[tot].fa=now;t[tot].v=v;splay(tot);return;}}}intget_lower(inta){splay(a);for(a=t[a].l;t[a].r;a=t[a].r);returna;}intget_upper(inta){splay(a);for(a=t[a].r;t[a].l;a=t[a].l);returna;}intget_rank(inta){splay(a);returnt[t[a].l].sum;}voiddel(intl,intr){l=get_lower(l);r=get_upper(r);splay(l);splay(r,l);t[r].l=0;update(r);update(l);}intget_kth(intk){++k;for(intnow=root;;){if(t[t[now].l].sum==k-1)returnnow;if(t[t[now].l].sum>=k)now=t[now].l;elsek-=t[t[now].l].sum+1,now=t[now].r;}}};

J. 紅黑樹和平衡二叉樹 區別

紅黑樹和平衡二叉樹的主要區別如下：
平衡二叉樹（AVL）樹是嚴格的平衡二叉樹，平衡條件必須滿足（所有節點的左右子樹高度差不超過1）。不管我們是執行插入還是刪除操作，只要不滿足上面的條件，就要通過旋轉來保持平衡，而的英文旋轉非常耗時的。所以平衡二叉樹（AVL）適合用於插入與刪除次數比較少，但查找多的情況。
紅黑樹在二叉查找樹的基礎上增加了著色和相關的性質使得紅黑樹相對平衡，從而保證了紅黑樹的查找、插入、刪除的時間復雜度最壞為O(log
n)。所以紅黑樹適用於搜索，插入，刪除操作較多的情況。
(10)紅黑樹插入演算法擴展閱讀：
平衡二叉樹在Windows
NT內核中廣泛存在。
紅黑樹的應用：
1、在C
++的STL中，地圖和集都是用紅黑樹實現的；
2、著名的Linux的的進程調度完全公平調度程序，用紅黑樹管理進程式控制制塊，進程的虛擬內存區域都存儲在一顆紅黑樹上，每個虛擬地址區域都對應紅黑樹的一個節點，左指針指向相鄰的地址虛擬存儲區域，右指針指向相鄰的高地址虛擬地址空間；
3、IO多路復用的epoll的的的實現採用紅黑樹組織管理的sockfd，以支持快速的增刪改查；
4、Nginx的的的中用紅黑樹管理定時器，因為紅黑樹是有序的，可以很快的得到距離當前最小的定時器；
5、Java中的TreeMap中的實現。
參考資料：
網路-平衡二叉樹
網路-紅黑樹