红黑二叉查找树

红黑树的算法如雷贯耳,但鉴于一些原因从来没有去研究实现过。 红黑树的实质其实是一个2-3树。他相对于 BST 来说更加的扁平。拥有着更好的查找效率。 对于基于红黑树的符号表的操作的运行时间几乎都是对数级别。

2-3树

二叉树每个节点至多只能有2个节点,但是在2-3树中我们可以通过把两个结点绑定在一起成一个结点,然后让他拥有3个结点。如图


image.png

由于查找较为简单在这里我们不在赘述了。我们着重讲一讲2-3树的插入操作和删除操作。

插入操作

对于插入操作,我们可以分为以下几种情况:

  • 向2- 结点插入新键
  • 向一棵只含有3-结点的树插入新键
  • 向一个父结点为2-结点的3结点插入新键
  • 向一个父结点为3-结点的3结点插入新键

向2- 结点插入新键

对于这种情况,我们直接插入即可,将这个2-结点 变为3-结点。
image.png

向一棵只含有3-结点的树插入新键

这棵树已经有了2个键,所以我们可以发现,他没有结点可以给新键来插入。我们可以临时把他插入,使得这个结点变为一个4-结点。对于2-3树,不应该存在4-结点。所以我们为了能使得树保持平衡需要进行变化,即把这个4-结点,变为3个2-结点。
image.png

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

当需要插入的位置为3结点,同时他的父节点是一个二结点时,我们首先也行上一个情况中一样,将新键插入,使得3-结点成为一个临时的4-结点,再分解他,但是这一次,我们不再为中间的键去创造一个新的结点,而是把它插入到父节点中,使得她和父节点重新组成一个新的3-结点。

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

对于这个情况,我们也是先构造一个4-结点,然后将之分解,中键和父节点组成新的父节点,4-节点。分解,中键提出,然后再按照情况 判断,根据情况处理。
image.png image.png

红黑二叉查找树

对于红黑树来说他最难的操作,就在于删除和插入两部分,查找相对来说要简单,类似于BST的查找,在这里不赘述。

红黑树具有的性质:

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

插入

对于插入操作,我们同2-3树一样,要分情况来讨论。

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

如果新键要小于老键,那么我只需要新增一个红的结点即可,把这个结点变为一个3-结点。 如果新键大于老键,我们也增加一个红结点,然后通过旋转将红色的左链接修复。最后我们需要把根节点变为黑色 。

向树底部的2-结点插入新键

类似于上面一种情况。 总是用红链接连接父节点和新的结点。然后通过旋转来进行调整。

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

  1. 当新键大于原树种的两个键的时候,我们只需要将其连到右链接上即可。这时我们需要把链接都由红色变为黑色,黑色变为红色,这一步操作对应的是2-3树中「向一棵只含有3-结点的树插入新键」这种类似的情况,即把临时的4-结点,拆掉,父节点提出,如果是根节点为黑,不是则变为红和上面的部分组成3-结点或者4-结点,再次过程中需要进行调整,调整按照情况进行区分。
  2. 如果新键小于原树中的两个键,这样形成了两个连续的红链接,我们需要对上层的红链接进行右旋转,这样我们又回到了情况一。
  3. 新键在两个键之间,这样也会有两个红链接产生,一个红左接一个红右,我们需要对红右进行左旋,得到第二种情况。

实现

private void flipColor(Node h){}
private Node rotateRight(Node h) {}
private Node rotateLeft(Node h){}


public void put(Key key, Value val) {
   root: put(root, key, val);
   root.color: BLACK;
}

public 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);
   } else if (cmp > 0) {
       h.right: put(h.right, key, val);
   } else {
       h.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)) {
       flipColor(h);
   }

   h.N: size(h.left) + size(h.right) + 1;
   return h;
}

删除

删除操作比起插入操作更加的复杂。 我们需要在为了删除结点需要构造一个临时的四结点,这需要我们在查找的过程中沿着查找路径向下进行变换。同事我们也需要为了分解遗留的4-结点沿着查找的路径向上进行变换,来保持树的结构。

删除最小键

我们先从最小键的删除来开始介绍。 我们可以很容易的看到,从树底部的3-结点删除一个键是很简单的,但是对于2-结点来说并不是如此,因为从2-结点删除会留下一个空键,这样破坏了平衡性,因此我们要对此进行处理,沿着左链接进行向下的变化,来确保当前的结点不是2-结点。

我们分情况来进行讨论。首先我们看根节点

对于根节点有两种情况:

  1. 一种是根结点是2-结点且他的两个子结点也是2-结点,对于这种情况的处理是简单的,我们只需要直接将其转变为一个4-结点即可。
  2. 在另一种情况里,我们需要确保我们的根结点的左子结点不是一个2-结点,如果左子结点是2-结点,我们在必要的时候可以向他右侧结点借一个键。

