學(xué)習(xí)紅黑樹的思考

紅黑樹本質(zhì)是由2-3查找樹演變而成的二叉樹躬审，由于2-3查找樹需要維護(hù)兩種節(jié)點(diǎn)入蛆，在實現(xiàn)上很不方便因此出現(xiàn)了紅黑樹這種演變沟启。紅黑樹中的紅色節(jié)點(diǎn)與其父節(jié)點(diǎn)即為2-3查找樹中的3節(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)的個數(shù)相同
④根節(jié)點(diǎn)必為黑色
⑤如果節(jié)點(diǎn)是紅色创泄，則其子節(jié)點(diǎn)必為黑色

特性①紅色節(jié)點(diǎn)為左節(jié)點(diǎn)個人理解是為了方便實現(xiàn)和畫圖理解艺玲。特性②和⑤其實是一回事，如果一個節(jié)點(diǎn)存在兩個紅色節(jié)點(diǎn)則他便是一個4節(jié)點(diǎn)鞠抑，同樣的紅節(jié)點(diǎn)的子節(jié)點(diǎn)還是紅節(jié)點(diǎn)也等價于一個4節(jié)點(diǎn)饭聚。
紅黑樹可將紅節(jié)點(diǎn)橫過來作為其父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)看，就可以看出所有2搁拙、3節(jié)點(diǎn)秒梳。

實現(xiàn)

顏色表示

可以定義兩個常量表示顏色：

public static final RED = true;
public static final BLACK = false;

節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)

class Node {
  
  private Key key;
  private Value value;
  private boolean color;  //節(jié)點(diǎn)顏色
  private int size;  //以節(jié)點(diǎn)為根的樹的節(jié)點(diǎn)個數(shù)
  private Node right, left;
  
  public Node(Key key, Value value, boolean color, int size){
    this.key = key;
    this.value = value;
    this.color = color;
    this.size = size;
  }

}

紅黑樹的平衡實現(xiàn)

紅黑樹是平衡樹法绵，所以維持樹的平衡很關(guān)鍵，但需要考慮節(jié)點(diǎn)顏色這一過程通過旋轉(zhuǎn)和變色來實現(xiàn)酪碘。紅黑樹的旋轉(zhuǎn)可分為左旋轉(zhuǎn)和右旋轉(zhuǎn)朋譬。變色其實就是當(dāng)前節(jié)點(diǎn)和其左右節(jié)點(diǎn)顏色都變?yōu)橄喾吹募纯伞?br> 在此之前先定函數(shù)判斷節(jié)點(diǎn)的顏色。

public boolean isRed(Node node){
  if(node == null){
    return false;
  }
  return node.color;
}

1.變色

變色發(fā)生在當(dāng)前節(jié)點(diǎn)及其左右節(jié)點(diǎn)違反了特性②的基礎(chǔ)上兴垦。

插入S后違反了特性②

插入操作在插入節(jié)點(diǎn)的時候都是創(chuàng)建一個鍵值對應(yīng)的紅色節(jié)點(diǎn)徙赢，并通過后續(xù)的平衡修正保證平衡。上圖插入S后節(jié)點(diǎn)E有兩個紅色節(jié)點(diǎn)探越，變成了一個4節(jié)點(diǎn)狡赐，這種情況下使用變色方式調(diào)整平衡。

public void flipColors(Node node){
  node.color = !node.color;
  node.left.color = !node.left.color;
  node.right.color = !node.right.color;
}

變換后的效果

變色后

2.左旋轉(zhuǎn)

當(dāng)節(jié)點(diǎn)的左節(jié)點(diǎn)為黑色扶关，右節(jié)點(diǎn)是紅節(jié)點(diǎn)的情況下需要左旋轉(zhuǎn)阴汇。

需要左旋轉(zhuǎn)

左旋轉(zhuǎn)實現(xiàn)

