1.平衡與非平衡樹
樹的平衡樹的平衡指的是：樹中每個節(jié)點的左邊后代的數(shù)目，應該和其右邊后代的數(shù)目大致相等棚放。對于隨機數(shù)構(gòu)成的二叉樹紊扬，一般來說是大致平衡的，但是對于有序的數(shù)據(jù)荣茫，二叉樹就嚴重不平衡了，極端情況下场靴，退化成為鏈表啡莉，其時間復雜度下降到 O(N)，而不再是平衡樹的O(logN)憎乙。
2.紅黑樹是什么以及特征
紅黑樹（R-B Tree）是什么紅黑樹是一種增加了某些特性的二叉搜索樹票罐，它可以保持樹的大致平衡叉趣。
大致思路是：在插入和刪除節(jié)點的時候泞边，檢查是否破壞了樹的一定的特
征，如果破壞了疗杉，就需要進行糾正阵谚，從而保持樹的平衡。
紅黑樹的特征 ：
1）節(jié)點都有顏色
2）在插入和刪除過程中烟具，要遵循保持這些顏色的不同排列的規(guī)則
3.紅黑樹的規(guī)則和修正手段
紅黑樹的規(guī)則（也稱紅黑規(guī)則）：
- 1）每個節(jié)點不是紅色就是黑色
- 2）根總是黑色
- 3）如果節(jié)點是紅色的梢什，那么它的子節(jié)點必須是黑色的（反之不必為真）
- 4）每個空子節(jié)點都是黑的
這里的空子節(jié)點指的是：對非葉子節(jié)點而言，本可能有朝聋，但實際沒有的那個子節(jié)點嗡午。比如一個節(jié)點只有右子節(jié)點，那么它空缺的左子節(jié)點就是空子節(jié)點冀痕。 - 5）從根到葉節(jié)點或“空子節(jié)點”的每條路徑荔睹，必須包含相同數(shù)目的黑色節(jié)點（這些黑色節(jié)點的數(shù)目也稱黑色高度）
紅黑樹的修正手段 ：
- 1）改變節(jié)點顏色
- 2）執(zhí)行旋轉(zhuǎn)操作
4.紅黑樹的旋轉(zhuǎn)
5.紅黑樹的節(jié)點插入算法，并代碼示例
紅黑樹的插入言蛇，前面跟二叉樹插入一樣僻他，就是從根節(jié)點向下查找節(jié)點要插入的位置，然后插入節(jié)點腊尚；插入節(jié)點過后吨拗，后面添加了這樣的操作：檢查樹是否平衡，如果不平衡，就要做修復劝篷，使樹重新變得平衡哨鸭。
插入新的節(jié)點，通常會設置這個節(jié)點為紅色娇妓，因為這樣違反紅黑規(guī)則的幾
率較小兔跌，插入節(jié)點后，有以下幾種情況：
- 1）如果插入的是根節(jié)點峡蟋，那么違反規(guī)則2坟桅，就直接把節(jié)點修改為黑色
- 2）如果插入節(jié)點的父節(jié)點是黑色的，說明符合規(guī)則蕊蝗，什么都不做
- 3）如果插入節(jié)點的父節(jié)點是紅色的仅乓，且祖父結(jié)點的另一個子節(jié)點（叔叔節(jié)點）也是紅色的
那么：將祖父節(jié)點變紅，而父和叔節(jié)點變黑蓬戚，然后設置祖父節(jié)點為當前節(jié)點夸楣，然后重新開始判斷。 - 4）如果插入節(jié)點的父節(jié)點是紅色子漩，而叔節(jié)點是黑色豫喧，且插入節(jié)點是其父的左子節(jié)點，而父節(jié)點是祖父節(jié)點的左子節(jié)點
那么：把父節(jié)點變?yōu)楹谏逼茫娓腹?jié)點變?yōu)榧t色紧显，然后對祖父節(jié)點進行右旋，然后重新開始判斷缕棵。 - 5）如果插入節(jié)點的父節(jié)點是紅色孵班，而叔節(jié)點是黑色，且插入節(jié)點是其父的右子節(jié)點招驴，而父節(jié)點是祖父節(jié)點的右子節(jié)點
那么：把父節(jié)點變?yōu)楹谏莩蹋娓腹?jié)點變?yōu)榧t色，然后對祖父節(jié)點進行左旋别厘，然后重新開始判斷虱饿。 - 6）如果插入節(jié)點的父節(jié)點是紅色，而叔節(jié)點是黑色触趴，且插入節(jié)點是其父的右子節(jié)點氮发，而父節(jié)點是祖父節(jié)點的左子節(jié)點
那么：把當前節(jié)點的父節(jié)點做為新的當前節(jié)點，對新的當前節(jié)點進行左旋雕蔽，然后重新開始判斷折柠。 - 7）如果插入節(jié)點的父節(jié)點是紅色，而叔節(jié)點是黑色批狐，且插入節(jié)點是其父的左子節(jié)點扇售，而父節(jié)點是祖父節(jié)點的右子節(jié)點
那么：把當前節(jié)點的父節(jié)點做為新的當前節(jié)點前塔，對新的當前節(jié)點進行右旋，然后重新開始判斷承冰。
6.紅黑樹的節(jié)點刪除算法华弓，并代碼示例
紅黑樹的節(jié)點刪除在前面學習二叉樹的時候，我們知道做節(jié)點刪除是很復雜的困乒，同樣寂屏，在紅黑樹里面做節(jié)點刪除，也是很復雜的娜搂，甚至比二叉樹的節(jié)點刪除更復雜迁霎，因為還需要保證刪除節(jié)點后，進行樹的平衡百宇。因此考廉，在實際開發(fā)中，多數(shù)情況下不用去做紅黑樹的節(jié)點刪除携御，而是采用其它變通方法：比如僅僅標識這個節(jié)點被刪除昌粤，并不真的刪除，這樣樹就不用動啄刹，在進行業(yè)務處理的時候涮坐，判斷一下，跳過這些節(jié)點就可以了誓军。
紅黑樹的刪除算法
- 1）如果刪除節(jié)點是葉子節(jié)點
（1）如果刪除節(jié)點是紅色的袱讹，那就直接刪除，不做其它操作
（2）如果刪除節(jié)點是黑色的谭企，那么就創(chuàng)建一個空節(jié)點來頂替刪除節(jié)點廓译，然后按照后面的調(diào)整步驟進行調(diào)整 - 2）如果刪除節(jié)點有一個子節(jié)點，把后來頂替被刪節(jié)點的那個節(jié)點成為頂替節(jié)點债查，如果刪除節(jié)點為黑，而且頂替節(jié)點也為黑瓜挽，那么把頂替節(jié)點當作當前節(jié)點盹廷，然后按照后面的調(diào)整步驟進行調(diào)整。
- 3）如果刪除節(jié)點有兩個子節(jié)點久橙，那么俄占，找到其中序后繼節(jié)點，把這兩個節(jié)點的數(shù)據(jù)交換一下淆衷，不要復制顏色缸榄，也不改變其原有的父子等關系，然后重新進行刪除祝拯。由于其中序后繼節(jié)點只可能是葉子節(jié)點或者只有一個子節(jié)點甚带，因此回到前面兩種情況她肯。
刪除步驟后的調(diào)整步驟，有以下幾種情況：
- 1）當前節(jié)點是紅
那么：直接把當前節(jié)點變成黑色鹰贵，結(jié)束 - 2）當前節(jié)點是黑且是根節(jié)點
那么：什么都不用做晴氨，結(jié)束 - 3）當前節(jié)點是黑且兄弟節(jié)點為紅色，當前節(jié)點為父節(jié)點的左子節(jié)點
那么：把兄弟結(jié)點變成父節(jié)點的顏色碉输，把父節(jié)點變成紅色籽前，然后在父節(jié)點上做左旋，再重新開始判斷敷钾。 - 4）當前節(jié)點是黑且兄弟節(jié)點為紅色枝哄，當前節(jié)點為父節(jié)點的右子節(jié)點
那么：把兄弟結(jié)點變成父節(jié)點的顏色，把父節(jié)點變成紅色阻荒，然后在父節(jié)點上做右旋膘格，再重新開始判斷。 - 5）當前節(jié)點是黑且父節(jié)點和兄弟節(jié)點都為黑色财松，兄弟節(jié)點的兩個子節(jié)點全為黑色
那么：把兄弟節(jié)點變紅瘪贱，然后把父節(jié)點當成新的當前節(jié)點，再重新開始判斷 - 6）當前節(jié)點是黑且兄弟節(jié)點為黑色辆毡，兄弟節(jié)點的兩個子節(jié)點都是黑色菜秦，但是父節(jié)點是紅色
那么：就把兄弟節(jié)點變紅，父節(jié)點變黑舶掖，結(jié)束 - 7）當前節(jié)點是黑且兄弟節(jié)點為黑色球昨，兄弟節(jié)點的左子是紅色，右子是黑色眨攘，而且當前節(jié)點是父節(jié)點的左子節(jié)點
那么：把兄弟節(jié)點變紅主慰，兄弟左子節(jié)點變黑，然后對兄弟節(jié)點進行右旋鲫售，再重新開始判斷 - 8）當前節(jié)點是黑且兄弟節(jié)點為黑色共螺，兄弟節(jié)點的左子是黑色，右子是紅色情竹，而且當前節(jié)點是父節(jié)點的右子節(jié)點
那么：把兄弟節(jié)點變紅藐不，兄弟右子節(jié)點變黑，然后對兄弟節(jié)點左旋秦效，再重新開始判斷 - 9）當前節(jié)點是黑且兄弟節(jié)點為黑色雏蛮，兄弟節(jié)點的右子是紅色，左子的顏色任意阱州，而且當前節(jié)點是父節(jié)點的左子節(jié)點
那么：把兄弟節(jié)點變成當前節(jié)點父節(jié)點的顏色挑秉，把當前節(jié)點父節(jié)點變黑，兄弟節(jié)點右子變黑苔货，然后以當前節(jié)點的父節(jié)點為支點進行左旋犀概，結(jié)束立哑。 - 10）當前節(jié)點是黑且兄弟節(jié)點為黑色，兄弟節(jié)點的左子是紅色阱冶，右子的顏色任意刁憋，而且當前節(jié)點是父節(jié)點的右子節(jié)點
那么：把兄弟節(jié)點變成當前節(jié)點父節(jié)點的顏色，把當前節(jié)點父節(jié)點變黑木蹬，兄弟節(jié)點左子變黑至耻，然后以當前節(jié)點的父節(jié)點為支點進行右旋，結(jié)束镊叁。
7.紅黑樹的效率
紅黑樹的效率紅黑樹的查找尘颓、插入和刪除的時間復雜度都是O(logN)，以2為底晦譬。跟二叉樹是一樣的疤苹，但實際上，由于紅黑樹在插入和刪除的時候敛腌，需要保證樹的平衡卧土，所以會比二叉樹慢。另外一個像樊，紅黑樹的節(jié)點需要多一點額外的空間尤莺，來存儲顏色信息。
8.了解其它的平衡樹
AVL(發(fā)明者為：Adelson-Velskii和Landis)樹是最早的一種平衡樹生棍，它要求節(jié)點左子樹和右子樹的高度相差不超過1颤霎。當插入和刪除節(jié)點的時候，都需要重新平衡樹涂滴，也就是每次操作會掃描兩趟樹友酱，一次向下查找節(jié)點，一次向上平衡樹柔纵。 AVL樹的效率不如紅黑樹缔杉，也不如紅黑樹常用，因此了解一下即可首量。
