知識總覽：

為什么要發明紅黑樹：

二叉排序樹BST

紅黑樹RBT的查找、插入和刪除效率基本和AVL平衡二叉樹的相同，但是平衡二叉樹在插入和刪除節點操作時容易被破壞平衡，所以需要消耗大量時間重新調整樹的形態(主要時間用在計算平衡因子，找最小不平衡樹等)，而紅黑樹在插入和刪除操作時就不需要頻繁調整樹的形態，即便需要調整，一般也可在常數級完成，所以紅黑樹很牛

一般查詢多，插入刪除少的用平衡二叉樹，如果是插入、刪除多的用紅黑樹

j?

紅黑樹定義：

紅黑樹是二叉排序樹的一種優化，則紅黑樹有二叉排序樹BST的特性，即節點值左子樹<根節點<右子樹(左<中<右)?，每個節點上除了有左子孩子指針外，還有節點的顏色color

定義：

1.紅黑樹的節點的顏色要么是黑色要么是紅色

2.紅黑樹中的葉節點一般指的是查找失敗的節點，葉節點又叫NULL空節點或者外部節點，注意不是最下層的節點，二叉排序樹中的查找失敗的節點也是NULL節點即不存在的節點，根節點和葉節點一定都是黑色的節點

4.紅黑樹中的父子節點不能出現連續的紅節點，但是如果是兄弟節點可以是連續的紅節點，如下圖3，節點17是紅節點，則它的父節點13和孩子節點15和25必須都是黑節點，否則就出現連續的紅節點了，如果15節點是紅節點，則不滿足紅黑樹定義，22和27是兄弟節點可以是連續紅節點

5.從任一節點(包括根節點)出發，該節點到任一葉節點的有各種各樣的路徑，但是不管是啥路徑，在各個路徑上所經過的黑節點的個數是相同的。如下從13出發可以到達各個葉節點，13->8->1->null,13->8->11->null,13->17->15->null等等路徑，所經過的黑節點個數都是2(注意從某個節點出發所經過的黑節點數量不包括出發節點，即便是從該節點出發該節點是黑節點，那也不包括)，以上路徑所經過的黑節點依次是(1,null)、(11,null)、(15,null)即都是2個黑節點

紅黑樹口訣：

左根右======》指的是滿足節點值左子樹<根節點<右子樹

根葉黑======》指的是根節點和葉子節點都是黑節點

不紅紅======》指的是父子節點不存在2個相鄰的紅節點

黑路同======》指的是一條路走到黑，走到葉子節點(葉子節點是黑的)，所包含的黑節點數目相同

平衡二叉樹AVL也是二叉排序樹的一種優化，AVL每個節點上除了有左右孩子指針外，還有平衡因子

練習：

如下截圖中分別違反不紅紅(父子節點2個紅節點不能相鄰)和根葉黑要求(根節點是黑色的)、黑路同(從1節點出發到葉子黑節點，經過的黑節點數目分別為1和2)，即不符合紅黑樹要求

?

補充概念：節點的黑高

黑高bh定義： 從某一節點出發(不包含該節點)到達任一空葉節點的路徑上的黑節點的數目(跟上邊的紅黑樹的黑路同特性類似)

如下15節點的bh=2，即15->11->8->null(黑節點為11和NULL節點)或者15->18->null(黑節點為18和和NULL節點)等等在到達葉節點上的路徑上的黑節點的數目都是2，根節點6bh=2同，6->2->null(黑節點為2、NULL節點)或者6->15->18->20->null(黑節點為18、NULL節點)等等路徑的黑節點的數目=2

?紅黑樹的性質：

1.從根節點到葉節點的最長路徑不大于最短路徑的2倍（這個是因為不允許2個紅節點相鄰出現，所以最長路勁肯定是紅黑交叉的路徑，所以最長路徑不大于最短路徑的2倍。。。。可能是吧。。）

2.有n個內部節點的紅黑樹高度h<=2log2(n+1)，即紅黑樹的查找效率為log2n數量級，即紅黑樹的查找時間復雜度為O(log2n)

紅黑樹的查找：因為紅黑樹也是二叉排序樹，所以查找和二叉排序樹一樣，從根節點出發，左小右大，若找到空葉節點則查找失敗

知識回顧：

?

又水一篇。。。。。。。。。。。。。?