平衡树

之前我们学习过二叉查找树,发现它的查询效率比单纯的链表和数组的查询效率要高很多,大部分情况下,确实是这样的,但不幸的是,在最坏情况下,二叉查找树的性能还是很糟糕的

例如我们依次往二叉树中插入$9,8,7,6,5,4,3,2,1$这$9$个数据,那么最终构造出来的树是长成下面这个样子

我们可以发现,如果我们要查找$1$这个元素,查找的效率依旧会很低,效率低的原因就是在于这个树并不平衡,全部是向左分支,如果我们有一种方法,能够不受插入数据的影响,让生成的树都像完全二叉树那样,那么即使是在最坏情况下,查找的效率依旧会很好

2-3查找树

为了保证查找树的平衡性,我们需要一些灵活性,因此在这里我们允许树中的一个节点保存多个键,确切地说,我们将一棵标准的二叉查找树中的节点称为2-节点(含有一个键和两条链),而现在我们引入3-节点,它含有两个键和三条链,2-节点和3-节点中的每条链都对应着其中保存的键所分割产生的一个区间

2-3查找树的定义

一棵2-3查找树要么为空,要么满足下面两个要求

• 2-节点:含有一个键(及其对应的值)和两条链,左连接指向的2-3树中的键都小于该节点,右连接指向的2-3树中的键都大于该节点
• 3-节点:含有两个键(及其对应的值)和三条链,左连接指向的2-3树中的键都小于该节点,中连接指向的2-3树中的键都位于该节点的两个键之间,右连接指向的2-3树中的键都大于该节点
  

查找

将二叉查找树的查找算法一般化我们就能够直接得到2-3树的查找算法,要判断一个键是否在树中,我们先将它和根节点中的键比较,如果它和其中任意一个相等,查找命中,否则我们就根据比较的结果找到相应区间的连接,并在其指向的子树中递归调用继续查找,如果这是个空链接,返回未查找到

插入

向2-节点中插入新键

往2-3树中插入元素和往二叉查找树中插入元素一样,首先要进行查找,然后将节点挂到未找到的节点上,2-3树之所以能够保证在最差的情况下的效率的原因在于插入之后仍然能够保持平衡状态,如果查找后未找到的节点是一个2-节点,那么很容易,我们只需要将新的元素放到这个2-节点里面使其变成一个3-节点即可,但是如果查找的节点结束于一个3-节点,那么可能有点麻烦

向一棵只含有一个3-节点的树中插入新键

假设2-3树值包含一个3-节点,这个节点有两个键,没有空间来插入第三个键了,最自然的方式是我们假设这个节点能存放三个元素,暂时使其变成一个4-节点,同时它包含四条链接,然后,我们将这个4-节点的中间元素提升,左边的键作为其左子节点,右边的键作为其右子节点,插入完成,变成平衡2-3查找树,树的高度从0变为1

向一个父节点为2-节点的3-节点中插入新键

和上面的情况一样,我们也可以将新的元素插入到3-节点中,使其变成一个临时的4-节点,然后将该节点的中间元素提升到父节点即2-节点中,使其父节点成为一个3-节点,然后将左右节点分别挂在这个3-节点的恰当位置

向一个父节点为3-节点的3-节点中插入新键

当我们插入的节点是3-节点的时候,我们将该节点拆分,中间元素提升至父节点,但是此时父节点也是一个3-节点,插入之后,父节点也变成了4-节点,然后需要继续将中间元素提升至其父节点,直到遇到一个父节点是2-节点,然后将其变为3-节点,不需要继续进行拆分

分解根节点

当插入节点到根节点的路径上全部都是3-节点时,最终我们的根节点会变成一个临时的4-节点,此时,就需要将根节点拆分为两个2-节点,树的高度加1

2-3树的性质

通过对2-3树插入操作的分析,我们发现在插入的时候,2-3树需要做一些局部的变换来保持2-3树的平衡

一棵完全平衡的2-3树具有以下性质

1. 任意空链接到根节点的路径长度都是相等的
2. 4-节点变换为3-节点时,树的高度是不会发生变化,只有当根节点是临时的4-节点,分解根节点时,树的高度才+1
3. 2-3树与普通二叉查找树最大的区别在于,普通的二叉查找树是自顶向下生长,而2-3树是自底向上生长

2-3树的实现

直接实现2-3树比较复杂,因为:

• 需要处理不同的节点类型,非常繁琐
• 需要多次比较操作来将节点下移
• 需要上移来拆分4-节点
• 拆分4-节点的情况有很多种

2-3查找树实现起来比较复杂,在某些情况插入后的平衡操作可能会使得效率降低,但是2-3查找树作为一种比较重要的概念和思路对于我们后面要学习的红黑树,B树和B+树非常重要

红黑树