public Node rorateLeft(Node node){
  Node temp = node.right;  //當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)
  node.right = temp.left;  //當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)變?yōu)槠溆夜?jié)點(diǎn)的左節(jié)點(diǎn)
  temp.left = node;  //當(dāng)前節(jié)點(diǎn)變?yōu)槠溆夜?jié)點(diǎn)的左節(jié)點(diǎn)
  //改變顏色
  temp.color = temp.left.color;
  temp.left.color = RED;
  temp.size = temp.left.size;
  //調(diào)整大小
  temp.left.size = size(temp.left.left) + size(temp.left.right) + 1;
  return temp;
}

旋轉(zhuǎn)后的樣子

左旋轉(zhuǎn)完成

旋轉(zhuǎn)函數(shù)以Node類型作為返回值，原因是旋轉(zhuǎn)過后當(dāng)前節(jié)點(diǎn)可能變?yōu)樾D(zhuǎn)后的子節(jié)點(diǎn)节槐，如圖h節(jié)點(diǎn)旋轉(zhuǎn)后成為x節(jié)點(diǎn)的左子結(jié)點(diǎn)搀庶，h節(jié)點(diǎn)即被其原右子節(jié)點(diǎn)x替代。

旋轉(zhuǎn)過程

3.右旋轉(zhuǎn)

右旋轉(zhuǎn)和左旋轉(zhuǎn)方向相反铜异，原節(jié)點(diǎn)的左子結(jié)點(diǎn)替換原節(jié)點(diǎn)哥倔，原節(jié)點(diǎn)變?yōu)槠渥笞咏Y(jié)點(diǎn)的右子節(jié)點(diǎn)。這種操作發(fā)生在當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)和其左節(jié)點(diǎn)的左節(jié)點(diǎn)都是紅色節(jié)點(diǎn)的情況下揍庄。

右旋轉(zhuǎn)前

右旋轉(zhuǎn)實現(xiàn)

public Node rorateRight(Node node){
  Node temp = node.left;  //記錄當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)
  node.left = temp.right;  //當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)變?yōu)槠渥蠊?jié)點(diǎn)的右節(jié)點(diǎn)
  temp.right = node;  //當(dāng)前節(jié)點(diǎn)變?yōu)槠渥蠊?jié)點(diǎn)的右節(jié)點(diǎn)
  //調(diào)整顏色
  temp.color = temp.right.color;
  temp.right.color = RED;
  //調(diào)整大小
  temp.size = temp.right.size;
  temp.right.size = size(temp.right.left) + size(temp.right.right) + 1;
  return temp;
}

右旋轉(zhuǎn)后

旋轉(zhuǎn)后

旋轉(zhuǎn)過程

補(bǔ)充

做旋轉(zhuǎn)和右旋轉(zhuǎn)中都有一個更新size的操作咆蒿，函數(shù)如下給出

public int size(Node node){
  if(null == node){
    return 0;
  }
  return 1 + size(node.left) + size(node.right);
}

三種旋轉(zhuǎn)和變色的操作在紅黑樹的插入和刪除操作后起著維持紅黑樹平衡的作用。

紅黑樹插入操作

插入操作從根節(jié)點(diǎn)出發(fā)蚂子，當(dāng)碰到Key值相等的節(jié)點(diǎn)時更新原值即結(jié)束沃测。否則，若當(dāng)前節(jié)點(diǎn)Key值大于插入的Key值食茎，繼續(xù)搜尋當(dāng)前節(jié)點(diǎn)的左子樹插入蒂破，否則右子樹插入。當(dāng)遇到空節(jié)點(diǎn)是創(chuàng)建新節(jié)點(diǎn)完成插入操作别渔。

public void insert(Key key, Value value){
  //key不可以為null
  if(null == key){
    throw new IllegalArgumentException("argument key of insert() can't be null");
  }
  //插入操作可能造成根節(jié)點(diǎn)變化
  root = insert(root, key, value);
  //保證根節(jié)點(diǎn)為BLACK
  root.color = BLACK;
}