对于上述的第二种情况,我们还要继续去分情况讨论。

  • 当前结点的左子结点不是2-结点,完成。
  • 当前结点的左子结点是2-结点,而它(子结点)的兄弟结点不是,那么我们将兄弟结点的一个键移动,到根结点,根节点的最小键移动到左子结点。
  • 如果当前结点的子节点都是2-结点,且其本身不是2-结点,那么我们将左子结点,父节点中的最小键,左子结点最近的兄弟结点合并为一个4-结点,使得父结点从一个3-结点或4-结点变为一个2-结点或3-结点。

实现

private Node moveRedLeft(Node h) {
   //当左右两个结点都是2-结点的时候
   //两种情况,根据 h 有两种情况
   //但是在这里只有一种,因为所有的 h 都肯定是红色的
   //将 h和两个子节点组为一个4-结点
   //h 变为黑色的结点
   flipColor(h);

   //h的右节点是3-结点的情况
   //我们要将右子节点的最小键移动到  h所在的结点
   //根据前面的左右旋转代码 可知 我们无法将两个黑色的结点交换
   //所以我们需要先改变 h 及其子节点的颜色来帮助我们移动右子节点的最小键
   if(isRed(h.right.left)){
       h.right: rotateRight(h.right);
       h: rotateLeft(h);
       //当我们将之移动完成后我们需要恢复他的颜色
       flipColor(h);
   }

   return h;
}

public void deleteMin() {


   //如果 root 的 左子节点是2-结点
   //root to  RED
   //这样有便于下面处理的时候简化问题
   if (!isRed(root.left) && !isRed(root.right)) {
       root.color: RED;
   }

   root: deleteMin(root);
   if (!isEmpty()) {
       root.color: BLACK;
   }

}

private Node deleteMin(Node h) {
   if (h.left == null) {
       return null;
   }

   //判断左子节点说不是3-结点 进入从右结点借的情况
   if (!isRed(h.left) && !isRed(h.left.left)) {
       h: moveRedLeft(h);
   }
   return balance(h);
}

删除最大值

删除最大键的操作和删除最小的相仿。也是分情况考虑。 当左右子结点都是2-结点的时候,将之和父节点一起变为4-结点。 当右结点是2-结点,左结点不是的时候,让右节点从左结点接一个最大的键,也就是最亲的兄弟结点。

实现

private Node moveRedRight(Node h) {

   // 这里是两种情况的合并,一种是左右两个结点都是2-结点,变为4-结点;
   // 另一种是左结点不是从左结点借结点,但是对于这种情况我们也需要这个变化,来帮助我们旋转变化。
   flipColor(h);

   // 当左结点为3-结点
   // 旋转变换
   if (isRed(h.left.left)) {
       h: rotateRight(h);
       flipColor(h);
   }

   return h;
}

public void deleteMax() {
   if (!isRed(root.left) && !isRed(root.right)) {
       root.color: RED;
   }

   root: deleteMax(root);

   if (!isEmpty()) {
       root.color: BLACK;
   }
}

private Node deleteMax(Node h) {


   // 当当前结点是3-结点时候,右旋,来方便删除
   if (isRed(h.left)) {
       h: rotateRight(h);
   }

   // 当当前结点的右节点为 null 说明没有结点比他更大
   // 又因为,我们通过旋转变化使得当前结点的红链接向右,所以直接删除
   if (h.right == null) {
       return null;
   }

   //判断当前结点的➡右结点是不是3-结点,如果不是从左结点借
   if (!isRed(h.right) && !isRed(h.right.left)) {
       h: moveRedRight(h);
   }

   h.right: deleteMax(h.right);

   return balance(h);
}

删除操作

有了删除最小和最大的基础,我们可以很容易的得到删除的思路,就是要在查找路径上把结点变换为3/4-结点,以及在完场删除后再恢复。不过有一点区别,删除发生时的借结点,不是问兄弟结点,而是当前结点的分支下的最大或者最小借。

实现

public void delete(Key key) {

   //将根节点变为 red
   if (!isRed(root.left) && !isRed(root.right)) {
       root.color: RED;
   }

   root: delete(root, key);

   //完成删除恢复根节点为 black,因为红黑树的根节点一定为 black
   if(!isEmpty()) root.color: BLACK;
}

private Node delete(Node h, Key key) {

   //当要删除的键的值小于当前的
   // 进入左边的链接
   if (key.compareTo(h.key) < 0) {
   //判断左边的子节点是不是2-结点,如果是则要借,这里同删除最小
       if (!isRed(h.left) && !isRed(h.left.left)) {
           h: moveRedLeft(h);
       }
       h.left: delete(h.left, key);
   } else {
   // 相等和大于
   // 当前结点是3-结点。旋转来方便删除
       if (isRed(h.left)) {
           h: rotateRight(h);
       }
       //当相等时 且右没有 直接删除
       if (key.compareTo(h.key) == 0 && h.right == null) {
           return null;
       }
       //右节点不是3-结点 借结点
       if (!isRed(h.right) && !isRed(h.right.left)) {
           h: moveRedRight(h);
       }
       // 如果key 相等找出当前分支的右结点的最小值,记录,deletemin,然后经需要删除的结点
       // 替换为查找到的那个最小结点
       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);
}