最近2018中文字幕在日韩欧美国产成人片_国产日韩精品一区二区在线_在线观看成年美女黄网色视频_国产精品一区三区五区_国产精彩刺激乱对白_看黄色黄大色黄片免费_人人超碰自拍cao_国产高清av在线_亚洲精品电影av_日韩美女尤物视频网站

紅黑樹是一種很經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，它可以在O(log n)時(shí)間內(nèi)做查找，插入和刪除。所以倍受關(guān)注。但是一直以來很多Java程序員對他都不是很重視，直到在JDK 1.8中，HashMap會(huì)將其鏈表轉(zhuǎn)換成紅黑樹，此后，很多人就開始重新學(xué)習(xí)紅黑樹的有關(guān)知識(shí)。

作者在學(xué)習(xí)紅黑樹時(shí)，查閱了很多資料都沒有找到解釋的特別清楚的，于是自己總結(jié)了這一篇文章，總字?jǐn)?shù)近7k，而且繪制了很多圖，希望可以讓大家更容易理解。

1. 定義

紅黑樹是Avl樹的一個(gè)變種，它也是在二叉查找樹的基礎(chǔ)上添加平衡條件，只是它對平衡條件的描述不像AVl樹那樣直接，而是轉(zhuǎn)化成對節(jié)點(diǎn)顏色規(guī)則的描述。

顏色規(guī)則：

1. 對于任意節(jié)點(diǎn)，要么是紅色，要么是黑色;
2. 根節(jié)點(diǎn)是黑色的;
3. 如果一個(gè)節(jié)點(diǎn)是紅色的，那么它的子節(jié)點(diǎn)必須是黑色的(即不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn));
4. 任意節(jié)點(diǎn)到其下面各個(gè)空結(jié)點(diǎn)(后面稱為nil節(jié)點(diǎn)，并約定其顏色為黑色)的路徑上都包含相同數(shù)目的黑色節(jié)點(diǎn)(稱為黑高);

通過對任何一條從根到空節(jié)點(diǎn)的路徑上各個(gè)結(jié)點(diǎn)的顏色進(jìn)行約束，紅黑樹可以確保沒有一條路徑會(huì)比其他路徑長出2倍，因而紅黑樹是近似平衡的。

2. 分析實(shí)現(xiàn)

為了便于處理紅黑樹代碼中的邊界條件，使用兩個(gè)標(biāo)記節(jié)點(diǎn)header和nil來充當(dāng)哨兵，它們與樹中的普通節(jié)點(diǎn)有相同的屬性，顏色設(shè)為黑色。將header的值設(shè)為負(fù)無窮，因此它的右子節(jié)點(diǎn)就是真正的根，在對樹進(jìn)行遍歷時(shí)我們可以用header作為起點(diǎn)。nil的值可以為任意值，將它作為所有空節(jié)點(diǎn)的統(tǒng)一引用， 即讓所有樹葉的左右子節(jié)點(diǎn)都指向nil，那么在遍歷時(shí)就可以將nil視為結(jié)束的標(biāo)志。

紅黑樹也是一顆查找二叉樹，所以它的基本操作與查找二叉樹一致，區(qū)別也在于插入和刪除后的平衡恢復(fù)。只是實(shí)現(xiàn)平衡時(shí)的目標(biāo)就是滿足它對顏色規(guī)則的定義，至于樹的平衡與否已經(jīng)由規(guī)則本身去保證。

2.1. 插入

與二叉查找樹一樣，插入節(jié)點(diǎn)其實(shí)就是添加一個(gè)樹葉，主要問題是在添加結(jié)束時(shí)可能要做一些調(diào)整來保證紅黑樹的規(guī)則不被破壞。

不過，根據(jù)規(guī)則4， 可以知道，在插入之前任意節(jié)點(diǎn)到其下面各個(gè)nil的路徑上都包含相同數(shù)目的黑節(jié)點(diǎn)數(shù)，如果能保證在插入節(jié)點(diǎn)前后父節(jié)點(diǎn)parent或者祖父節(jié)點(diǎn)grand到其下面nil的路徑上的黑節(jié)點(diǎn)數(shù)不變， 即保證parent或者grand的黑高不變，那么就可以保證紅黑樹的規(guī)則不被破壞，這樣就可以將平衡操作時(shí)需要考慮的范圍縮小到grand。

由于插入紅色節(jié)點(diǎn)不會(huì)影響路徑上的黑節(jié)點(diǎn)數(shù)，因此就先將待插入的節(jié)點(diǎn)涂成紅色，如果parent是黑色，那么插入直接完成。如果parent是紅色，那么插入之后將違反規(guī)則3， 這時(shí)再做一些調(diào)整。

先分析一下插入之前的可能情形，根據(jù)規(guī)則3，如果parent是紅色，那么可以斷定grand以及parent的另一個(gè)子節(jié)點(diǎn)一定是黑色。不僅如此，因?yàn)椴迦氲氖菢淙~節(jié)點(diǎn)在之前一定是nil， 那么parent的另一個(gè)子節(jié)點(diǎn)必然也是nil，否則插入之前parent就違反了規(guī)則4。

