搜索部分非平衡樹的時(shí)間介于O(N)和O(logN)之間，取決樹的不平衡程度，平衡樹O(logN)
紅黑樹規(guī)則
1.每個(gè)節(jié)點(diǎn)不是紅色就是黑色的
2.根總是黑色
3.每個(gè)葉結(jié)點(diǎn)（葉結(jié)點(diǎn)即指樹尾端NIL指針或NULL結(jié)點(diǎn)）都是黑的
4.如果一個(gè)結(jié)點(diǎn)是紅的，那么它的兩個(gè)兒子都是黑的
5.對(duì)于任意結(jié)點(diǎn)而言，其到葉結(jié)點(diǎn)樹尾端NIL指針的每條路徑都包含相同數(shù)目的黑結(jié)點(diǎn)
樹的選擇
左旋
當(dāng)在某個(gè)結(jié)點(diǎn)pivot上，做左旋操作時(shí)，左旋以pivot到Y(jié)之間的鏈為“支軸”進(jìn)行，它使Y成為該子樹的新根，而Y的左孩子b則成為pivot的右孩子
右旋
紅黑樹的插入和插入修復(fù)
1.如果插入的是根結(jié)點(diǎn)，由于原樹是空樹，此情況只會(huì)違反性質(zhì)2，因此直接把此結(jié)點(diǎn)涂為黑色
2.如果插入的結(jié)點(diǎn)的父結(jié)點(diǎn)是黑色，由于此不會(huì)違反性質(zhì)2和性質(zhì)4，紅黑樹沒有被破壞，所以此時(shí)什么也不做。
3.當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色，祖父結(jié)點(diǎn)的另一個(gè)子結(jié)點(diǎn)（叔叔結(jié)點(diǎn)）是紅色：將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)涂黑，祖父結(jié)點(diǎn)涂紅，把當(dāng)前結(jié)點(diǎn)指向祖父節(jié)點(diǎn)，從新的當(dāng)前節(jié)點(diǎn)重新開始算法
4.當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色,叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右子（插入節(jié)點(diǎn)N是其父節(jié)點(diǎn)P的右孩子，而父節(jié)點(diǎn)P又是其父節(jié)點(diǎn)的左孩子）：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)做為新的當(dāng)前節(jié)點(diǎn)，以新當(dāng)前節(jié)點(diǎn)為支點(diǎn)左旋
5.當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色,叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子（要插入的節(jié)點(diǎn)N 是其父節(jié)點(diǎn)的左孩子，而父節(jié)點(diǎn)P又是其父G的左孩子）：父節(jié)點(diǎn)變?yōu)楹谏?，祖父?jié)點(diǎn)變?yōu)榧t色，在祖父節(jié)點(diǎn)為支點(diǎn)右旋
紅黑樹的刪除和刪除修復(fù)
1.根結(jié)點(diǎn)
2.當(dāng)前節(jié)點(diǎn)是黑且兄弟節(jié)點(diǎn)為紅色(此時(shí)父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)分為黑)：把父節(jié)點(diǎn)染成紅色，把兄弟結(jié)點(diǎn)染成黑色，父節(jié)點(diǎn)為支點(diǎn)左旋，之后重新進(jìn)入算法（我們只討論當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)左孩子時(shí)的情況）
3.當(dāng)前節(jié)點(diǎn)是黑且兄弟是黑色且兄弟節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)全為黑色：把當(dāng)前節(jié)點(diǎn)和兄弟節(jié)點(diǎn)中抽取一重黑色追加到父節(jié)點(diǎn)上，把父節(jié)點(diǎn)當(dāng)成新的當(dāng)前節(jié)點(diǎn)，重新進(jìn)入算法
4.當(dāng)前節(jié)點(diǎn)顏色是黑，兄弟節(jié)點(diǎn)是黑色，兄弟的左子是紅色，右子是黑色：把兄弟結(jié)點(diǎn)染紅，兄弟左子節(jié)點(diǎn)染黑，之后再在兄弟節(jié)點(diǎn)為支點(diǎn)解右旋，之后重新進(jìn)入算法
5.當(dāng)前節(jié)點(diǎn)顏色是黑，它的兄弟節(jié)點(diǎn)是黑色，但是兄弟節(jié)點(diǎn)的右子是紅色，兄弟節(jié)點(diǎn)左子的顏色任意:把兄弟節(jié)點(diǎn)染成當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)的顏色，把當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)染成黑色，兄弟節(jié)點(diǎn)右子染成黑色，之后以當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋
鏈接：
http://blog.csdn.net/chenhuajie123/article/details/11951777