private Node insert(Node node, Key key, Value value){
  //遇到null節(jié)點(diǎn)創(chuàng)建新節(jié)點(diǎn)
  if(null == node){
    node = new Node(key, value, RED, 1);
    return node;
  }
  //否則進(jìn)行比較
  int cmp = key.compareTo(node.key);
  if(cmp == 0){  //相等更新value即可
    node.value = value;
  }else if(cmp > 0){  //key大于node.key附迷，右子樹繼續(xù)插入操作
    node = insert(node.right, key, value);
  }else{  //key小于node.key，左子樹繼續(xù)插入操作
    node = insert(node.left, key, value);
  }
  //完成插入后哎媚，紅黑樹平衡可能被破壞喇伯，需要重新調(diào)整平衡
  insertBalance(node);
}

public void insertBalance(Node node){
  //當(dāng)前節(jié)點(diǎn)左節(jié)點(diǎn)為黑節(jié)點(diǎn)，右節(jié)點(diǎn)為紅節(jié)點(diǎn)——左旋轉(zhuǎn)
  if(!isRed(node.left) && isRed(node.right)){
    node = rorateLeft(node);
  }
  //當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)及其左節(jié)點(diǎn)的左節(jié)點(diǎn)為紅色節(jié)點(diǎn)——右旋轉(zhuǎn)
  if(isRed(node.left) && isRed(node.right)){
    node = rorateRight(node);
  }
  //當(dāng)前節(jié)點(diǎn)左右節(jié)點(diǎn)都是紅色節(jié)點(diǎn)——變色
  if(isRed(node.left) && isRed(node.right)){
    flipColors(node);
  }
  return node;
}

插入過程相對比較簡單拨与，注意的是插入新結(jié)點(diǎn)后進(jìn)行紅黑樹平衡調(diào)整的幾個條件不是if...else if的關(guān)系稻据，而是每部操作之后都需要進(jìn)行一次判斷，畢竟旋轉(zhuǎn)過程中任何情況都可能發(fā)生买喧。
每部插入操作后對當(dāng)前節(jié)點(diǎn)進(jìn)行調(diào)整捻悯，逐層向上遞歸箩朴，每層都調(diào)整平衡即可保證根節(jié)點(diǎn)處左右子樹的平衡和紅黑節(jié)點(diǎn)規(guī)范。

刪除操作

紅黑樹刪除操作相對復(fù)雜秋度，對于刪除的節(jié)點(diǎn)，如果節(jié)點(diǎn)是紅色節(jié)點(diǎn)直接刪除不會影響樹的平衡性钱床，如果是黑色節(jié)點(diǎn)荚斯，刪除后會造成當(dāng)前路徑上黑色節(jié)點(diǎn)數(shù)少1，違反了紅黑樹特性③查牌，因此在刪除過程中需要對樹的結(jié)構(gòu)進(jìn)行調(diào)整事期，刪除后依舊需要對樹的結(jié)構(gòu)進(jìn)行調(diào)整。
方便理解纸颜，由刪除最小鍵值兽泣、刪除最大鍵值和普通刪除操作展看。

1.刪除最小鍵值

如果最小鍵為紅色節(jié)點(diǎn)胁孙，直接刪除即可唠倦，不影響紅黑樹平衡。所以在遞歸刪除的過程中涮较，需要保證最小節(jié)點(diǎn)為紅色節(jié)點(diǎn)稠鼻，那么在遞歸刪除的過程中，需要保證當(dāng)前節(jié)點(diǎn)或者其左節(jié)點(diǎn)為紅色狂票。
原因：

①如果當(dāng)前節(jié)點(diǎn)是紅色且是最小鍵候齿，直接刪除即可
②當(dāng)前節(jié)點(diǎn)是3節(jié)點(diǎn)中的黑色節(jié)點(diǎn)，繼續(xù)遞歸闺属，下一個節(jié)點(diǎn)定是紅色節(jié)點(diǎn)慌盯，只需要判斷紅色節(jié)點(diǎn)是否是最小鍵即可

