紅黑樹(shù)

1. 紅-黑樹(shù)的特征

平衡二叉搜索樹(shù)：它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù).

時(shí)間復(fù)雜度：
常數(shù)階O(1)、對(duì)數(shù)階O(log2n)、線性階O(n)、線性對(duì)數(shù)階O(nlog2n)、平方階O(n^{2)、立方階O(n}3)、k次方階O(n^{k)、指數(shù)階O(2}n)。
https://blog.csdn.net/m0_37854317/article/details/70491581

二叉搜索樹(shù)作為一種數(shù)據(jù)結(jié)構(gòu)，其查找、插入和刪除操作的時(shí)間復(fù)雜度都為O(logn),底數(shù)為2。
如果插入的數(shù)據(jù)是隨機(jī)的，則效率很高，但是如果插入的數(shù)據(jù)是有序的，比如10,20,30,40,50插入到二叉搜索樹(shù)中：
這和鏈表沒(méi)有任何區(qū)別了，查找的時(shí)間復(fù)雜度為O(N)，而不是O(logN)。
當(dāng)然這是在最不平衡的條件下，實(shí)際情況下，二叉搜索樹(shù)的效率應(yīng)該在O(N)和O(logN)之間，這取決于樹(shù)的不平衡程度。

紅黑規(guī)則
1.每個(gè)節(jié)點(diǎn)不是紅色就是黑色的；
　　2.根節(jié)點(diǎn)總是黑色的
　　3.如果節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的（反之不一定）,(也就是從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))；
　　4.從根節(jié)點(diǎn)到葉節(jié)點(diǎn)或空子節(jié)點(diǎn)的每條路徑，必須包含相同數(shù)目的黑色節(jié)點(diǎn)（即相同的黑色高度）
新插入的節(jié)點(diǎn)顏色總是紅色的，這是因?yàn)椴迦胍粋€(gè)紅色節(jié)點(diǎn)比插入一個(gè)黑色節(jié)點(diǎn)違背紅-黑規(guī)則的可能性更小

效率
紅黑樹(shù)的查找、插入和刪除時(shí)間復(fù)雜度都為O(log2N)，額外的開(kāi)銷是每個(gè)節(jié)點(diǎn)的存儲(chǔ)空間都稍微增加了一點(diǎn)，因?yàn)橐粋€(gè)存儲(chǔ)紅黑樹(shù)節(jié)點(diǎn)的顏色變量。
插入和刪除的時(shí)間要增加一個(gè)常數(shù)因子，因?yàn)橐M(jìn)行旋轉(zhuǎn)，平均一次插入大約需要一次旋轉(zhuǎn)，因此插入的時(shí)間復(fù)雜度還是O(log2N)
(時(shí)間復(fù)雜度的計(jì)算省略常數(shù))，但實(shí)際上比普通的二叉樹(shù)是要慢的。

大多數(shù)應(yīng)用中，查找的次數(shù)比插入和刪除的次數(shù)多，所以應(yīng)用紅黑樹(shù)取代普通的二叉搜索樹(shù)總體上不會(huì)有太多的時(shí)間開(kāi)銷。
而且紅黑樹(shù)的優(yōu)點(diǎn)是對(duì)于有序數(shù)據(jù)的操作不會(huì)慢到O(N)的時(shí)間復(fù)雜度。

2. 紅-黑樹(shù)的自我修正
   在新增節(jié)點(diǎn)或者刪除節(jié)點(diǎn)之后，可能會(huì)破壞二叉樹(shù)的平衡。通過(guò)三種方式對(duì)平衡進(jìn)行修正
   改變顏色是為了幫助判斷何時(shí)旋轉(zhuǎn)，而旋轉(zhuǎn)是為了保證樹(shù)的平衡。光改變節(jié)點(diǎn)顏色是不能起到任何作用的，旋轉(zhuǎn)才是關(guān)鍵的操作，
   節(jié)點(diǎn)本身是不會(huì)旋轉(zhuǎn)的，旋轉(zhuǎn)改變的是節(jié)點(diǎn)之間的關(guān)系。選擇一個(gè)節(jié)點(diǎn)作為旋轉(zhuǎn)的頂端，如果做一次右旋，
   這個(gè)頂端節(jié)點(diǎn)會(huì)向下和向右移動(dòng)到它右子節(jié)點(diǎn)的位置，它的左子節(jié)點(diǎn)會(huì)上移到它原來(lái)的位置。

①、改變節(jié)點(diǎn)顏色
　?、凇⒂倚?br> 　 右旋的頂端節(jié)點(diǎn)必須要有左子節(jié)點(diǎn)。
　?、?、左旋
左旋的頂端節(jié)點(diǎn)必須要有右子節(jié)點(diǎn)。

3. 插入
   如果是第一次插入，由于原樹(shù)為空，所以只要把根節(jié)點(diǎn)涂黑即可；
   如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色的，那不會(huì)違背紅-黑樹(shù)的規(guī)則，什么也不需要做；
   但是插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的，有如下三種情況，就要開(kāi)始變色和旋轉(zhuǎn)：

①、插入節(jié)點(diǎn)的父節(jié)點(diǎn)和其叔叔節(jié)點(diǎn)（祖父節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn)）均為紅色。

此時(shí)肯定存在祖父節(jié)點(diǎn)，但是不知道父節(jié)點(diǎn)是其左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)，但是由于對(duì)稱性，我們只要討論出一邊的情況。
這種情況，將當(dāng)前節(jié)點(diǎn)(4) 的父節(jié)點(diǎn)(5) 和叔叔節(jié)點(diǎn)(8) 涂黑，將祖父節(jié)點(diǎn)(7)涂紅。
再將當(dāng)前節(jié)點(diǎn)指向其祖父節(jié)點(diǎn)，再次從新的當(dāng)前節(jié)點(diǎn)開(kāi)始算法（具體看下面的步驟）。這樣上右圖就變成情況2了。

②、插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的，叔叔節(jié)點(diǎn)是黑色的，且插入節(jié)點(diǎn)是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)。

③、插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的，叔叔節(jié)點(diǎn)是黑色的，且插入節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)。