我们之前了解了2-3树,可以看到2-3树能保证在插入元素之后,树依然保持平衡状态,它的最坏情况下所有子节点都是2-节点,树的高度为$lgN$,相比于我们普通的二叉查找树,最坏情况下树的高度为N,确实保证了最坏情况下的时间复杂度,但是2-3树实现起来过于复杂,所以我们介绍一种2-3树思想的简单实现:红黑树

红黑树主要是对2-3树进行编码,红黑树背后的基本思想是用标准的二叉查找树(完全由2-节点构成)和一些额外的信息(替换3-节点)来表示2-3树,我们将树种的链接分为两种类型:

红链接:将两个2-节点连接起来构成一个3-节点

黑链接:则是2-3树中的普通链接

确切地说,我们将3-节点表示为由一条左斜的红色链接(两个2-节点其中之一是另一个的左子节点)相连的两个2-节点,这种表示法的一个优点是,我们无需修改就可以直接使用标准的二叉查找树的get方法

红黑树的定义

红黑树是含有红黑链接并满足下列条件的二叉查找树:

1. 红链接均为左链接
2. 没有任何一个节点同时和两条红链接相连
3. 该树是完美黑色平衡的,即任意空链接到根节点的路径上的黑链接数量相同

下面是红黑树与2-3树的对应关系

红黑树节点API

因为每个节点都只会有一条指向自己的链接(从它的父节点指向它),我们可以在之前的Node节点中添加一个布尔类型的变量color来表示链接的颜色,如果指向它的链接是红色的,那么该变量的值为true,如果链接是黑色的,那么该变量的值为false

API设计

平衡化

在对红黑树进行一些增删改查的操作后,很有可能会出现红色的右链接或者两条连续的红色链接,而这些都不满足红黑树的定义,所以我们需要对这些情况通过旋转进行修复,让红黑树保持平衡

左旋

当某个节点的左子节点为黑色,右子节点为红色,此时需要左旋

前提:当前节点为h,它的右子节点为x

左旋过程:

1. 让x的左子节点变为h的右子节点:h.right=x.left
2. 让h成为x的左子节点:x.left=h
3. 让h的color属性变为x的color属性:x.color=h.color
4. 让h的color属性变为red:h.color=true
   

右旋

当某个节点的左子节点是红色,且左子节点的左子节点也是红色,需要右旋

前提:当前节点为h,它的左子节点为x

右旋过程:

1. 让x的右子节点成为h的左子节点:h.left=x.right
2. 让h成为x的右子节点:x.right=h
3. 让x的color变为h的color属性:x.color=h.color
4. 让h的color变为red
   

虽然节点经过了右旋,但仍然有一些小问题,需要通过颜色反转来修改

向单个2-节点中插入新键

一棵只含有一个键的红黑树只含有一个2-节点,插入另一个键后,我们马上就需要将他们旋转

• 如果新键小于当前节点的键,我们只需要新增一个红色节点即可,新的红黑树和单个3-节点完全等价
  
• 如果新键大于当前节点的键,那么新增的红色节点将会产生一条红色的右链接,此时我们需要通过左旋,把红色右链接变成左链接,插入操作才算完成,形成的新的红黑树依然和3-节点等价,其中含有两个键,一条红色链接
  

向底部的2-节点插入新键

用和二叉查找树相同的方式向一棵红黑树中插入一个新键,会在树的底部新增一个节点(可以保证有序性),唯一区别的地方是我们会用红链接将新节点和它的父节点相连,如果它的父节点是一个2-节点,那么刚才讨论的两种方式仍然适用

颜色反转

当一个节点的左子节点和右子节点的color都为red时,也就是出现了临时的4-节点,此时只需要把左子节点和右子节点的颜色变为black,同时让当前节点的颜色变为red即可

向一棵双键树(即一个3-节点)中插入新键

这种情况可以分为三种子情况:

1. 新键大于原树中的两个键
   
2. 新键小于原树中的两个键
   
3. 新键介于原树中两个键之间
   

根节点的颜色总是黑色

之前我们介绍节点API的时候,在节点Node对象color属性表示的父节点指向当前节点的链接的颜色,由于根节点不存在父节点,所以每次插入操作之后,我们都需要把根节点的颜色设置为黑色

向树底部的3-节点插入新键

假设在树的底部的一个3-节点下加入一个新的节点,前面我们所讲的3种情况都会出现,指向新节点的链接可能是3-节点的右链接(此时我们只需要转换颜色即可),或是左链接(此时我们需要进行右旋转然后再转换),或是中链接(此时需要先左旋转然后再右旋转,最后转换颜色),颜色转换会使中间节点的颜色变红,相当于将它送入了父节点,这意味着父节点中继续插入一个新键,我们只需要使用相同的方法解决即可,直到遇到一个2-节点或者根节点为止

