学习红黑树的思考

红黑树本质是由2-3查找树演变而成的二叉树，由于2-3查找树需要维护两种节点，在实现上很不方便因此出现了红黑树这种演变。红黑树中的红色节点与其父节点即为2-3查找树中的3节点。黑色节点即为正常的节点。

红黑树的特性

①红节点均为左节点
②不存在拥有两个红子节点的节点
③红黑树是平衡二叉树，任意叶子结点到根节点的路径上黑色节点的个数相同
④根节点必为黑色
⑤如果节点是红色，则其子节点必为黑色

特性①红色节点为左节点个人理解是为了方便实现和画图理解。特性②和⑤其实是一回事，如果一个节点存在两个红色节点则他便是一个4节点，同样的红节点的子节点还是红节点也等价于一个4节点。
红黑树可将红节点横过来作为其父节点的兄弟节点看，就可以看出所有2、3节点。

实现

颜色表示

可以定义两个常量表示颜色：

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

节点数据结构

class Node {
  
  private Key key;
  private Value value;
  private boolean color;  //节点颜色
  private int size;  //以节点为根的树的节点个数
  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;
  }

}

红黑树的平衡实现

红黑树是平衡树，所以维持树的平衡很关键，但需要考虑节点颜色这一过程通过旋转和变色来实现。红黑树的旋转可分为左旋转和右旋转。变色其实就是当前节点和其左右节点颜色都变为相反的即可。
在此之前先定函数判断节点的颜色。

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

1.变色

变色发生在当前节点及其左右节点违反了特性②的基础上。

插入S后违反了特性②

插入操作在插入节点的时候都是创建一个键值对应的红色节点，并通过后续的平衡修正保证平衡。上图插入S后节点E有两个红色节点，变成了一个4节点，这种情况下使用变色方式调整平衡。

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

变换后的效果

变色后

2.左旋转

当节点的左节点为黑色，右节点是红节点的情况下需要左旋转。

需要左旋转

左旋转实现

public Node rorateLeft(Node node){
  Node temp = node.right;  //当前节点的右节点
  node.right = temp.left;  //当前节点的右节点变为其右节点的左节点
  temp.left = node;  //当前节点变为其右节点的左节点
  //改变颜色
  temp.color = temp.left.color;
  temp.left.color = RED;
  temp.size = temp.left.size;
  //调整大小
  temp.left.size = size(temp.left.left) + size(temp.left.right) + 1;
  return temp;
}

旋转后的样子

左旋转完成

旋转函数以Node类型作为返回值，原因是旋转过后当前节点可能变为旋转后的子节点，如图h节点旋转后成为x节点的左子结点，h节点即被其原右子节点x替代。

旋转过程

3.右旋转

右旋转和左旋转方向相反，原节点的左子结点替换原节点，原节点变为其左子结点的右子节点。这种操作发生在当前节点的左节点和其左节点的左节点都是红色节点的情况下。

右旋转前

右旋转实现

public Node rorateRight(Node node){
  Node temp = node.left;  //记录当前节点的左节点
  node.left = temp.right;  //当前节点的左节点变为其左节点的右节点
  temp.right = node;  //当前节点变为其左节点的右节点
  //调整颜色
  temp.color = temp.right.color;
  temp.right.color = RED;
  //调整大小
  temp.size = temp.right.size;
  temp.right.size = size(temp.right.left) + size(temp.right.right) + 1;
  return temp;
}

右旋转后

旋转后

旋转过程

补充

做旋转和右旋转中都有一个更新size的操作，函数如下给出

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

三种旋转和变色的操作在红黑树的插入和删除操作后起着维持红黑树平衡的作用。

红黑树插入操作

插入操作从根节点出发，当碰到Key值相等的节点时更新原值即结束。否则，若当前节点Key值大于插入的Key值，继续搜寻当前节点的左子树插入，否则右子树插入。当遇到空节点是创建新节点完成插入操作。

public void insert(Key key, Value value){
  //key不可以为null
  if(null == key){
    throw new IllegalArgumentException("argument key of insert() can't be null");
  }
  //插入操作可能造成根节点变化
  root = insert(root, key, value);
  //保证根节点为BLACK
  root.color = BLACK;
}

private Node insert(Node node, Key key, Value value){
  //遇到null节点创建新节点
  if(null == node){
    node = new Node(key, value, RED, 1);
    return node;
  }
  //否则进行比较
  int cmp = key.compareTo(node.key);
  if(cmp == 0){  //相等更新value即可
    node.value = value;
  }else if(cmp > 0){  //key大于node.key，右子树继续插入操作
    node = insert(node.right, key, value);
  }else{  //key小于node.key，左子树继续插入操作
    node = insert(node.left, key, value);
  }
  //完成插入后，红黑树平衡可能被破坏，需要重新调整平衡
  insertBalance(node);
}