再看parent的兄弟節(jié)點(diǎn)，如果它是黑色的，那么它一定也是nil節(jié)點(diǎn);如果它是紅色的，那么它的兩個(gè)子節(jié)點(diǎn)一定都是nil節(jié)點(diǎn)，否則插入之前grand就違反了規(guī)則4。

所以，如果parent是紅色，那么我們可以完整地畫出插入之前的所有可能情況，一共有4種，其中待插入節(jié)點(diǎn)的位置就是圖中parent下面的兩個(gè)nil之一。

可以看出，1和2，3和4分別是對稱的兩種情況，區(qū)別在于parent與grand的大小關(guān)系，其實(shí)可以概括為parent的兄弟節(jié)點(diǎn)uncle是黑色還是紅色的兩種情況。

1. 如果parent為紅色，uncle為黑色

以情況1為例(即parent小于grand)：如果current小于parent，那么插入之后，可以將parent和grand的顏色互換，然后將grand右旋，這樣就能保證原來以grand為根的這個(gè)子樹的黑高保持不變，也就保證了整棵樹不被破壞。

如果current大于parent，則可以先將parent左旋，然后將current視為parent，再與上面進(jìn)行相同的操作，即可恢復(fù)平衡。

2. 如果parent為紅色，uncle為紅色

這時(shí)無論怎么旋轉(zhuǎn)都已經(jīng)解決不了問題，不過可以知道，在插入之前grand到下面各個(gè)nil的黑節(jié)點(diǎn)數(shù)為1，因此，只要保證grand的黑高仍然為1就行， 那么，通過將grand與其左右子節(jié)點(diǎn)的顏色進(jìn)行翻轉(zhuǎn)便可達(dá)到目標(biāo)。

以情況3為例：

但是，翻轉(zhuǎn)會(huì)使grand變成紅色，這時(shí)如果曾祖父也是紅色，那么將違反了規(guī)則3。因此可能需要朝著樹根的方向進(jìn)行逐層分析，直到不再有兩個(gè)相連的紅色節(jié)點(diǎn)或者到達(dá)樹根為止，但這顯然會(huì)很麻煩。

事實(shí)上，由于顏色翻轉(zhuǎn)的等價(jià)性，我們可以在查找插入節(jié)點(diǎn)位置的過程中，通過顏色翻轉(zhuǎn)來避免掉uncle為紅色的情況，即將顏色翻轉(zhuǎn)的事情提前做了。

在自上而下的查找過程中，如果看到一個(gè)節(jié)點(diǎn)X的兩個(gè)子節(jié)點(diǎn)都為紅色，可以使X變成紅色，而兩個(gè)子節(jié)點(diǎn)變成黑色(如果X是根，則可以在翻轉(zhuǎn)之后再將其置為黑色)，結(jié)果依然滿足紅黑樹的規(guī)則。

只有當(dāng)X的parent為紅色時(shí)，才會(huì)破壞紅黑樹的規(guī)則。不過這時(shí)可以斷定X的兄弟節(jié)點(diǎn)，X的grand，以及X的uncle都是黑色的(因?yàn)槿绻鸛的parent和uncle都為紅色， 那么一定會(huì)在自上而下的查找和翻轉(zhuǎn)過程中被過濾掉)。

那么，可以將X視為current，然后與上面parent為紅色，uncle為黑色的情形進(jìn)行相同的處理。下面通過畫圖來說明一種情形(對稱情形類似處理)：

先對X與其子節(jié)點(diǎn)進(jìn)行顏色翻轉(zhuǎn)

然后，將X視為之前的current，對parent和grand進(jìn)行換色和旋轉(zhuǎn)

完成之后，將新的根(即原本grand的位置)視為新的current，然后重新向下遍歷。由于X的孫子節(jié)點(diǎn)之前一定為黑色，而X的兒子節(jié)點(diǎn)在翻轉(zhuǎn)之后也為黑色，因此在調(diào)整之后， 可以保證在X的下面將有連續(xù)兩層不會(huì)出現(xiàn)紅節(jié)點(diǎn)。

所以，盡管旋轉(zhuǎn)調(diào)整會(huì)使得gand的位置變得錯(cuò)誤，但在接下來的遍歷中，又會(huì)立即將grand-parent-current恢復(fù)成正確的位置關(guān)系。

總結(jié)節(jié)點(diǎn)插入問題：首先根據(jù)二叉查找樹的性質(zhì)，可以知道插入節(jié)點(diǎn)就是添加樹葉，其次對于紅黑樹而言，插入紅色節(jié)點(diǎn)不會(huì)影響路徑上的黑節(jié)點(diǎn)數(shù)。

因此， 我們將插入的節(jié)點(diǎn)視為紅色的樹葉，這時(shí)只要考慮插入的紅色樹葉的parent是紅色還是黑色，如果是黑色問題直接解決，如果是紅色，再看uncle是紅色還是黑色。如果uncle是黑色，可以通過變色旋轉(zhuǎn)解決;如果是紅色，那么通過顏色翻轉(zhuǎn)也能達(dá)到目的，但這會(huì)使grand變成紅色，需要進(jìn)一步考慮曾祖父的顏色問題，將問題放大了。于是考慮在一開始向下的遍歷過程中， 提前翻轉(zhuǎn)顏色來避免掉parent和unlce同時(shí)為紅色的情況。