保證當(dāng)前節(jié)點(diǎn)或者其左節(jié)點(diǎn)是紅色節(jié)點(diǎn)的實現(xiàn)：從當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)入手，如果不能保證左節(jié)點(diǎn)是3節(jié)點(diǎn)或4節(jié)點(diǎn)（即不是2節(jié)點(diǎn)）時掂器，就需要從當(dāng)前節(jié)點(diǎn)右子樹中借一個節(jié)點(diǎn)亚皂，通過旋轉(zhuǎn)和變色實現(xiàn)。
①借一個節(jié)點(diǎn)使得當(dāng)前節(jié)點(diǎn)為紅節(jié)點(diǎn)唉匾，對應(yīng)2-3樹中的4節(jié)點(diǎn)

當(dāng)前節(jié)點(diǎn)變?yōu)榧t節(jié)點(diǎn)

Ｔ谢洹！巍膘！注意這里的h節(jié)點(diǎn)指的是當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)

②借一個節(jié)點(diǎn)使得當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為紅色節(jié)點(diǎn)厂财，對應(yīng)2-3樹中的3節(jié)點(diǎn)

當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)變?yōu)榧t色

！Ｏ啃浮璃饱！注意這里的h節(jié)點(diǎn)指的是當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)

public void deleteMin(){
  //空樹無法刪除
  if(null == root){
    throw new NoSuchElementException("tree is empty!");
  }
  //根節(jié)點(diǎn)左右節(jié)點(diǎn)都為黑色節(jié)點(diǎn)，置根節(jié)點(diǎn)為紅色
  if(!isRed(root.left) && !isRed(root.right)){
    root.color = RED;
  }
  root = deleteMin(root);
  //樹非空肪康，根節(jié)點(diǎn)顏色置黑
  if(!isEmpty()){
    root.color = BLACK;
  }
}

private Node deleteMin(Node node){
  //當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null荚恶，即為最小節(jié)點(diǎn)
  if(null == node.left){
    return null;
  }
  //保證當(dāng)前節(jié)點(diǎn)或其左節(jié)點(diǎn)為紅色撩穿，注意是從父節(jié)點(diǎn)入手
  if(!isRed(node.left) && !isRed(node.left.left)){
    //制造紅色節(jié)點(diǎn)
    node = moveRedLeft(node);
  }
  //遞歸刪除最小鍵節(jié)點(diǎn)
  node = deleteMin(node.left);
  //調(diào)整平衡
  return deleteBalance(node);
}

private Node moveRedLeft(Node node){
  //先變色
  flipColors(node);
  //判斷節(jié)點(diǎn)右節(jié)點(diǎn)的左節(jié)點(diǎn)是否紅色，若是谒撼，按第二種方式操作
  if(isRed(node.right.left)){
    node.right = rorateRight(node.right);
    node = rorateLeft(node);
    flipColors(node);
  }
  return node;
}

private Node deleteBalance(Node node){
  if(isRed(node.right)){
    node = rorateLeft(node);
  }
  if(isRed(node.left) && isRed(node.right)){
    node = rorateRight(node);
  }
  if(isRed(node.left) && isRed(node.right)){
    flipColors(node);
  }
  return node;
}

moveRedLeft()函數(shù)即上面兩張圖片對應(yīng)的轉(zhuǎn)換操作食寡，當(dāng)當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)的左節(jié)點(diǎn)顏色為紅色時按照第二種方式進(jìn)行轉(zhuǎn)換，將當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)的左節(jié)點(diǎn)變成紅色廓潜。否則當(dāng)前節(jié)點(diǎn)左節(jié)點(diǎn)為紅色抵皱，左節(jié)點(diǎn)的左節(jié)點(diǎn)為黑色。（看代碼更好理解）

2.刪除最大鍵值節(jié)點(diǎn)

