算法3.4 红黑树

实现

红黑查找树是2-3树的具体实现

1. 替换3-结点

• 红黑树的基本思想:用标准的二叉查找树(全是2-结点)和一些额外信息(替换3-结点)来表示2-3查找树
• 结点类型:(结点的颜色指的是指向该结点的链接颜色)
  • 红链接:将两个2-结点连成3-结点
  • 黑链接:2-3树中的普通链接

private class Node{
        Key key;
        Value val;
        Node left, right;
        int N;
        //结点颜色:指向该结点链接的颜色
        boolean color;
        Node(Key key, Value val, int N, boolean color){
            this.key = key;
            this.val = val;
            this.N = N;
            this.color = color;
        }
    }

2. 等价定义

• 红链接均为左链接
• 没有一个结点同时和两条红链接相连(4-结点)
• 该树是黑色平衡,即任意空链接到根结点的路径上黑链接数量相同

3. 一一对应

将红黑树中所有红链接画水平,那所有空链接到根结点的距离都将相同.再将红链接相连的结点合并,即可得到2-3树.红黑树结合了二叉树的高效查找和2-3树的平衡插入

4. 主要操作

4.1 旋转

某些操作下,可能出现红色右链接或两个连续红链接,需要旋转改变红链接指向,旋转操作保证了有序性和完美平衡性

• 左旋:避免产生右红链接
• 右旋:处理左侧两个连续红链接

Node rotateLeft(Node h){
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = h.color;//初始h的颜色不确定
    h.color = RED;//旋转后左链接置红色
    x.N = h.N;
    h.N = 1+size(h.left)+size(h.right);
    return x;
}
Node rotateRight(Node h){
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = RED;
    x.N = h.N;
    h.N = 1+size(h.left)+size(h.right);
    return x;
}

4.2 插入

4.2.1 向2-结点插入新键

当只有一个2-结点时,插入一个新键后立刻旋转

• 新键<老键:增加红色结点,新树等价于3-结点
• 新键>老键:增加红色结点,但产生红右链,root=rotateLeft(root),旋转修正

4.2.2 向双键树(3-结点)插入新键

• 新键>原数中两个键:最简单的情况,直接连接到3-结点右链接.此时树是平衡的,将两个链接的颜色由黑变红,即得到一棵由三个结点组成的,高为2的平衡树,真好对于2-3树
• 新键<原数中两个键:连接到最左边的空链接,形成了连续两条红链接(4-结点),只需把上层红链接右旋转即可回到情况一
• 新键介于二者之间:连接到左结点的右链(红色),有形成两条连续红链接,将右链左旋,回到情况二

4.2.3 颜色转换

在上述向双键树插入新键操作后,子结点都由红变黑,父结点变红,这是局部变换,不会影响整棵树的黑色平衡性