因此，最終在插入節(jié)點(diǎn)時(shí)，實(shí)際需要考慮旋轉(zhuǎn)調(diào)整的情形只有一種，即parent為紅色，uncle為黑色。

2.2. 刪除

對于節(jié)點(diǎn)刪除，大概思路也是先將問題轉(zhuǎn)化成刪除樹葉來簡化問題，如果是紅色樹葉，則可以直接刪除，如果是黑色樹葉，則再分情形進(jìn)行討論。

先看下如何將刪除目標(biāo)轉(zhuǎn)化成對樹葉的刪除，根據(jù)二叉查找樹的性質(zhì)，在刪除節(jié)點(diǎn)時(shí)可以用右子樹的最小節(jié)點(diǎn)或左子樹的最大節(jié)點(diǎn)來替換要?jiǎng)h除的節(jié)點(diǎn)，然后刪除子樹中用來替換的那個(gè)節(jié)點(diǎn)。

不過在紅黑樹中，為了保證節(jié)點(diǎn)的顏色規(guī)則，替換時(shí)將只進(jìn)行值的替換。其實(shí)，根據(jù)紅黑樹的規(guī)則可以得出一個(gè)簡單的推論：如果一個(gè)樹葉沒有兄弟節(jié)點(diǎn)，那么它一定為紅色，或者說如果一個(gè)樹葉為黑色， 則它必然有兄弟節(jié)點(diǎn)。

另外，還可以斷定：對于任意節(jié)點(diǎn)，其右子樹的最小(即最左)節(jié)點(diǎn)最多存在一個(gè)紅色右子節(jié)點(diǎn)，其左子樹的最大(即最右)節(jié)點(diǎn)最多存在一個(gè)紅色左子節(jié)點(diǎn)。因此，當(dāng)左子樹的最大節(jié)點(diǎn)或右子樹的最小節(jié)點(diǎn)不是樹葉時(shí)，可以繼續(xù)用同樣的思路來轉(zhuǎn)換要?jiǎng)h除的目標(biāo)，并且這時(shí)可以斷定最后刪除的樹葉一定是紅色。

再來討論刪除黑色樹葉的情形，由于黑色樹葉必然會(huì)存在兄弟節(jié)點(diǎn)(樹根除外)，因此在下面的討論中首先假設(shè)要?jiǎng)h除的黑色樹葉總是在左邊(如果在右邊則對稱處理)， 這時(shí)可以根據(jù)其兄弟節(jié)點(diǎn)brother和父親節(jié)點(diǎn)parent的顏色來將刪除情形分為3種。下面分別進(jìn)行畫圖分析(圖中省略掉空節(jié)點(diǎn)nil)：

1.parent為紅色，brother為黑色

由于current是樹葉，那么可以斷定brother下面不會(huì)再有黑色的后代節(jié)點(diǎn)，至多只能有紅色的兒子節(jié)點(diǎn)，否則parent在刪除前將違反規(guī)則4。

1.1 先看brother沒有兒子的情況，此時(shí)看上去比較簡單，直接對parent進(jìn)行左旋即可解決問題，能夠保證在刪除調(diào)整前后以原parent為根的子樹的黑高不變。

1.2 但是，如果brother有一個(gè)紅色左兒子(右兒子沒有影響，因此忽略)，那么直接對parent進(jìn)行左旋，將會(huì)造成兩個(gè)連續(xù)的紅色的節(jié)點(diǎn)而違反規(guī)則3， 這時(shí)需要先將brother右旋，然后再對parent進(jìn)行換色并左旋來解決。

因此，需要根據(jù)brother是否有紅色左兒子將情形1再分為2種子情形來進(jìn)行處理。

2.parent為黑色，brother為紅色

同樣由于current是樹葉，可以斷定brother的兩個(gè)黑色的兒子節(jié)點(diǎn)下面至多只能有一層紅色子節(jié)點(diǎn)，下面根據(jù)brother左兒子的子節(jié)點(diǎn)情況(右兒子的子節(jié)點(diǎn)沒有影響，因此忽略)來分情形討論。

2.1 還是先看brother的左兒子沒有子節(jié)點(diǎn)的情況，這時(shí)可以將brother與其左兒子進(jìn)行換色，然后將parent進(jìn)行左旋。

2.2 如果brother的左兒子有一個(gè)紅色右子節(jié)點(diǎn)，這時(shí)需要先將brother左兒子的右子節(jié)點(diǎn)涂成黑色，并將brother右旋，然后再將parent左旋。

2.3 如果brother的左兒子沒有紅色右子節(jié)點(diǎn)，但有一個(gè)紅色左子節(jié)點(diǎn)。這時(shí)可以先將brother左兒子的左子節(jié)點(diǎn)涂成黑色，并將brother的左兒子右旋，這樣將情形轉(zhuǎn)化成2.2， 然后依次將brother右旋，parent左旋。