最大鍵刪除和最小鍵正好相反辩蛋，刪除最大鍵的過程就是保證當(dāng)前節(jié)點(diǎn)或當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為紅色節(jié)點(diǎn)呻畸，保證刪除后不會破壞紅黑樹平衡。將當(dāng)前節(jié)點(diǎn)或其右節(jié)點(diǎn)變?yōu)榧t色的過程也需要從其父節(jié)點(diǎn)入手悼院。
①生成一個4節(jié)點(diǎn)

當(dāng)前節(jié)點(diǎn)變成紅色

Ｉ宋！据途！注意這里的h節(jié)點(diǎn)指的是當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
②借一個節(jié)點(diǎn)使得當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為紅色節(jié)點(diǎn)绞愚，對應(yīng)2-3樹中的3節(jié)點(diǎn)

當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)變?yōu)榧t色

！Ｓ币健爽醋！注意這里的h節(jié)點(diǎn)指的是當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)

public void deleteMax(){
  //檢查二叉樹非空
  if(isEmpty()){
    throw new NoSuchElementException("tree is empty!");
  }
  //當(dāng)根節(jié)點(diǎn)左右節(jié)點(diǎn)都為黑色節(jié)點(diǎn)，將根節(jié)點(diǎn)變紅
  if(!isRed(root.left) && !isRed(root.right)){
    root.color = RED;
  }
  //刪除最大鍵便脊，刪除過程根節(jié)點(diǎn)可能變化
  root = deleteMax(root);
  //樹非空蚂四，保證根節(jié)點(diǎn)為黑色
  if(!isEmpty()){
    root.color = BLACK;
  }
}

private Node deleteMax(Node node){
  //當(dāng)前節(jié)點(diǎn)存在紅色左節(jié)點(diǎn)，進(jìn)行右旋轉(zhuǎn)創(chuàng)造紅色的右節(jié)點(diǎn)
  if(isRed(node.left)){
    node = rorateRight(node);
  }
  //節(jié)點(diǎn)無右節(jié)點(diǎn)哪痰，即為最大鍵遂赠，刪除
  if(null == node.right){
    return null;
  }
  //保證node或node.right為紅節(jié)點(diǎn)，注意也是從父節(jié)點(diǎn)入手
  //因為3節(jié)點(diǎn)是用紅節(jié)點(diǎn)來模擬的晌杰，紅節(jié)點(diǎn)不可能是右孩子跷睦，所以不可能是h.right.right
  if(!isRed(node.right) && !isRed(node.right.left)){
    node = moveRedRight(node);
  }
  node.right = deleteMax(node.right);
  //注意刪除后需要重新平衡紅黑樹
  return deleteBalance(node);
}

private Node moveRedRight(Node node){
  //變色
  flipColors(node);
  //相當(dāng)于完成圖2，將右節(jié)點(diǎn)的右節(jié)點(diǎn)變紅肋演，創(chuàng)造3節(jié)點(diǎn)操作
  if(isRed(node.left.left)){
    node = rorateRight(node);
    flipColors(node);
  }
  return node;
}

3.刪除操作

刪除操作結(jié)合了1抑诸、2中所講的兩種制造紅色節(jié)點(diǎn)的操作，直接看代碼配合1爹殊、2中的圖更方便理解蜕乡。

public void delete(Key key){
  //判斷樹非空
  if(isEmpty()){
    throw new NoSuchElementException("tree is empty!");
  }
  //key不得為null
  if(null == key){
    throw new IllegalArgumentException("argument of delete can't be null");
  }
  //檢查鍵是否存在
  if(!contains(key)){
    return ;
  }
  //根節(jié)點(diǎn)左右節(jié)點(diǎn)都是黑色，根節(jié)點(diǎn)變紅
  if(!isRed(root.left) && !isRed(root.right)){
    root.color = RED;
  }
  root = delete(root, key);
  //樹非空梗夸，根節(jié)點(diǎn)為黑色
  if(!isEmpty()){
    root.color = BLACK;
  }
}

