日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

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

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

1. 定義

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

顏色規(guī)則：

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

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

2. 分析實現(xiàn)

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

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

2.1. 插入

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

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

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

先分析一下插入之前的可能情形，根據(jù)規(guī)則3，如果parent是紅色，那么可以斷定grand以及parent的另一個子節(jié)點一定是黑色。不僅如此，因為插入的是樹葉節(jié)點在之前一定是nil， 那么parent的另一個子節(jié)點必然也是nil，否則插入之前parent就違反了規(guī)則4。

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

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

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

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

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

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

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

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

以情況3為例：

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

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

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

只有當X的parent為紅色時，才會破壞紅黑樹的規(guī)則。不過這時可以斷定X的兄弟節(jié)點，X的grand，以及X的uncle都是黑色的(因為如果X的parent和uncle都為紅色， 那么一定會在自上而下的查找和翻轉過程中被過濾掉)。

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

先對X與其子節(jié)點進行顏色翻轉

然后，將X視為之前的current，對parent和grand進行換色和旋轉

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

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

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

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

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

2.2. 刪除

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

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

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

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

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

1.parent為紅色，brother為黑色

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

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

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

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

2.parent為黑色，brother為紅色

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

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

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

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

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

3.parent為黑色，brother為黑色

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

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

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

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

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

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

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

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

為了更好的說明，圖中用x標出樹根， 并用a,b,c,d,e,f,g,h標出樹根下面的一些相對位置(可以將這些位置看成nil，只是圖中做了省略，沒有畫出current和brother到這些nil的完整路徑)。所有圖的最終目標的都是保證：如果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é)點涂成黑色，然后對brother右旋，再對parent左旋，也可以保證x到a,b,c,d,e,f,g,h的相對黑高保持不變， 如圖(A涂成灰色表示其顏色可以紅或者黑，沒有影響)：

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

對于3.1，如果current子樹黑高降1，與之前一樣，依然只能降低brother的黑高，使x到a,b,c,d,e,f的相對黑高同時降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é)點刪除問題：首先將問題轉化為對樹葉的刪除，如果樹葉是紅色則直接刪除，如果是黑色，則根據(jù)兄弟節(jié)點和父節(jié)點的顏色情況來對情形進行分類。想法是盡量在子樹中解決， 如果實在解決不了，就降低子樹的高度，并將子樹視為整體然后向樹根進行追溯，直到問題解決。上面的分析中，對于刪除黑色樹葉的刪除，分成了8種情形，其中3.1需要向樹根追溯， 直到轉化成其它7種情形或到樹根為止才能解決。其次，2.3也需要轉化成2.2來解決，因此，對于黑色樹葉的刪除，實際上最后直接解決的情形可以歸結有6種。

3. java實現(xiàn)