因此，需要根據(jù)brother左兒子的子節(jié)點(diǎn)情況將情形2再分為3種子情形來處理。

3.parent為黑色，brother為黑色

還是由于current是樹葉，可以斷定brother下面至多只能有一層紅色的兒子節(jié)點(diǎn)，否則parent在刪除前就違反了規(guī)則4。

3.1 還是先看brother沒有兒子的情況，此時(shí)通過parent為根的子樹自身已經(jīng)解決不了問題，想法是將brother變成紅色來降低parent子樹的黑高，然后將parent子樹整個(gè)視為一個(gè)current進(jìn)行處理， 下面會(huì)再詳細(xì)說明。

3.2 如果brother有一個(gè)紅色右兒子，這時(shí)可以將brother的右兒子變成黑色，然后將parent左旋。

3.3 如果brother沒有紅色右兒子，但是存在一個(gè)紅色左兒子，這時(shí)可以將brother的左兒子變成黑色，然后將brother右旋，再將parent左旋。

因此，需要根據(jù)brother的子節(jié)點(diǎn)情況將情形3再分為3種子情形來處理。

小結(jié)一下，上面一共將刪除了黑色樹葉的情形分成了8種，除了3.1，其它都可以在parent子樹內(nèi)部解決問題。為了進(jìn)一步分析3.1的問題，需要擴(kuò)展下思維， 可以想象一下，將current是樹葉這個(gè)前提去掉，然后將current視為根為黑色的子樹。假設(shè)這時(shí)刪除的黑色樹葉落在current子樹下面， 并且遇到了情形3.1，那么可以看成將current子樹整體的黑高降1，然后再根據(jù)brother子樹和parent的情況來進(jìn)行處理。

如果依然解決不了問題， 那么可以將parent樹視為新的current子樹， 再將祖父節(jié)點(diǎn)視為新的parent，這樣逐層向上分析，直到能夠在新的parent為根的樹內(nèi)部解決問題或者到達(dá)樹根為止。

下面通過畫圖再對上面的情形進(jìn)行一遍說明，對于空節(jié)點(diǎn)nil可以使用黑色節(jié)點(diǎn)代替。另外，這時(shí)有一個(gè)前提假設(shè)：即在刪除之前current子樹的黑高一定大于1， 那么brother子樹的黑高必然也至少為2，也就是說brother到nil的路徑上必然還有黑色節(jié)點(diǎn)。

為了更好的說明，圖中用x標(biāo)出樹根， 并用a,b,c,d,e,f,g,h標(biāo)出樹根下面的一些相對位置(可以將這些位置看成nil，只是圖中做了省略，沒有畫出current和brother到這些nil的完整路徑)。所有圖的最終目標(biāo)的都是保證：如果current子樹的黑高降1，那么通過調(diào)整保證x到a,b,c,d,e,f,g,h這些位置的相對黑高不變。

對于1.1，如果current子樹黑高降1，與之前一樣，直接將parent左旋，可以保證在調(diào)整前后，x到a,b,c,d,e的相對黑高保持不變，如圖：

對于1.2，如果current子樹黑高降1，與之前一樣，先將brother右旋，然后將parent變成黑色并左旋，也能保證x到a,b,c,d,e的相對黑高保持不變，如圖：

對于2.1，如果current子樹黑高降1，與之前一樣，將brother與左兒子換色，然后對parent左旋，可以保證x到a,b,c,d,e,f,g,h的相對黑高保持不變，如圖：

對于2.2，如果current子樹黑高降1，與之前一樣，將brother的左兒子的右子節(jié)點(diǎn)涂成黑色，然后對brother右旋，再對parent左旋，也可以保證x到a,b,c,d,e,f,g,h的相對黑高保持不變， 如圖(A涂成灰色表示其顏色可以紅或者黑，沒有影響)：

對于2.3，如果current子樹黑高降1，與之前一樣，先將brother的左兒子的左子節(jié)點(diǎn)涂成黑色，并對將brother的左兒子右旋，這樣將情形轉(zhuǎn)化成2.2，然后再進(jìn)行同樣的旋轉(zhuǎn)調(diào)整， 以保證x到a,b,c,d,e,f,g,h的相對黑高保持不變，如圖：

對于3.1，如果current子樹黑高降1，與之前一樣，依然只能降低brother的黑高，使x到a,b,c,d,e,f的相對黑高同時(shí)降1，然后將parent視為新的current子樹繼續(xù)向樹根追溯，如圖：

對于3.2，如果current子樹黑高降1，與之前一樣，將brother的右兒子涂黑，然后對parent左旋，也能保證x到a,b,c,d,e,f的相對黑高保持不變， 如圖(圖中將left涂成灰色表示其顏色可以紅或者黑，沒有影響)：

對于3.3，如果current子樹黑高降1，與之前一樣，先將brother的左兒子涂黑，然后對parent右旋，再對parent左旋，也能保證x到a,b,c,d,e,f的相對黑高保持不變，如圖：

