1哥纫、定義
紅黑樹是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的平衡二叉查找樹 镇眷，顏色為紅色或黑色波桩。除了二叉查找樹一般要求以外鹅巍，對(duì)于任何有效的紅黑樹我們?cè)黾恿巳缦碌念~外要求:
（1）節(jié)點(diǎn)是要么紅色或要么是黑色音同。
（2）根一定是黑色節(jié)點(diǎn)词爬。
（3）每個(gè)葉子節(jié)點(diǎn)都帶有兩個(gè)空的黑色節(jié)點(diǎn)（稱之為NIL節(jié)點(diǎn)，它又被稱為黑哨兵）权均。
（4）每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色（或者說(shuō)從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）顿膨。
（5）從任一節(jié)點(diǎn)到它所能到達(dá)得葉子節(jié)點(diǎn)的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
如下圖
2叽赊、性質(zhì)
根節(jié)點(diǎn)到任意葉子節(jié)點(diǎn)的路徑長(zhǎng)度恋沃，最多相差一半。若樹存在最短路徑必指，則最短路徑上均為黑色節(jié)點(diǎn)囊咏，那么第五條性質(zhì)保證根節(jié)點(diǎn)到達(dá)最長(zhǎng)路徑與最短路徑所包含的黑色節(jié)點(diǎn)數(shù)目相同，若最短路徑長(zhǎng)為N塔橡，則最長(zhǎng)路徑M=N+紅色節(jié)點(diǎn)數(shù)目梅割，性質(zhì)4要求紅色節(jié)點(diǎn)必定不連續(xù)，因此紅色節(jié)點(diǎn)數(shù)目最多為N葛家，則最長(zhǎng)路徑與最短路徑最多相差N户辞。
3、插入
3.1癞谒、插入節(jié)點(diǎn)的父節(jié)點(diǎn)為黑色
若待插入節(jié)點(diǎn)的父節(jié)點(diǎn)為黑色底燎，則直接插入節(jié)點(diǎn)，并將插入的節(jié)點(diǎn)涂紅弹砚，插入結(jié)束双仍。父節(jié)點(diǎn)為黑色，插入紅色節(jié)點(diǎn)并不會(huì)使紅黑樹違背5條性質(zhì)迅栅。如圖
3.2殊校、插入節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色，叔叔節(jié)點(diǎn)為黑色：
此種情形需要區(qū)分節(jié)點(diǎn)的插入位置读存，根據(jù)插入位置的不同進(jìn)行相應(yīng)的調(diào)整为流。此種情形共有四種：
3.2.1、父節(jié)點(diǎn)P為G左孩子让簿，插入位置為左孩子
1：插入后違背性質(zhì)4敬察，首先以祖父節(jié)點(diǎn)G為中心，執(zhí)行右旋操作尔当。
2：右旋操作結(jié)束莲祸，將父節(jié)點(diǎn)P涂黑色蹂安，祖父節(jié)點(diǎn)G涂紅色，調(diào)整完畢锐帜。
3.2.2田盈、父節(jié)點(diǎn)P為G左孩子，插入位置為右孩子
1：插入后違背性質(zhì)4缴阎，首先以父節(jié)點(diǎn)P為中心允瞧，執(zhí)行左旋操作。
2：左旋操作結(jié)束后蛮拔，情形與3.2.1相同述暂，進(jìn)行處理。
3.2.3建炫、父節(jié)點(diǎn)P為G右孩子畦韭，插入位置為右孩子
1：插入后違背性質(zhì)4，首先以祖父節(jié)點(diǎn)G為中心肛跌，執(zhí)行左旋操作艺配。
2：左旋操作結(jié)束，將父節(jié)點(diǎn)P涂黑色惋砂，祖父節(jié)點(diǎn)G涂紅色妒挎，調(diào)整完畢。
3.2.4西饵、父節(jié)點(diǎn)P為G右孩子酝掩，插入位置為左孩子
可參考3.2.2/3.2.3操作。
3.3眷柔、插入節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色期虾，叔叔節(jié)點(diǎn)為紅色
此種情形根據(jù)插入位置的不同，分為兩種：
3.3.1驯嘱、插入位置為左子樹
3.3.2镶苞、插入位置為右子樹
祖父結(jié)點(diǎn)作為新插入的結(jié)點(diǎn)繼續(xù)向上迭代進(jìn)行平衡操作，在迭代時(shí)如果調(diào)整到根鞠评，則根為黑色茂蚓，跳出循環(huán)（否則繼續(xù)循環(huán)，循環(huán)結(jié)束條件為當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)顏色為黑色）剃幌，調(diào)整完畢聋涨。
4、應(yīng)用
（1）IO多路復(fù)用epoll的實(shí)現(xiàn)采用紅黑樹組織管理sockfd负乡，以支持快速的增刪改查.
（2）ngnix中,用紅黑樹管理timer,因?yàn)榧t黑樹是有序的,通過(guò)二分法可以很快的得到距離當(dāng)前最小的定時(shí)器.
（3） java中TreeMap牍白，jdk1.8的hashmap的實(shí)現(xiàn).