繼承之前二叉查找樹的實現(xiàn)，重寫下插入和刪除，分別實現(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的值設為e 
  
  
  
  
    nil.element = e; 
  
  
  
  
    //然后從header開始自上而下尋找值為e的節(jié)點a 
  
  
  
  
    while(compare(e, current) != 0){ 
  
  
  
  
      parent = current; 
  
  
  
  
      if(compare(e, current) < 0){ 
  
  
  
  
        current = getLeft(current); 
  
  
  
  
      }else{ 
  
  
  
  
        current = getRight(current); 
  
  
  
  
      } 
  
  
  
  
      //如果左右子節(jié)點都為紅色，則進行顏色翻轉，避免插入時出現(xiàn)父親的兄弟節(jié)點為紅色的情況 
  
  
  
  
      if(getLeft(current).red && getRight(current).red){ 
  
  
  
  
        current = handleReorient(current); 
  
  
  
  
      } 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    //如果發(fā)現(xiàn)了值相同的重復節(jié)點，直接覆蓋 
  
  
  
  
    if(current != nil){ 
  
  
  
  
      current.element = e; 
  
  
  
  
      return true; 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    //新建一個數(shù)據(jù)節(jié)點代替nil，并將其左右子樹指向nil 
  
  
  
  
    current = new RBNode<>(e, nil, nil); 
  
  
  
  
    size++; 
  
  
  
  
 
  
  
  
  
    //當while結束時，必然可以明確待插入節(jié)點的parent節(jié)點，這里使parent節(jié)點鏈接到新節(jié)點 
  
  
  
  
    current.parent = parent; 
  
  
  
  
    if(compare(e, parent) < 0){ 
  
  
  
  
      parent.left = current; 
  
  
  
  
    }else{ 
  
  
  
  
      parent.right = current; 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    //將新數(shù)據(jù)節(jié)點設成紅色，如果父親節(jié)點為紅色則需要旋轉調(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; 
  
  
  
  
    //翻轉之后發(fā)現(xiàn)parent也是紅色，進行換色和旋轉 
  
  
  
  
    RBNode parent = current.parent; 
  
  
  
  
    if(parent.red){ 
  
  
  
  
      RBNode grand = parent.parent; 
  
  
  
  
      grand.red = true; 
  
  
  
  
      //旋轉parent, 向外旋轉到同一側  
  
  
  
  
      if(compare(current.element, grand) != compare(current.element, parent)) { 
  
  
  
  
        if(compare(current.element, parent) > 0){ 
  
  
  
  
          rotateLeft(parent); 
  
  
  
  
        }else{ 
  
  
  
  
          rotateRight(parent); 
  
  
  
  
        } 
  
  
  
  
      } 
  
  
  
  
      //旋轉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é)點置為黑色  
  
  
  
  
    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é)點 
  
  
  
  
      return true; 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    size--; 
  
  
  
  
    RBNode node = current; 
  
  
  
  
    if(current.right != nil){ //替換右子樹最小節(jié)點 
  
  
  
  
      parent = current; 
  
  
  
  
      current = getRight(current); 
  
  
  
  
      while(current.left != nil){ 
  
  
  
  
        parent = current; 
  
  
  
  
        current = getLeft(current); 
  
  
  
  
      } 
  
  
  
  
      node.element = current.element; 
  
  
  
  
      //右側最小節(jié)點不是葉子，則繼續(xù)向下遍歷一層，這時可以斷定樹葉是紅色 
  
  
  
  
      if(current.right != nil){ 
  
  
  
  
        parent = current; 
  
  
  
  
        current = getRight(current); 
  
  
  
  
        parent.element = current.element; 
  
  
  
  
        parent.right = nil; 
  
  
  
  
        return true; 
  
  
  
  
      } 
  
  
  
  
    }else if(current.left != nil){ //替換左子樹最大節(jié)點 
  
  
  
  
      parent = current; 
  
  
  
  
      current = getLeft(node); 
  
  
  
  
      while(current.right != nil){ 
  
  
  
  
        parent = current; 
  
  
  
  
        current = getRight(current); 
  
  
  
  
      } 
  
  
  
  
      node.element = current.element; 
  
  
  
  
      //左側最大節(jié)點不是葉子，則繼續(xù)向下遍歷一層，這時可以斷定樹葉是紅色 
  
  
  
  
      if(current.left != nil){ 
  
  
  
  
        parent = current; 
  
  
  
  
        current = getLeft(current); 
  
  
  
  
        parent.element = current.element; 
  
  
  
  
        parent.left = nil; 
  
  
  
  
        return true; 
  
  
  
  
      } 
  
  
  
  
    } 
  
  
  
  
 
  
  
  
  
    //先調(diào)整再刪除，因為后面還需要依賴current與parent的位置關系判斷 
  
  
  
  
    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é)點設成紅色，如果父親節(jié)點為紅色則需要旋轉調(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; 
  
  
  
  
//旋轉parent, 向外旋轉到同一側  
  
  
  
  
if(compare(current.getKey(), grand) != compare(current.getKey(), parent)) { 
  
  
  
  
if(compare(current.getKey(), parent) > 0){ 
  
  
  
  
          rotateLeft(parent); 
  
  
  
  
        }else{ 
  
  
  
  
          rotateRight(parent); 
  
  
  
  
        } 
  
  
  
  
      } 
  
  
  
  
//旋轉grand 
  
  
  
  
if(compare(current.getKey(), grand) < 0){ 
  
  
  
  
        subRoot = getLeft(grand); 
  
  
  
  
        subRoot.isRed = false; 
  
  
  
  
        rotateRight(grand); 
  
  
  
  
 &nb                                                

                                                分享標題：他一口氣寫出了這7k字的紅黑樹總結！看過的都說好?。?                                               

                                                標題來源：http://www.dlmjj.cn/article/djdsoih.html