private void flipColors(Node h){
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

4.2.4 根结点总为黑色

红色结点说明结点是3-结点的一部分,但根结点并不满足,则每次插入后根结点都设为黑,且每当根结点由红变黑,树高加1

4.2.5 红链接向上传递

在2-3树中,在一个3-结点下插入新键->临时创建4-结点->分解,传递中间值到父结点->父结点是一个2-结点或为根结点->若为后者,则分解根结点.
对应到红黑树中就是红链接向上传递,插入->旋转->颜色转换->红链接转移至中结点->重复(和新插入结点效果一样)->直到非红右链接/非连续红链接/非根结点

4.2.6 插入算法

• 插入操作只有以下三种:
  • 左子结点黑色,右子结点红色->左旋
  • 左子结点和左子结点的左子结点都为红色->右旋
  • 左右子结点都为红色->颜色转换

• 红黑树平衡性的调整是自下而上的,所以在put()递归插入语句后,再用if判断以上三种情况,并且,三条语句有顺序(根据4.2.2分析)

  public class RedBlackBST<Key extends Comparable<Key>, Value > {
  private Node root;
  private static final boolean RED = true;
  private static final boolean BLACK = false;
  private class Node{}
  private boolean isRed(Node x){
     if (x == null) return false;
     return x.color == RED;
  }
  private Node rotateLeft(Node h){}
  private Node rotateRight(Node h){}
  private void flipColors(Node h){}
  public int size(){ return size(root);}
  private int size(Node h){
     if (h == null) return 0;
     else return h.N;
  }
  public void put(Key key, Value val){
     root = put(root,key,val);
     root.color = BLACK;
  }
  private Node put(Node h, Key key, Value val){
     if (h == null){
         //新建结点都用红链接
         return new Node(key, val, 1, RED);
     }
     int cmp = key.compareTo(h.key);
     if (cmp < 0) h.left = put(h.left, key, val);//小于key,进入左子树
     else if(cmp > 0) h.right = put(h.right, key, val);//大于key,进入右子树
     else h.val = val;//已存在,则更新val
     //处理右侧红链接
     if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
     //处理连续红链接
     if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
     //颜色转换
     if (isRed(h.left) && isRed(h.right)) flipColors(h);
     h.N = size(h.right)+size(h.left)+1;
     return h;
  }
  }

示例

4.3 删除

4.3.1 自顶向下的2-3-4树
2-3-4树中允许存在4-结点,它的插入算法和2-3数的删除算法类似,因此作为引导

• 插入: 沿着路径向下进行变换,始终保持当前结点非4-结点(这样树底才有空间插入新键),沿查找路径向上进行变换是为了将之前创建的4-结点配平
  • 向下变换:
    1. 根结点是4-结点,分解为三个2-结点,树高加一
    2. 父结点为2-结点的4-结点,将中间结点上移构成3-结点,剩下拆分为两个2-结点
    3. 父结点为3-结点的4-结点,将中间结点上移构成4-结点,剩下拆分为两个2-结点
    4. 不会构建出出现父结点和子结点同时为4-结点的情况
    5. 树底部只可能为2-/3-结点,插入扩大一个即可
  • 向上变换:即put()中的递归后rotate()处理
  • 红黑树实现2-3-4插入:
    • 4-结点由三个2-结点表示
    • 向下时分解4-结点,进行颜色转换
    • 向上时旋转配平4-结点
  • 只需要将colorFlip()语句及其if语句放在null测试和比较操作之间,就可以实现上述算法
    • 允许4-结点存在,即允许连续两个左红链接存在,所以语句提前在比较执行put()前,再下次put()时前在调整颜色(分解4-结点)—向下
    • 两个方向rotate()依旧在put()后,则在向上过程中配平4-结点—向上

4.3.2 删除最小键

• 考虑:在树底部删除3-结点删除最小键容易实现,但若从2-结点删除一个结点,会留下一个空链接,破坏平衡性
• 因此:删除最小键时,沿着左链接向下变换,确保当前结点非2-结点(可能是3-结点或者临时4-结点)
  1. 根结点的两种可能:
     • 根结点是2-结点且两个子结点也是2-结点:将三个结点合并为一个4-结点
     • 否则需要保证根结点的左子结点非2-结点,必要时从其右兄弟结点取一个键
  2. 沿着左链接向下时:
     • if(!isRed(h.left) && !isRed(h.left.left))
     • 若当前结点左子结点非2-结点(h.left或h.left.left中一个为红色,则h.left就在一个3-结点中),完成,继续左下深入
     • 若当前结点左子结点是2-结点而亲兄弟非2-结点,将右子结点的兄弟结点中一个键移动到左子结点中
     • 若当前结点左子结点和兄弟结点都是2-结点,将左子结点,父结点中的最小键,左子结点最近兄弟结点合并为一个4-结点,则父结点从3-变为2-或4-变为3-
  3. 最终:得到一个含有最小键的3-结点或者4-结点,将其删除,在回头向上分解4-结点(递归)

//配平4-结点函数,只有第一句话不同,其余和put最后五句一致
private Node balance(Node h){
    if (isRed(h.right)) h = rotateLeft(h);
    if(!isRed(h.left) && isRed(h.right)) rotateLeft(h);
    if(isRed(h.left) && isRed(h.left.left)) rotateRight(h);
    if(isRed(h.left) && isRed(h.right)) flipColors(h);
    h.N = size(h.right) + size(h.left)+1;
    return h;
}
//删除时的颜色转换与插入时刚好相反
private void delFlipColors(Node h){
    h.color = BLACK;
    h.left.color = RED;
    h.right.color = RED;
}
public void deleteMin(){
    if(!isRed(root.left) && !isRed(root.right))//根结点三个2-结点
        root.color = RED;//为后续颜色变换准备
    deleteMin(root.left);
    if(!isEmpty()) root.color = BLACK;//根结点始终为黑色
}
private Node deleteMin(Node h){
    if (h.left == null) return null;//找到左链最底,返回null
    if(!isRed(h.left) && !isRed(h.left.left))//h.left是2-结点
        h = moveRedLeft(h);//借助兄弟结点
    h.left = deleteMin(h.left);
    return balance(h);
}
private Node moveRedLeft(Node h){
    delFlipColors(h);//Min:默认形成4-结点
    if (isRed(h.right.left)){//Min:当右兄弟非2-结点,借出一个键给左兄弟
        h.right = rotateRight(h.right);
        h = rotateLeft(h);
    }
    return h;
}

示例

4.3.3 删除最大键

• 删除最大键的思想和删除最小键一样
  1. 对根结点的处理:同上
  2. 沿着右链接向下时:
     • 若当前结点的左子结点非2-结点,则左旋转左子结点,成为父结点,新的右子结点一定非2-结点,为后续删除创造条件
     • if(!isRed(h.left) && !isRed(h.left.left))
     • 若当前结点右子结点非2-结点(h.right或h.right.left中一个为红色,则h.left就在一个3-结点中),完成,继续右下深入
     • 若当前结点右子结点是2-结点而左兄弟非2-结点,将右子结点,父结点中的最大键,最近左兄弟结点合并为一个4-结点
     • 若当前结点右子结点和兄弟结点都是2-结点,则将左子结点旋转,即移动一个键到右子结点
  3. 最终:得到一个含有最大键的3-结点或者4-结点,将其删除,在回头向上分解4-结点(递归)

//删除最大键
public void deleteMax(){
    if(!isRed(root.left) && !isRed(root.right))//根结点三个2-结点
        root.color = RED;//为后续颜色变换准备
    root = deleteMax(root);
    if (!isEmpty()) root.color = BLACK;
}
private Node deleteMax(Node h){
    if (isRed(h.left)) h = rotateRight(h);//左侧非2-结点右旋转
    if(h.right == null) return null;//找到右链底部,返回null
    if (!isRed(h.right) && !isRed(h.right.left))
        h = moveRedRight(h);//从左链借来键
    h.right = deleteMax(h.right);
    return balance(h);
}
private Node moveRedRight(Node h){
    //delMin与delMax这两步含义不同
    delFlipColors(h);//Max:默认右子结点变为非2-结点
    if (!isRed(h.left.left))//Max:当左兄弟是2-结点,则形成4-结点
        h = rotateRight(h);
    return h;
}

示例

4.3.4 删除操作

• 删除和delMin/delMax都要保证当前结点非2-结点,若最终找到结点在底部(左链接/右链接),则直接删除,否则就用右子树最小结点键值与其他交换,再删除右子树最小键

public void delete(Key key){
    if(!isRed(root.left) && !isRed(root.right))//根结点三个2-结点
        root.color = RED;//为后续颜色变换准备
    root = delete(root, key);
    if (!isEmpty()) root.color = BLACK;
}
private Node delete(Node h, Key key){
    if(key.compareTo(h.key) < 0){//cmp < 0,类比delMin
        if(!isRed(h.left) && !isRed(h.left.left))
            h = moveRedLeft(h);
        h.left = delete(h.left, key);
    }
    else{//cmp >= 0,类比delMax
        if(isRed(h.left)) h = rotateRight(h);
        if(key.compareTo(h.key) == 0 && (h.right == null)) return null;//找到结点,且无右子树,直接删除
        if(!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h);
        if(key.compareTo(h.key) == 0){//找到结点,且有后续结点,则用右子树最小结点键值替换父结点,再删去右子树最小结点
            h.val = get(h.right, min(h.right).key);
            h.key = min(h.right).key;
            h.right = deleteMin(h.right);
        }
        else h.right = delete(h.right, key);
    }
    return balance(h);
}

示例

5. 红黑树性质

5.1 性能分析

1. 大小为N的红黑树高度不超过2lgN
   最坏情况是对应2-3树最左边路径全是3-结点而其余都为2-结点
2. 大小为N的红黑树,根结点到任意结点的平均路径长度为~1.00lgN
3. 红黑树中,以下操作在最坏情况下是对数级别的:
   get(),put(),min(),max(),floor(),ceiling(),rank(),select(),deleteMin(),deleteMax(),delete(),range()

红黑树是第一个可以保证**对数级别插入和查找的符号表实现**

5.2 各种符号表实现性能总结