總結(jié)節(jié)點(diǎn)刪除問題：首先將問題轉(zhuǎn)化為對樹葉的刪除，如果樹葉是紅色則直接刪除，如果是黑色，則根據(jù)兄弟節(jié)點(diǎn)和父節(jié)點(diǎn)的顏色情況來對情形進(jìn)行分類。想法是盡量在子樹中解決， 如果實(shí)在解決不了，就降低子樹的高度，并將子樹視為整體然后向樹根進(jìn)行追溯，直到問題解決。上面的分析中，對于刪除黑色樹葉的刪除，分成了8種情形，其中3.1需要向樹根追溯， 直到轉(zhuǎn)化成其它7種情形或到樹根為止才能解決。其次，2.3也需要轉(zhuǎn)化成2.2來解決，因此，對于黑色樹葉的刪除，實(shí)際上最后直接解決的情形可以歸結(jié)有6種。

3. java實(shí)現(xiàn)

繼承之前二叉查找樹的實(shí)現(xiàn)，重寫下插入和刪除，分別實(shí)現(xiàn)Set和MultiTreeMap

3.1. Set

 
 
 
 

  
  
  
  
public class RBTreeSet> extends BinarySearchTreeSet { 
  
  
  
  
 
  
  
  
  
  private RBNode header; 
  
  
  
  
 
  
  
  
  
  private RBNode nil; 
  
  
  
  
 
  
  
  
  