红黑树的API设计

代码实现

RedBlackTree

public class RedBlackTree<Key extends Comparable<Key>, Value> {

  /**
   * 根节点
   */
  private Node root;
  /**
   * 记录树中元素的个数
   */
  private int N;
  /**
   * 红色链接
   */
  private static final boolean Red = true;
  /**
   * 黑色链接
   */
  private static final boolean Black = false;

  /**
   * 节点类
   */
  private class Node {

    //存储键
    public Key key;
    //存储值
    public Value value;
    //记录左子节点
    public Node left;
    //记录右子节点
    public Node right;
    //由其父节点指向它的链接的颜色
    public boolean color;

    public Node(Key key, Value value, Node left, Node right, boolean color) {
      this.key = key;
      this.value = value;
      this.left = left;
      this.right = right;
      this.color = color;
    }
  }

  /**
   * 判断当前节点的父指向链接是否为红色
   */
  private boolean isRed(Node x) {
    //如果x是空链接,则应该是黑色
    if (x == null) {
      return false;
    }
    return x.color == Red;
  }

  /**
   * 左旋调整
   */
  private Node rotateLeft(Node h) {
    //获取h的右子节点x
    Node x = h.right;
    //让x的左子节点变为h的右子节点
    h.right = x.left;
    //让h变为x的左子节点
    x.left = h;
    //让x的color属性等于h节点的color属性
    x.color = h.color;
    //让h节点的color属性变为red
    h.color = Red;
    return x;
  }

  /**
   * 右旋调整
   */
  private Node rotateRight(Node h) {
    //获取h节点的左子节点x
    Node x = h.left;
    //让x的右子节点称为h节点的左子节点
    h.left = x.right;
    //让h节点成为x的右子节点
    x.right = h;
    //让x节点的color属性变为h节点的color属性
    h.color = x.color;
    //让h节点的color属性变为red
    h.color = Red;
    return x;
  }

  /**
   * 颜色反转,相当于完成拆分4-节点
   */
  private void flipColors(Node h) {
    //让当前节点color变为red
    h.color = Red;
    //左子节点和右子节点变为black
    h.left.color = Black;
    h.right.color = Black;
  }

  /**
   * 在整个树上完成插入操作
   */
  public void put(Key key, Value value) {
    root = put(root, key, value);
    //根节点的颜色永远是黑色的
    root.color = Black;
  }

  /**
   * 在指定树中,完成插入操作,并返回添加元素后的新的树
   */
  private Node put(Node h, Key key, Value value) {
    //判断h是否为空,如果为空,直接返回一个red的节点即可
    if (h == null) {
      //数量+1
      N++;
      return new Node(key, value, null, null, Red);
    }
    //比较h节点的键和key的大小
    int cmp = key.compareTo(h.key);
    //如果比key小
    if (cmp < 0) {
      //继续往左
      h.left = put(h.left, key, value);
    }//如果大于key
    else if (cmp > 0) {
      //继续往右
      h.right = put(h.right, key, value);
    }//如果在中间范围
    else {
      //进行值的替换
      h.value = value;
    }
    //进行左旋判断:当前节点的左子节点为black,右子节点为red
    if (!isRed(h.left) && isRed(h.right)) {
      h = rotateLeft(h);
    }
    //进行右旋判断:当前节点左子节点为red,左子节点的左子节点为red
    if (isRed(h.left) && isRed(h.left.left)) {
      h = rotateRight(h);
    }
    //进行颜色反转判断,当前节点的左子节点为red,右子节点为red
    if (isRed(h.left) && isRed(h.right)) {
      flipColors(h);
    }
    return h;
  }

  /**
   * 根据key,从树中找出对应的值
   */
  public Value get(Key key) {
    return get(root, key);
  }

  /**
   * 从指定的树x中,找出key对应的值
   */
  private Value get(Node x, Key key) {
    if (x == null) {
      return null;
    }
    //比较x节点的键和key的大小
    int cmp = key.compareTo(x.key);
    if (cmp < 0) {
      return get(x.left, key);
    } else if (cmp > 0) {
      return get(x.right, key);
    } else {
      return x.value;
    }
  }

  /**
   * 获取树中元素的个数
   */
  public int size() {
    return N;
  }
}

RedBlackTreeTest

public static void main(String[] args) {
    //创建红黑树
    RedBlackTree<String, String> redBlackTree = new RedBlackTree<>();
    //往树中插入元素
    redBlackTree.put("1", "java");
    redBlackTree.put("2", "C");
    redBlackTree.put("3", "php");
    //从树中获取元素
    String r1 = redBlackTree.get("1");
    System.out.println(r1);
    String r2 = redBlackTree.get("2");
    System.out.println(r2);
    String r3 = redBlackTree.get("3");
    System.out.println(r3);
  }