public void insertBalance(Node node){
  //当前节点左节点为黑节点，右节点为红节点——左旋转
  if(!isRed(node.left) && 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;
}

插入过程相对比较简单，注意的是插入新结点后进行红黑树平衡调整的几个条件不是if...else if的关系，而是每部操作之后都需要进行一次判断，毕竟旋转过程中任何情况都可能发生。
每部插入操作后对当前节点进行调整，逐层向上递归，每层都调整平衡即可保证根节点处左右子树的平衡和红黑节点规范。

删除操作

红黑树删除操作相对复杂，对于删除的节点，如果节点是红色节点直接删除不会影响树的平衡性，如果是黑色节点，删除后会造成当前路径上黑色节点数少1，违反了红黑树特性③，因此在删除过程中需要对树的结构进行调整，删除后依旧需要对树的结构进行调整。
方便理解，由删除最小键值、删除最大键值和普通删除操作展看。

1.删除最小键值

如果最小键为红色节点，直接删除即可，不影响红黑树平衡。所以在递归删除的过程中，需要保证最小节点为红色节点，那么在递归删除的过程中，需要保证当前节点或者其左节点为红色。
原因：

①如果当前节点是红色且是最小键，直接删除即可
②当前节点是3节点中的黑色节点，继续递归，下一个节点定是红色节点，只需要判断红色节点是否是最小键即可

保证当前节点或者其左节点是红色节点的实现：从当前节点的父节点入手，如果不能保证左节点是3节点或4节点（即不是2节点）时，就需要从当前节点右子树中借一个节点，通过旋转和变色实现。
①借一个节点使得当前节点为红节点，对应2-3树中的4节点

当前节点变为红节点

！！！注意这里的h节点指的是当前节点的父节点

②借一个节点使得当前节点的左节点为红色节点，对应2-3树中的3节点

当前节点的左节点变为红色

！！！注意这里的h节点指的是当前节点的父节点

public void deleteMin(){
  //空树无法删除
  if(null == root){
    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){
  //当前节点的左节点为null，即为最小节点
  if(null == node.left){
    return null;
  }
  //保证当前节点或其左节点为红色，注意是从父节点入手
  if(!isRed(node.left) && !isRed(node.left.left)){
    //制造红色节点
    node = moveRedLeft(node);
  }
  //递归删除最小键节点
  node = deleteMin(node.left);
  //调整平衡
  return deleteBalance(node);
}

private Node moveRedLeft(Node node){
  //先变色
  flipColors(node);
  //判断节点右节点的左节点是否红色，若是，按第二种方式操作
  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()函数即上面两张图片对应的转换操作，当当前节点的右节点的左节点颜色为红色时按照第二种方式进行转换，将当前节点的左节点的左节点变成红色。否则当前节点左节点为红色，左节点的左节点为黑色。（看代码更好理解）

2.删除最大键值节点

最大键删除和最小键正好相反，删除最大键的过程就是保证当前节点或当前节点的右节点为红色节点，保证删除后不会破坏红黑树平衡。将当前节点或其右节点变为红色的过程也需要从其父节点入手。
①生成一个4节点

当前节点变成红色

！！！注意这里的h节点指的是当前节点的父节点
②借一个节点使得当前节点的右节点为红色节点，对应2-3树中的3节点

当前节点的右节点变为红色

！！！注意这里的h节点指的是当前节点的父节点

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(isRed(node.left)){
    node = rorateRight(node);
  }
  //节点无右节点，即为最大键，删除
  if(null == node.right){
    return null;
  }
  //保证node或node.right为红节点，注意也是从父节点入手
  //因为3节点是用红节点来模拟的，红节点不可能是右孩子，所以不可能是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);
  //相当于完成图2，将右节点的右节点变红，创造3节点操作
  if(isRed(node.left.left)){
    node = rorateRight(node);
    flipColors(node);
  }
  return node;
}

3.删除操作

删除操作结合了1、2中所讲的两种制造红色节点的操作，直接看代码配合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 ;
  }
  //根节点左右节点都是黑色，根节点变红
  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){
  //当前节点的键大于待删除的键，需要在当前节点左子树中递归删除
  //当前节点的左右节点都是黑色节点，通过moveRedLeft创造红色左节点
  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);
    }
    //如果待删除key与当前节点key相等，切当前节点右节点为空——可以直接删除
    if(key.compareTo(node.key) == 0 && node.right == null){
      return null;
    }
    //当前节点key小于待删除的key，需要在其右子树中进行删除
    //当前节点的左右节点都是黑色节点，通过moveRedRight创造红色右节点
    if(!isRed(node.right) && !isRed(node.right.left)){
      node = moveRedRight(node);
    }
    //旋转后的当前节点key若等于待删除key
    //替换当前节点为其右子树的最小节点，之后删除其右子树的最小节点即可
    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);
  }

！！！注意，这里不能再函数的开头使用一个int值记录当前节点key和待删除key的比较结果，因为在后续过程中，moveRedLeft和moveRedRight操作可能改变当前节点所指向的节点，因此，每次变换完都需要重新进行比较。

给出完整的红黑树操作

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;
  }

}

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,271评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,275评论 2赞 380
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,151评论 0赞 336
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,550评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,553评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,559评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,924评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,580评论 0赞 257
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,826评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,578评论 2赞 320
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,661评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,363评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,940评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,926评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,156评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,872评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,391评论 2赞 342

学习红黑树的思考

红黑树的特性

实现

颜色表示

节点数据结构

红黑树的平衡实现

1.变色

2.左旋转

3.右旋转

补充

红黑树插入操作

删除操作

1.删除最小键值

！！！注意这里的h节点指的是当前节点的父节点

！！！注意这里的h节点指的是当前节点的父节点

2.删除最大键值节点

3.删除操作

！！！注意，这里不能再函数的开头使用一个int值记录当前节点key和待删除key的比较结果，因为在后续过程中，moveRedLeft和moveRedRight操作可能改变当前节点所指向的节点，因此，每次变换完都需要重新进行比较。

给出完整的红黑树操作

推荐阅读更多精彩内容