紅黑樹特點:
每個節(jié)點不是紅色就是黑色的；
根節(jié)點總是黑色的煌恢；
所有的葉節(jié)點都是是黑色的（紅黑樹的葉子節(jié)點都是空節(jié)點（NIL或者NULL））；
如果節(jié)點是紅色的，則它的子節(jié)點必須是黑色的（反之不一定）枢贿；
從根節(jié)點到葉節(jié)點或空子節(jié)點的每條路徑，必須包含相同數(shù)目的黑色節(jié)點（即相同的黑色高度）
紅黑樹性能：?
二叉樹是一個簡單的二分查找刀脏，但其性能取決于二叉樹的層數(shù)”局荚。
紅黑樹和 平衡二叉樹 區(qū)別如下 ：
1、紅黑樹放棄了追求完全平衡，追求大致平衡耀态，在與平衡二叉樹的時間復(fù)雜度相差不大的情況下轮傍，保證每次插入最多只需要三次旋轉(zhuǎn)就能達到平衡，實現(xiàn)起來也更為簡單首装。
2创夜、平衡二叉樹追求絕對平衡，條件比較苛刻仙逻，實現(xiàn)起來比較麻煩驰吓，每次插入新節(jié)點之后需要旋轉(zhuǎn)的次數(shù)不能預(yù)知。
二叉查找樹（BST）具備什么特性呢桨醋？
1.左子樹上所有結(jié)點的值均小于或等于它的根結(jié)點的值棚瘟。
2.右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值。
3.左喜最、右子樹也分別為二叉排序樹偎蘸。
下圖中這棵樹，就是一顆典型的二叉查找樹：
依次插入如下五個節(jié)點：7,6,5,4,3瞬内。依照二叉查找樹的特性迷雪，結(jié)果會變成什么樣呢？
什么情況下會破壞紅黑樹的規(guī)則虫蝶，什么情況下不會破壞規(guī)則呢章咧？我們舉兩個簡單的栗子：
1.向原紅黑樹插入值為14的新節(jié)點：
由于父節(jié)點15是黑色節(jié)點，因此這種情況并不會破壞紅黑樹的規(guī)則能真，無需做任何調(diào)整赁严。
2.向原紅黑樹插入值為21的新節(jié)點：
由于父節(jié)點22是紅色節(jié)點，因此這種情況打破了紅黑樹的規(guī)則4（每個紅色節(jié)點的兩個子節(jié)點都是黑色）粉铐，必須進行調(diào)整疼约，使之重新符合紅黑樹的規(guī)則。
下圖所表示的是紅黑樹的一部分蝙泼，需要注意節(jié)點25并非根節(jié)點程剥。因為節(jié)點21和節(jié)點22連續(xù)出現(xiàn)了紅色，不符合規(guī)則4汤踏，所以把節(jié)點22從紅色變成黑色：
但這樣并不算完织鲸，因為憑空多出的黑色節(jié)點打破了規(guī)則5，所以發(fā)生連鎖反應(yīng)溪胶，需要繼續(xù)把節(jié)點25從黑色變成紅色：
此時仍然沒有結(jié)束搂擦，因為節(jié)點25和節(jié)點27又形成了兩個連續(xù)的紅色節(jié)點，需要繼續(xù)把節(jié)點27從紅色變成黑色：
左旋轉(zhuǎn)：
逆時針旋轉(zhuǎn)紅黑樹的兩個節(jié)點载荔，使得父節(jié)點被自己的右孩子取代盾饮，而自己成為自己的左孩子。說起來很怪異，大家看下圖：
右旋轉(zhuǎn)：
順時針旋轉(zhuǎn)紅黑樹的兩個節(jié)點丘损，使得父節(jié)點被自己的左孩子取代普办，而自己成為自己的右孩子。大家看下圖：
具體：https://juejin.im/post/5a27c6946fb9a04509096248#comment
變色 -> 左旋轉(zhuǎn) -> 變色 -> 右旋轉(zhuǎn) -> 變色 ok