  public RBTreeSet() { 
  
  
  
  
    nil = new RBNode<>(null); 
  
  
  
  
    nil.left = nil; 
  
  
  
  
    nil.right = nil; 
  
  
  
  
    header = new RBNode<>(null, nil, nil); 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
  @Override 
  
  
  
  
  protected Node getRoot() { 
  
  
  
  
    return header.right; 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
  @Override 
  
  
  
  
  protected boolean isEmptyNode(Node node) { 
  
  
  
  
    return nil == node; 
  
  
  
  
  } 
  
  
  
  
   
  
  
  
  
  @Override 
  
  
  
  
  public void clear() { 
  
  
  
  
    header.right = nil; 
  
  
  
  
    size = 0; 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
  @Override 
  
  
  
  
  public boolean add(E e) { 
  
  
  
  
    RBNode current = header; 
  
  
  
  
    RBNode parent = header; 
  
  
  
  
    //先將nil的值設(shè)為e 
  
  
  
  
    nil.element = e; 
  
  
  
  
    //然后從header開始自上而下尋找值為e的節(jié)點(diǎn)a 
  
  
  
  
    while(compare(e, current) != 0){ 
  
  
  
  
      parent = current; 
  
  
  
  
      if(compare(e, current) < 0){ 
  
  
  
  
        current = getLeft(current); 
  
  
  
  
      }else{ 
  
  
  
  
        current = getRight(current); 
  
  
  
  
      } 
  
  
  
  
      //如果左右子節(jié)點(diǎn)都為紅色，則進(jìn)行顏色翻轉(zhuǎn)，避免插入時(shí)出現(xiàn)父親的兄弟節(jié)點(diǎn)為紅色的情況 
  
  
  
  
      if(getLeft(current).red && getRight(current).red){ 
  
  
  
  
        current = handleReorient(current); 
  
  
  
  
      } 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    //如果發(fā)現(xiàn)了值相同的重復(fù)節(jié)點(diǎn)，直接覆蓋 
  
  
  
  
    if(current != nil){ 
  
  
  
  
      current.element = e; 
  
  
  
  
      return true; 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    //新建一個(gè)數(shù)據(jù)節(jié)點(diǎn)代替nil，并將其左右子樹指向nil 
  
  
  
  
    current = new RBNode<>(e, nil, nil); 
  
  
  
  
    size++; 
  
  
  
  
 
  
  
  
  
    //當(dāng)while結(jié)束時(shí)，必然可以明確待插入節(jié)點(diǎn)的parent節(jié)點(diǎn)，這里使parent節(jié)點(diǎn)鏈接到新節(jié)點(diǎn) 
  
  
  
  
    current.parent = parent; 
  
  
  
  
    if(compare(e, parent) < 0){ 
  
  
  
  
      parent.left = current; 
  
  
  
  
    }else{ 
  
  
  
  
      parent.right = current; 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    //將新數(shù)據(jù)節(jié)點(diǎn)設(shè)成紅色，如果父親節(jié)點(diǎn)為紅色則需要旋轉(zhuǎn)調(diào)整 
  
  
  
  
    handleReorient(current); 
  
  
  
  
    return true; 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
  private RBNode getLeft(Node node){ 
  
  
  
  
    return (RBNode)node.left; 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
  private RBNode getRight(Node node){ 
  
  
  
  
    return (RBNode)node.right; 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
  private int compare(E e, Node node) { 
  
  
  
  
    if(node == header){ 
  
  
  
  
      return 1; 
  
  
  
  
    }else{ 
  
  
  
  
      return e.compareTo(node.element); 
  
  
  
  
    } 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
  private RBNode handleReorient(RBNode current) { 
  
  
  
  
    getLeft(current).red = false;   
  
  
  
  
    getRight(current).red = false;  
  
  
  
  
    current.red = true; 
  
  
  
  
 
  
  
  
  
    RBNode subRoot = current; 
  
  
  
  
    //翻轉(zhuǎn)之后發(fā)現(xiàn)parent也是紅色，進(jìn)行換色和旋轉(zhuǎn) 
  
  
  
  
    RBNode parent = current.parent; 
  
  
  
  
    if(parent.red){ 
  
  
  
  
      RBNode grand = parent.parent; 
  
  
  
  
      grand.red = true; 
  
  
  
  
      //旋轉(zhuǎn)parent, 向外旋轉(zhuǎn)到同一側(cè)  
  
  
  
  
      if(compare(current.element, grand) != compare(current.element, parent)) { 
  
  
  
  
        if(compare(current.element, parent) > 0){ 
  
  
  
  
          rotateLeft(parent); 
  
  
  
  
        }else{ 
  
  
  
  
          rotateRight(parent); 
  
  
  
  
        } 
  
  
  
  
      } 
  
  
  
  
      //旋轉(zhuǎn)grand 
  
  
  
  
      if(compare(current.element, grand) < 0){ 
  
  
  
  
        subRoot = getLeft(grand); 
  
  
  
  
        subRoot.red = false; 
  
  
  
  
        rotateRight(grand); 
  
  
  
  
      }else{ 
  
  
  
  
        subRoot = getRight(grand); 
  
  
  
  
        subRoot.red = false; 
  
  
  
  
        rotateLeft(grand); 
  
  
  
  
      } 
  
  
  
  
    } 
  
  
  
  
    //直接將根節(jié)點(diǎn)置為黑色  
  
  
  
  
    getRight(header).red = false; 
  
  
  
  
    return subRoot; 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
  private void rotateRight(RBNode node) { 
  
  
  
  
    RBNode parent = node.parent; 
  
  
  
  
    RBNode left = getLeft(node);  
  
  
  
  
    RBNode leftRight = getRight(left); 
  
  
  
  
    left.right = node; 
  
  
  
  
    node.parent = left; 
  
  
  
  
    node.left = leftRight; 
  
  
  
  
    leftRight.parent = node; 
  
  
  
  
    left.parent = parent; 
  
  
  
  
    if(parent.right == node){ 
  
  
  
  
      parent.right = left; 
  
  
  
  
    }else{ 
  
  
  
  
      parent.left = left; 
  
  
  
  
    } 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
  private void rotateLeft(RBNode node) { 
  
  
  
  
    RBNode parent = node.parent; 
  
  
  
  
    RBNode right = getRight(node);  
  
  
  
  
    RBNode rightLeft = getLeft(right); 
  
  
  
  
    right.left = node; 
  
  
  
  
    node.parent = right; 
  
  
  
  
    node.right = rightLeft; 
  
  
  
  
    rightLeft.parent = node; 
  
  
  
  
    right.parent = parent; 
  
  
  
  
    if(parent.right == node){ 
  
  
  
  
      parent.right = right; 
  
  
  
  
    }else{ 
  
  
  
  
      parent.left = right; 
  
  
  
  
    } 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
  @Override 
  
  
  
  
  public boolean remove(Object o) { 
  
  
  
  
    RBNode current = header; 
  
  
  
  
    RBNode parent = header; 
  
  
  
  
     
  
  
  
  
    @SuppressWarnings("unchecked") 
  
  
  
  
    E e = (E)o; 
  
  
  
  
    nil.element = e; 
  
  
  
  
    while(compare(e, current) != 0){ 
  
  
  
  
      parent = current; 
  
  
  
  
      if(compare(e, current) < 0){ 
  
  
  
  
        current = getLeft(current); 
  
  
  
  
      }else{ 
  
  
  
  
        current = getRight(current); 
  
  
  
  
      } 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    if(current == nil){ //沒有找到值為e的數(shù)據(jù)節(jié)點(diǎn) 
  
  
  
  
      return true; 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    size--; 
  
  
  
  
    RBNode node = current; 
  
  
  
  
    if(current.right != nil){ //替換右子樹最小節(jié)點(diǎn) 
  
  
  
  
      parent = current; 
  
  
  
  
      current = getRight(current); 
  
  
  
  
      while(current.left != nil){ 
  
  
  
  
        parent = current; 
  
  
  
  
        current = getLeft(current); 
  
  
  
  
      } 
  
  
  
  
      node.element = current.element; 
  
  
  
  
      //右側(cè)最小節(jié)點(diǎn)不是葉子，則繼續(xù)向下遍歷一層，這時(shí)可以斷定樹葉是紅色 
  
  
  
  
      if(current.right != nil){ 
  
  
  
  
        parent = current; 
  
  
  
  
        current = getRight(current); 
  
  
  
  
        parent.element = current.element; 
  
  
  
  
        parent.right = nil; 
  
  
  
  
        return true; 
  
  
  
  
      } 
  
  
  
  
    }else if(current.left != nil){ //替換左子樹最大節(jié)點(diǎn) 
  
  
  
  
      parent = current; 
  
  
  
  
      current = getLeft(node); 
  
  
  
  
      while(current.right != nil){ 
  
  
  
  
        parent = current; 
  
  
  
  
        current = getRight(current); 
  
  
  
  
      } 
  
  
  
  
      node.element = current.element; 
  
  
  
  
      //左側(cè)最大節(jié)點(diǎn)不是葉子，則繼續(xù)向下遍歷一層，這時(shí)可以斷定樹葉是紅色 
  
  
  
  
      if(current.left != nil){ 
  
  
  
  
        parent = current; 
  
  
  
  
        current = getLeft(current); 
  
  
  
  
        parent.element = current.element; 
  
  
  
  
        parent.left = nil; 
  
  
  
  
        return true; 
  
  
  
  
      } 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    //先調(diào)整再刪除，因?yàn)楹竺孢€需要依賴current與parent的位置關(guān)系判斷 
  
  
  
  
    if(!current.red){ 
  
  
  
  
      fixRemove(current); 
  
  
  
  
    } 
  
  
  
  
     
  
  
  
  
    //刪除樹葉leaf 
  
  
  
  
    if(current == parent.left){ 
  
  
  
  
      parent.left = nil; 
  
  
  
  
    }else{ 
  
  
  
  
      parent.right = nil; 
  
  
  
  
    } 
  
  
  
  
    return true; 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
  private void fixRemove(RBNode current){ 
  
  
  
  
    RBNode parent = current.parent; 
  
  
  
  
    if(parent == header){ 
  
  
  
  
      return; 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    if(current == parent.left){ 
  
  
  
  
      RBNode brother = getRight(parent); 
  
  
  
  
      if(parent.red){ // 1.parent為紅色 
  
  
  
  
        if(getLeft(brother).red){  
  
  
  
  
          parent.red = false; 
  
  
  
  
          rotateRight(brother); 
  
  
  
  
        } 
  
  
  
  
      }else if(brother.red){ // 2.brother為紅色 
  
  
  
  
        if(!getLeft(brother.left).red && !getRight(brother.left).red){ 
  
  
  
  
          brother.red = false; 
  
  
  
  
          getLeft(brother).red = true; 
  
  
  
  
        }else if(getRight(brother.left).red){ 
  
  
  
  
          getRight(brother.left).red = false; 
  
  
  
  
          rotateRight(brother); 
  
  
  
  
        }else{ 
  
  
  
  
          getLeft(brother.left).red = false; 
  
  
  
  
          rotateRight(getLeft(brother)); 
  
  
  
  
          rotateRight(brother); 
  
  
  
  
        } 
  
  
  
  
      }else{ // 3. parent和brother都為黑色 
  
  
  
  
        if(!getLeft(brother).red && !getRight(brother).red){  
  
  
  
  
          brother.red = true; 
  
  
  
  
          fixRemove(parent); 
  
  
  
  
          return; 
  
  
  
  
        }else if(getRight(brother).red){ 
  
  
  
  
          getRight(brother).red = false; 
  
  
  
  
        }else{ 
  
  
  
  
          getLeft(brother).red = false; 
  
  
  
  
          rotateRight(brother); 
  
  
  
  
        } 
  
  
  
  
      } 
  
  
  
  
      //最后一步的調(diào)整都是parent左旋 
  
  
  
  
      rotateLeft(parent); 
  
  
  
  
    }else{ // 對稱情形 
  
  
  
  
      RBNode brother = getLeft(parent);    
  
  
  
  
      if(parent.red){  
  
  
  
  
        if(getRight(brother).red){  
  
  
  
  
          parent.red = false; 
  
  
  
  
          rotateLeft(brother); 
  
  
  
  
        } 
  
  
  
  
      }else if(brother.red){     
  
  
  
  
        if(!getLeft(brother.right).red && !getRight(brother.right).red){ 
  
  
  
  
          brother.red = false; 
  
  
  
  
          getRight(brother).red = true; 
  
  
  
  
        }else if(getLeft(brother.right).red){ 
  
  
  
  
          getLeft(brother.right).red = false; 
  
  
  
  
          rotateLeft(brother); 
  
  
  
  
        }else{ 
  
  
  
  
          getRight(brother.right).red = false; 
  
  
  
  
          rotateLeft(getRight(brother)); 
  
  
  
  
          rotateLeft(brother); 
  
  
  
  
        } 
  
  
  
  
      }else{  
  
  
  
  
        if(!getLeft(brother).red && !getRight(brother).red){ 
  
  
  
  
          brother.red = true; 
  
  
  
  
          fixRemove(parent); 
  
  
  
  
          return; 
  
  
  
  
        }else if(getLeft(brother).red){ 
  
  
  
  
          getLeft(brother).red = false; 
  
  
  
  
        }else{ 
  
  
  
  
          getRight(brother).red = false; 
  
  
  
  
          rotateLeft(brother); 
  
  
  
  
        } 
  
  
  
  
      } 
  
  
  
  
      rotateRight(parent); 
  
  
  
  
    } 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
  static class RBNode extends Node { 
  
  
  
  
 
  
  
  
  
    RBNode parent; 
  
  
  
  
 
  
  
  
  
    boolean red; 
  
  
  
  
 
  
  
  
  
    RBNode(E e) { 
  
  
  
  
      super(e); 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    RBNode(E e, RBNode left, RBNode right) { 
  
  
  
  
      super(e); 
  
  
  
  
      this.left = left; 
  
  
  
  
      this.right = right; 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    @Override 
  
  
  
  
    public String toString() { 
  
  
  
  
      return red ? element.toString() + "(red)" : element.toString(); 
  
  
  
  
    } 
  
  
  
  
  } 
  
  
  
  
} 
 
 
 
 

3.2. MultiTreeMap

 
 
 
 

  
  
  
  
public class MultiRBTreeMap, V> extends MultiBinarySearchTreeMap { 
  
  
  
  
 
  
  
  
  
public MultiRBTreeMap() { 
  
  
  
  
 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
public MultiRBTreeMap(boolean deduplication, boolean asc){ 
  
  
  
  
super(deduplication, asc); 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
  @Override 
  
  
  
  
  protected void init() { 
  
  
  
  
nil = new RBNode(null, null, false, null, null); 
  
  
  
  
nil.left = nil; 
  
  
  
  
nil.right = nil; 
  
  
  
  
    header = new RBNode(null, null, false, nil, nil); 
  
  
  
  
    header.next = nil; 
  
  
  
  
nil.prev = header; 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
public V put(K key, V value){ 
  
  
  
  
nil.key = key; 
  
  
  
  
RBNode current = (RBNode)header; 
  
  
  
  
RBNode parent = (RBNode)header;  
  
  
  
  
while(compare(key, current) != 0){ 
  
  
  
  
      parent = current; 
  
  
  
  
if(compare(key, current) < 0){ 
  
  
  
  
        current = getLeft(current); 
  
  
  
  
      }else{ 
  
  
  
  
        current = getRight(current); 
  
  
  
  
      } 
  
  
  
  
if(getLeft(current).isRed && getRight(current).isRed){ 
  
  
  
  
        current = handleReorient(current); 
  
  
  
  
      } 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
if(current != nil){ 
  
  
  
  
if(deduplication){ 
  
  
  
  
V old = current.value; 
  
  
  
  
        current.key = key; 
  
  
  
  
        current.value = value; 
  
  
  
  
return old; 
  
  
  
  
      }else{ 
  
  
  
  
while((current = getNext(current)).isRepeat);  
  
  
  
  
V old = current.prev.value; 
  
  
  
  
        linkIn(new RBNode<>(key, value, true, nil, nil), current, false); 
  
  
  
  
return old; 
  
  
  
  
      } 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    current = new RBNode<>(key, value, false, nil, nil); 
  
  
  
  
    current.parent = parent; 
  
  
  
  
if(compare(key, parent) < 0){ 
  
  
  
  
      parent.left = current; 
  
  
  
  
      linkIn(current, parent, false); 
  
  
  
  
    }else{ 
  
  
  
  
      parent.right = current; 
  
  
  
  
while((parent = getNext(parent)).isRepeat); 
  
  
  
  
      linkIn(current, parent, false); 
  
  
  
  
    } 
  
  
  
  
//將新數(shù)據(jù)節(jié)點(diǎn)設(shè)成紅色，如果父親節(jié)點(diǎn)為紅色則需要旋轉(zhuǎn)調(diào)整 
  
  
  
  
    handleReorient(current); 
  
  
  
  
return null; 
  
  
  
  
  } 
  
  
  
  
 
  
  
  
  
private RBNode handleReorient(RBNode current) { 
  
  
  
  
    getLeft(current).isRed = false;   
  
  
  
  
    getRight(current).isRed = false;  
  
  
  
  
    current.isRed = true; 
  
  
  
  
 
  
  
  
  
RBNode subRoot = current;  
  
  
  
  
RBNode parent = getParent(current); 
  
  
  
  
if(parent.isRed){ 
  
  
  
  
RBNode grand = getParent(parent); 
  
  
  
  
      grand.isRed = true; 
  
  
  
  
//旋轉(zhuǎn)parent, 向外旋轉(zhuǎn)到同一側(cè)  
  
  
  
  
if(compare(current.getKey(), grand) != compare(current.getKey(), parent)) { 
  
  
  
  
if(compare(current.getKey(), parent) > 0){ 
  
  
  
  
          rotateLeft(parent); 
  
  
  
  
        }else{ 
  
  
  
  
          rotateRight(parent); 
  
  
  
  
        } 
  
  
  
  
      } 
  
  
  
  
//旋轉(zhuǎn)grand 
  
  
  
  
if(compare(current.getKey(), grand) < 0){ 
  
  
  
  
        subRoot = getLeft(grand); 
  
  
  
  
        subRoot.isRed = false; 
  
  
  
  
        rotateRight(grand); 
  
  
  
  
 &nb                                                

                                                當(dāng)前名稱：他一口氣寫出了這7k字的紅黑樹總結(jié)！看過的都說好??！                                                

                                                標(biāo)題網(wǎng)址：http://m.fisionsoft.com.cn/article/djdsoih.html