private Node delete(Node node, Key key){
  //當(dāng)前節(jié)點(diǎn)的鍵大于待刪除的鍵层玲，需要在當(dāng)前節(jié)點(diǎn)左子樹中遞歸刪除
  //當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)都是黑色節(jié)點(diǎn)，通過moveRedLeft創(chuàng)造紅色左節(jié)點(diǎn)
  if(key.compareTo(node.key) < 0){
    if(!isRed(node.left) && !isRed(node.left.left)){
      node = moveRedLeft(node);
    }
    node.left = delete(node.left, key);
  }else{  //待刪除的鍵大于等于當(dāng)前節(jié)點(diǎn)的鍵
    //如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為紅色——右旋轉(zhuǎn)
    //該步操作創(chuàng)造紅色右節(jié)點(diǎn)
    if(isRed(node.left)){
      node = rorateRight(node);
    }
    //如果待刪除key與當(dāng)前節(jié)點(diǎn)key相等，切當(dāng)前節(jié)點(diǎn)右節(jié)點(diǎn)為空——可以直接刪除
    if(key.compareTo(node.key) == 0 && node.right == null){
      return null;
    }
    //當(dāng)前節(jié)點(diǎn)key小于待刪除的key辛块，需要在其右子樹中進(jìn)行刪除
    //當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)都是黑色節(jié)點(diǎn)畔派，通過moveRedRight創(chuàng)造紅色右節(jié)點(diǎn)
    if(!isRed(node.right) && !isRed(node.right.left)){
      node = moveRedRight(node);
    }
    //旋轉(zhuǎn)后的當(dāng)前節(jié)點(diǎn)key若等于待刪除key
    //替換當(dāng)前節(jié)點(diǎn)為其右子樹的最小節(jié)點(diǎn)，之后刪除其右子樹的最小節(jié)點(diǎn)即可
    if(key.compareTo(node.key) == 0){
      Node temp = min(node.right);
      node.key = temp.key;
      node.value = temp.value;
      node.right = deleteMin(node.right);
    }else{  //若不相等润绵，繼續(xù)在右子樹中執(zhí)行刪除操作
      node.right = delete(node.right, key);
    }
    return deleteBalance(node);
  }

Ｏ咭！尘盼！注意士嚎，這里不能再函數(shù)的開頭使用一個int值記錄當(dāng)前節(jié)點(diǎn)key和待刪除key的比較結(jié)果，因為在后續(xù)過程中悔叽，moveRedLeft和moveRedRight操作可能改變當(dāng)前節(jié)點(diǎn)所指向的節(jié)點(diǎn)，因此爵嗅，每次變換完都需要重新進(jìn)行比較娇澎。

給出完整的紅黑樹操作

public class RedBlackTree <Key extends Comparable, Value>{

  private Node root;
  private static final boolean RED = true;
  private static final boolean BLACK = false;

  private class Node{

    private Key key;
    private Value value;
    private boolean color;
    private int size;
    
    public Node(Key key, Value value, boolean color, int size){
      this.key = key;
      this.value = value;
      this.color = color;
      this.size = size;
    }

  }

  private boolean isRed(Node node){
    if(null == node){
      return false;
    }
    return node.color;
  }

  private int size(Node node){
    if(null == node){
      return 0;
    }
    return 1 + size(node.left) + size(node.right);
  }

  public boolean isEmpty(){
    return null == root;
  }

  public Node min(){
    if(isEmpty()){
      return null;
    }
    return min(root);
  }

  private Node min(Node node){
    if(null == node.left){
      return node;
    }
    return min(node.left);
  }

  public Node max(){
    if(isEmpty()){
      return null;
    }
    return max(root);
  }

  private Node max(Node node){
    if(null == node.right){
      return node;
    }
    return node.right;
  }

  public Value get(Key key){
    if(null == key){
      throw new IllegalArgumentException("argument of get() can't be null!");
    }
    return get(root, key);
  }

  private Value get(Node node, Key key){
    if(null == node){
      return null;
    }
    int cmp = key.compareTo(node.key);
    if(cmp == 0){
      return node.value;
    }else if(cmp > 0){
      return get(node.right, key);
    }else{
      return get(node.left, key);
    }
  }

  public boolean contains(Key key){
    if(null == get(key)){
      return false;  
    }
    return true;
  }

  public void insert(Key key, Value value){
    if(null == key){
      throw new IllegalArgumentException("argument of get() can't be null!");
    }
    root = insert(root, key, value);
    root.color = BLACK;
  }

  private Node insert(Node node, Key key, Value value){
    if(null == node){
      node = new Node(key, value, RED, 1);
      return node;
    }
    int cmp = key.compareTo(node.key);
    if(cmp == 0){
      node.value = value;
    }else if(cmp > 0){
      node.right = insert(node.right, key, value);
    }else{
      node.left = insert(node.left, key, value);
    }
    return insertBalance(node);
  }

  public void deleteMin(){
    if(isEmpty()){
      throw new NoSuchElementException("tree is empty!");
    }
    if(!isRed(root.left) && !isRed(root.right)){
      root.color = RED;
    }
    root = deleteMin(root);
    if(!isEmpty()){
      root.color = BLACK;
    }
  }

  private Node deleteMin(Node node){
    if(null == node.left){
      return null;
    }
    if(!isRed(node.left) && !isRed(node.left.left)){
      node = moveRedLeft(node);
    }
    node.left = deleteMin(node.left);
    return deleteBalance(node);
  }

  public void deleteMax(){
    if(isEmpty()){
      throw new NoSuchElementException("tree is empty!");
    }
    if(!isRed(root.left) && !isRed(root.right)){
      root.color = RED;
    }
    root = deleteMax(root);
    if(isEmpty()){
      root.color = BLACK;
    }
  }

  private Node deleteMax(Node node){
    if(null == node.right){
      return null;
    }
    if(!isRed(node.right) && !isRed(node.right.left)){
      node = moveRedRight(node);
    }
    node.right = deleteMax(node.right);
    return deleteBalance(node);
  }

  public void delete(Key key){
    if(!contains(key)){
      return ;
    }
    if(null == key){
      throw new IllegalArgumentException("argument of get() can't be null!");
    }
    if(!isRed(root.left) && !isRed(root.right)){
      root.color = RED;
    }
    root = delete(root, key);
    if(!isEmpty()){
      root.color = BLACK;
    }
  }

  private Node delete(Node node, Key key){
    if(key.compareTo(node.key) < 0){
      if(!isRed(node.left) && !isRed(node.left.left)){
        node = moveRedLeft(node);
      }
      node.left = delete(node.left, key);
    }else{
      if(isRed(node.left)){
        node = rorateRight(node);
      }
      if(key.compareTo(node.key) == 0 && null == node.right){
        return null;
      }
      if(!isRed(node.right) && !isRed(node.right.left)){
        node = moveRedRight(node);
      }
      if(key.compareTo(node.key) == 0){
        Node temp = min(node.right);
        node.key = temp.key;
        node.value = temp.value;
        node.right = deleteMin(node.right);
      }else{
        node.right = delete(node.right, key);
      }
    }
    return deleteBalance(node);
  }

  private Node insertBalance(Node node){
    if(!isRed(node.left) && isRed(node.right)){
      node = rorateLeft(node);
    }
    if(isRed(node.left) && isRed(node.left.left)){
      node = rorateRight(node);
    }
    if(isRed(node.left) && isRed(node.right)){
      flipColors(node);
    }
    return node;
  }

  private Node deleteBalance(Node node){
      if(isRed(node.right)){
        node = rorateLeft(node);
      }
      if(isRed(node.left) && isRed(node.left.left)){
        node = rorateRight(node);
      }
      if(isRed(node.left) && isRed(node.right)){
        flipColors(node);
      }
      return node;
  }

  private void flipColors(Node node){
    node.color = !node.color;
    node.left.color = !node.left.color;
    node.right.color = !node.right.color;
  }

  private Node rorateLeft(Node node){
    Node temp = node.right;
    node.right = temp.left;
    temp.left = node;
    temp.color = node.color;
    node.color = RED;
    temp.size = node.size;
    node.size = 1 + size(node.left) + size(node.right);
    return temp;
  }

  private Node rorateRight(Node node){
    Node temp = node.left;
    node.left = temp.right;
    temp.right = node;
    temp.color = node.color;
    node.color = RED;
    temp.size = node.size;
    node.size = 1 + size(node.left) + size(node.right);
    return temp;
  }

  private Node moveRedLeft(Node node){
      flipColors(node);
      if(isRed(node.right.left)){
        node.right = rorateRight(node.right);
        node = rorateLeft(node);
        flipColors(node);
      }
      return node;
  }

}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市睹晒，隨后出現(xiàn)的幾起案子趟庄，更是在濱河造成了極大的恐慌，老刑警劉巖伪很，帶你破解...
沈念sama閱讀 211,194評論 6贊 490
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件戚啥，死亡現(xiàn)場離奇詭異，居然都是意外死亡锉试，警方通過查閱死者的電腦和手機(jī)猫十，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,058評論 2贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來呆盖，“玉大人拖云，你說我怎么就攤上這事∮τ郑” “怎么了宙项？”我有些...
開封第一講書人閱讀 156,780評論 0贊 346
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長株扛。經(jīng)常有香客問我尤筐，道長，這世上最難降的妖魔是什么洞就？我笑而不...
開封第一講書人閱讀 56,388評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任盆繁，我火速辦了婚禮，結(jié)果婚禮上旬蟋，老公的妹妹穿的比我還像新娘改基。我一直安慰自己，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 65,430評論 5贊 384
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布秕狰。她就那樣靜靜地躺著稠腊，像睡著了一般。火紅的嫁衣襯著肌膚如雪鸣哀。梳的紋絲不亂的頭發(fā)上架忌，一...
開封第一講書人閱讀 49,764評論 1贊 290
城市分裂傳說
那天，我揣著相機(jī)與錄音我衬，去河邊找鬼叹放。笑死，一個胖子當(dāng)著我的面吹牛挠羔，可吹牛的內(nèi)容都是我干的井仰。我是一名探鬼主播，決...
沈念sama閱讀 38,907評論 3贊 406
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼破加，長吁一口氣：“原來是場噩夢啊……” “哼俱恶！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起范舀，我...
開封第一講書人閱讀 37,679評論 0贊 266
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤合是，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后锭环，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體聪全，經(jīng)...
沈念sama閱讀 44,122評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,459評論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年辅辩，在試婚紗的時候發(fā)現(xiàn)自己被綠了难礼。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,605評論 1贊 340
活死人
序言：一個原本活蹦亂跳的男人離奇死亡玫锋，死狀恐怖鹤竭，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情景醇，我是刑警寧澤臀稚，帶...
沈念sama閱讀 34,270評論 4贊 329
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站三痰，受9級特大地震影響吧寺，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜散劫，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,867評論 3贊 312
男人毒藥：我在死后第九天來索命
文/蒙蒙一稚机、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧获搏，春花似錦赖条、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,734評論 0贊 21
一樁弒父案纬乍，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽碱茁。三九已至，卻和暖如春仿贬，著一層夾襖步出監(jiān)牢的瞬間纽竣，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 31,961評論 1贊 265
情欲美人皮
我被黑心中介騙來泰國打工茧泪，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留蜓氨，地道東北人。一個月前我還...
沈念sama閱讀 46,297評論 2贊 360
代替公主和親
正文我出身青樓队伟，卻偏偏與公主長得像穴吹，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子嗜侮，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,472評論 2贊 348