文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

红黑树的实现原理是什么

2024-04-02 19:55

关注

本篇文章给大家分享的是有关红黑树的实现原理是什么,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。

一、摘要

平衡二叉查找树是一个高度平衡的二叉树,也就是说树的高度差不能大于1,在删除的时候,可能需要多次调整,也就是左旋转、右旋转操作,在树的深度很大的情况下,删除效率会非常低,如何提高这种效率?

红黑树由此诞生了,了解过红黑树的朋友们一定知道,红黑树是一个基本平衡的二叉树,英文全称:red-black-tree,简称:RBT,特性如下:

关于它的特性,需要注意的是:

红黑树示例图,如下:

红黑树的实现原理是什么

红黑树,与二叉树,在查询、插入、删除方面,都是一样的,最大的不同点是,插入、删除需要重新调整树的形态,以保持红黑树的特性!

二、算法思路

在上篇平衡二叉树的文章中,我们了解到为了保证树的高度差不超过1,我们通过树高超过1这么一个判断条件,通过左旋转、右旋转来调整,从而保证树的高度平衡!

对于红黑树,其实也是一样的,对于插入、删除操作,主要也是通过左旋转、右旋转来进行调整,相比平衡二叉树,红黑树因为节点有颜色标签,多了一个颜色转变操作!

同理,我们只需要分析出哪些场景下需要进行调整,即可总结出算法,从而写出实践代码!

废话也不多说来,下面我们一起来分析一下红黑树,在插入、删除操作时,应该怎么处理!

2.1、插入场景

将一个节点插入到红黑树中,需要执行哪些步骤呢?

对于第一步,比较好理解,红黑树其实就是二叉树的一种特殊形态的树形结构,先找到合适的位置,然后将节点插入到树上。

红黑树的实现原理是什么

对于第二步,为什么新插入的节点要设置为红色呢?

因为插入之前所有根至外部节点的路径上黑色节点数目都相同,所以如果插入的节点是黑色,肯定会导致黑色节点数目不相同!

而相对的插入红节点可能也会违反不能出现两个连续的红节点,如果违反条件,直接进行颜色转换或者旋转操作即可!

相对将插入的节点着色为黑色,红色操作可能更简单些!因为根节点为黑色,如果是新插入的节点为根节点,直接将颜色设置为黑色!

既然新插入的节点为红色,那么我们就继续来分析一下,新插入节点的场景,例如:

当新插入的节点的父亲为黑色时!因为新插入的节点为红色,因此不会违反任何特性!

红黑树的实现原理是什么

当新插入的节点的父亲为红色时!因为新插入的节点为红色,违反不能出现两个连续的红节点,因此需要进行调整!

红黑树的实现原理是什么

这种场景有3种调整情况,为了便于下面分析,假设将新插入节点用z代替,z的父节点用a代替,a的父节点用c代替,z的叔节点用y代替,如下:

红黑树的实现原理是什么

情况1:z的叔节点y是红色的

case1调整过程如下:

红黑树的实现原理是什么

调整说明:因为节点 z 是一个红色节点,其父节点 a 是红色的,违反了特性4,因此需要进行调整。因为其叔节点 y 是红色的,于是可以修改节点 a、节点 y  为黑色,此时节点 c 的黑高会发生变化,由原来的黑高1变成黑高2,为了节点 c 保持黑高不变,将其变成红色。

此时,由于节点 c 由黑色变成了红色,如果节点 c 的父节点是红色,也会违反特性4,继续将节点 c 看成是节点 z,向上回溯调整树!

需要注意的是:对于新插入的节点 z 是节点a 的左子树的情况,操作与上述一致;对于新插入的节点 z 是节点 c  的右子树的节点的情况,操作与上述对称!

情况2:z的叔节点y是黑色,且z是一个左孩子

case2调整过程如下:

红黑树的实现原理是什么

调整说明:这种情况,并不能像上面那样改变节点颜色就可以满足要求,因为如果将节点z 的父节点 a 变成了黑色,  那么树的黑高就会发生变化,必然会引起对性质5的违反。比如,此时节点y为黑色, 节点c 的右子树高度为2(忽略子树),左子树高也相同,如果简单的修改节点a  为黑色,那么节点c 的左子树的黑高会比右子树大1, 此时即使将节点c 修改为红色也于事无补!

因此,单靠颜色转变无非解决问题,需要进行旋转调整。先绕节点 a 的父节点进行右旋转,再将节点 a、节点 c 的颜色进行互换!最终结果与插入前一致!

需要注意的是:对于新插入的节点 z 是节点 c 的右子树的节点的情况,操作与上述对称!

情况3:z的叔节点y是黑色,且z是一个右孩子

case3调调整过程如下:

红黑树的实现原理是什么

调整说明:当节点 z 是一个右孩子时,先绕节点 a  进行左旋转,之后树的形态就变成如上面介绍的情况2,再进行右旋转、颜色转变,即可实现红黑树的特性!

需要注意的是:对于新插入的节点 z 是节点 c 的右子树的节点的情况,操作与上述对称!

以上就是红黑树新增节点时,所有可能的操作以及调整方式!

可以得出如下结论:对插入节点后的调整所做的旋转操作不会超过2次!

2.2、删除场景

我们继续来看看删除场景,对于二叉查找树操作,我们知道有如下步骤:

二叉查找树删除过程图:

红黑树的实现原理是什么

红黑树的操作也是如此,步骤如下;

在第一步中,首先我们重点要弄清楚什么是删除节点?

这个删除节点,某些情况下并非我们真正传入的删除值,对于拥有左子树、右子树的节点来说,删除节点指的是被删除节点的后继节点或者前驱节点!

可能有点绕,例如上图中拥有左子树、右子树的删除场景,我们传入需要删除的节点是  80,但是实际上删除节点的是85节点(85是一个叶子节点),然后将80节点内容替换成85,做了一个偷天换日的操作!

因此无论对于哪种情况,我们可以得出结论:删除节点一定是一个单分支节点或者叶子节点,了解这个结论对于后面我们的红黑树删除过程分析会非常有用!

清楚删除流程之后,剩下的重点就是如何进行修正,以满足红黑树的特性,那么,哪些场景下的删除需要进行调整,我们一起来看一下!

2.2.1、删除的节点为红色

当删除的节点为红色时,这种情况直接将删除节点移除,理由如下:

2.2.2、删除的节点为黑色

当删除的节点为黑色时,因为删除节点的父节点失去了一个黑色子节点,这种情况会导致左右子树不平衡,因此需要进行调整,假设x为被删节点的替换节点,也就是说:

w为x的兄弟节点,有以下几种情况!

1)x的兄弟节点w是红色的

case1调整过程如下:

红黑树的实现原理是什么

调整说明:因为节点 c 的左子树被删去了一个黑色节点,导致节点 c 的左子树黑高少了1,所以节点c 是不平衡的。可以对节点c  进行一次左旋,然后修改节点80和节点120的颜色。

此时,x的父亲节点c依然不平衡,节点x 的兄弟节点w 变成黑色的!

继续看下面的分析,这种不平衡由下面的几种情况进行处理!

2)x的兄弟节点w是黑色的,并且w的两个子节点都是黑色的

当x的兄弟节点 w 是黑色的,并且w的两个子节点都是黑色的时,此时需要分两种情况!

情况2.1:x的父节点为红色

case2.1调整过程如下:

红黑树的实现原理是什么

调整说明:在删除节点后,左图节点 c 不平衡,节点c 左子树的黑高为hl+1,节点c 左子树的黑高为hr+2,左子树黑高小于右子树黑高。因此直接将节点c  修改为黑色,节点 w 修改为红色,此时的黑高又恢复如初!但是节点c 作为子节点,因为黑高减少,需要继续向上回溯调整树的黑高,此时节点c 作为新的节点x。

情况2.2:x的父节点为黑色

case2.2调整过程如下:

红黑树的实现原理是什么

调整说明:只需要将节点 w 修改为红色,继续向上回溯调整树的黑高,此时节点 c 作为新的节点x。

3)x的兄弟节点w是黑色的,并且w的右孩子是红色的

当x的兄弟节点w是黑色的,并且w的右孩子是红色的,此时也需要分四种情况!

情况3.1:x的父节点为黑色,w的左孩子是黑色的

case3.1调整过程如下:

红黑树的实现原理是什么

调整说明:因为删除节点导致节点c 不平衡,对节点c 进行一次左旋转,将节点w 的右孩子颜色修改为黑色。此时节点c 已经达到平衡,同时节点w  也达到平衡,整棵树已经平衡了!

情况3.2:x的父节点为黑色,w的左孩子是红色的

case3.2调整过程如下:

红黑树的实现原理是什么

调整说明:同样的,对节点c 进行一次左旋转,将节点w 的右孩子颜色修改为黑色。此时节点c 已经达到平衡,同时节点w 也达到平衡,整棵树已经平衡了!

情况3.3:x的父节点为红色,w的左孩子是黑色的

case3.3调整过程如下:

红黑树的实现原理是什么

调整说明:对节点c 进行一次左旋转,将节点 w 的右孩子颜色修改为黑色,同时将节点80 和节点100 颜色进行互换。此时节点c 已经达到平衡,同时节点w  也达到平衡,整棵树已经平衡了!

情况3.4:x的父节点为红色,w的左孩子是红色的

case3.4调整过程如下:

红黑树的实现原理是什么

调整说明:同样的,对节点c 进行一次左旋转,将节点 w 的右孩子颜色修改为黑色,同时将节点80 和节点100 颜色进行互换。此时节点c  已经达到平衡,同时节点w 也达到平衡,整棵树已经平衡了!

4)x的兄弟节点w是黑色的,而且w的左孩子是红色的,w的右孩子是黑色的

当x的兄弟节点w是黑色的,而且w的左孩子是红色的,w的右孩子是黑色的,此时也需要分2种情况!

情况4.1:x的父节点为红色

case4.1调整过程如下:

红黑树的实现原理是什么

调整说明:对节点w 进行一次右旋转,将节点90和节点100 进行颜色互换,此时节点x 和节点w  的关系变成:x的兄弟节点w是黑色的,并且w的右孩子是红色的。此时按照case3.3情况进行处理即可!

情况4.2:x的父节点为黑色

case4.2调整过程如下:

红黑树的实现原理是什么

调整说明:同样的,对节点w 进行一次右旋转,将节点90和节点100进行颜色互换,此时节点x 和节点w  的关系变成:x的兄弟节点w是黑色的,并且w的右孩子是红色的。此时按照case3.1情况进行处理即可!

删除的场景相比插入要多很多,情况也比较复杂,但是基本有自己的规律,我们只需要把规律总结出来,然后就可以用逻辑代码来实现!

需要注意的是:此次节点x 位于节点c 的左子树,如果位于右子树,操作与之对称!

可以得出如下结论:对删除节点后的调整所做的旋转操作不会超过3次!

三、代码实践

接下来,我们从代码层面来定义一下树的实体结构,如下:

public class RBTNode<E extends Comparable<E>> {           boolean color;           E key;           RBTNode<E> parent;           RBTNode<E> left;           RBTNode<E> right;      public RBTNode(E key, boolean color, RBTNode<E> parent, RBTNode<E> left, RBTNode<E> right) {         this.key = key;         this.color = color;         this.parent = parent;         this.left = left;         this.right = right;     }      @Override     public String toString() {         return "RBTNode{" +                 "color=" + (color ? "red":"black") +                 ", key=" + key +                 '}';     } }

我们创建一个算法类RBTSolution,完整实现如下:

public class RBTSolution<E extends Comparable<E>> {           public RBTNode<E> root;           private static final boolean RED = false;     private static final boolean BLACK = true;            public void insert(E key) {         System.out.println("插入[" + key + "]:");         RBTNode<E> node=new RBTNode<E>(key, BLACK,null,null,null);         // 如果新建结点失败,则返回。         if (node != null)             insert(node);     }           private void insert(RBTNode<E> node) {         int cmp;         RBTNode<E> y = null;         RBTNode<E> x = this.root;          // 1. 将红黑树当作一颗二叉查找树,将节点添加到二叉查找树中。         while (x != null) {             y = x;             cmp = node.key.compareTo(x.key);             if (cmp < 0)                 x = x.left;             else                 x = x.right;         }          node.parent = y;         if (y!=null) {             cmp = node.key.compareTo(y.key);             if (cmp < 0)                 y.left = node;             else                 y.right = node;         } else {             this.root = node;         }          // 2. 设置节点的颜色为红色         node.color = RED;          // 3. 将它重新修正为一颗二叉查找树         insertFixUp(node);     }           private void insertFixUp(RBTNode<E> node) {         RBTNode<E> parent, gparent;          // 若“父节点存在,并且父节点的颜色是红色”         while (((parent = parentOf(node))!=null) && isRed(parent)) {             gparent = parentOf(parent);              //若“父节点”是“祖父节点的左孩子”             if (parent == gparent.left) {                 // Case 1条件:叔叔节点是红色                 RBTNode<E> uncle = gparent.right;                 if ((uncle!=null) && isRed(uncle)) {                     setBlack(uncle);                     setBlack(parent);                     setRed(gparent);                     node = gparent;                     continue;                 }                  // Case 3条件:叔叔是黑色,且当前节点是右孩子                 if (parent.right == node) {                     RBTNode<E> tmp;                     leftRotate(parent);                     tmp = parent;                     parent = node;                     node = tmp;                 }                  // Case 2条件:叔叔是黑色,且当前节点是左孩子。                 setBlack(parent);                 setRed(gparent);                 rightRotate(gparent);             } else {    //若“z的父节点”是“z的祖父节点的右孩子”                 // Case 1条件:叔叔节点是红色                 RBTNode<E> uncle = gparent.left;                 if ((uncle!=null) && isRed(uncle)) {                     setBlack(uncle);                     setBlack(parent);                     setRed(gparent);                     node = gparent;                     continue;                 }                  // Case 2条件:叔叔是黑色,且当前节点是左孩子                 if (parent.left == node) {                     RBTNode<E> tmp;                     rightRotate(parent);                     tmp = parent;                     parent = node;                     node = tmp;                 }                  // Case 3条件:叔叔是黑色,且当前节点是右孩子。                 setBlack(parent);                 setRed(gparent);                 leftRotate(gparent);             }         }          // 将根节点设为黑色         setBlack(this.root);     }           public void remove(E key) {         RBTNode<E> node;          if ((node = search(root, key)) != null)             remove(node);     }            private void remove(RBTNode<E> node) {         RBTNode<E> child, parent;         boolean color;          // 被删除节点的"左右孩子都不为空"的情况。         if ( (node.left!=null) && (node.right!=null) ) {             // 被删节点的后继节点。(称为"取代节点")             // 用它来取代"被删节点"的位置,然后再将"被删节点"去掉。             RBTNode<E> replace = node;              // 获取后继节点             replace = replace.right;             while (replace.left != null)                 replace = replace.left;              // "node节点"不是根节点(只有根节点不存在父节点)             if (parentOf(node)!=null) {                 if (parentOf(node).left == node)                     parentOf(node).left = replace;                 else                     parentOf(node).right = replace;             } else {                 // "node节点"是根节点,更新根节点。                 this.root = replace;             }              // child是"取代节点"的右孩子,也是需要"调整的节点"。             // "取代节点"肯定不存在左孩子!因为它是一个后继节点。             child = replace.right;             parent = parentOf(replace);             // 保存"取代节点"的颜色             color = colorOf(replace);              // "被删除节点"是"它的后继节点的父节点"             if (parent == node) {                 parent = replace;             } else {                 // child不为空                 if (child!=null)                     setParent(child, parent);                 parent.left = child;                  replace.right = node.right;                 setParent(node.right, replace);             }              replace.parent = node.parent;             replace.color = node.color;             replace.left = node.left;             node.left.parent = replace;              if (color == BLACK)                 removeFixUp(child, parent);              node = null;             return ;         }          if (node.left !=null) {             child = node.left;         } else {             child = node.right;         }          parent = node.parent;         // 保存"取代节点"的颜色         color = node.color;          if (child!=null)             child.parent = parent;          // "node节点"不是根节点         if (parent!=null) {             if (parent.left == node)                 parent.left = child;             else                 parent.right = child;         } else {             this.root = child;         }          if (color == BLACK)             removeFixUp(child, parent);         node = null;     }           private void removeFixUp(RBTNode<E> node, RBTNode<E> parent) {         RBTNode<E> other;          while ((node==null || isBlack(node)) && (node != this.root)) {             if (parent.left == node) {                 other = parent.right;                 if (isRed(other)) {                     // Case 1: x的兄弟w是红色的                     setBlack(other);                     setRed(parent);                     leftRotate(parent);                     other = parent.right;                 }                  if ((other.left==null || isBlack(other.left)) &&                         (other.right==null || isBlack(other.right))) {                     // Case 2: x的兄弟w是黑色,且w的俩个孩子也都是黑色的                     setRed(other);                     node = parent;                     parent = parentOf(node);                 } else {                      if (other.right==null || isBlack(other.right)) {                         // Case 4: x的兄弟w是黑色的,并且w的左孩子是红色,右孩子为黑色。                         setBlack(other.left);                         setRed(other);                         rightRotate(other);                         other = parent.right;                     }                     // Case 3: x的兄弟w是黑色的;并且w的右孩子是红色的,左孩子任意颜色。                     setColor(other, colorOf(parent));                     setBlack(parent);                     setBlack(other.right);                     leftRotate(parent);                     node = this.root;                     break;                 }             } else {                  other = parent.left;                 if (isRed(other)) {                     // Case 1: x的兄弟w是红色的                     setBlack(other);                     setRed(parent);                     rightRotate(parent);                     other = parent.left;                 }                  if ((other.left==null || isBlack(other.left)) &&                         (other.right==null || isBlack(other.right))) {                     // Case 2: x的兄弟w是黑色,且w的俩个孩子也都是黑色的                     setRed(other);                     node = parent;                     parent = parentOf(node);                 } else {                      if (other.left==null || isBlack(other.left)) {                         // Case 4: x的兄弟w是黑色的,并且w的左孩子是红色,右孩子为黑色。                         setBlack(other.right);                         setRed(other);                         leftRotate(other);                         other = parent.left;                     }                      // Case 3: x的兄弟w是黑色的;并且w的右孩子是红色的,左孩子任意颜色。                     setColor(other, colorOf(parent));                     setBlack(parent);                     setBlack(other.left);                     rightRotate(parent);                     node = this.root;                     break;                 }             }         }          if (node!=null)             setBlack(node);     }            public RBTNode<E> search(E key) {         return search(root, key);     }            private RBTNode<E> search(RBTNode<E> x, E key) {         if (x==null)             return x;          int cmp = key.compareTo(x.key);         if (cmp < 0)             return search(x.left, key);         else if (cmp > 0)             return search(x.right, key);         else             return x;     }           public void middleTreeIterator(RBTNode<E> node){         if(node != null){             middleTreeIterator(node.left);//遍历当前节点左子树             System.out.println("key:" + node.key);             middleTreeIterator(node.right);//遍历当前节点右子树         }     }        private RBTNode<E> parentOf(RBTNode<E> node) {         return node!=null ? node.parent : null;     }     private boolean colorOf(RBTNode<E> node) {         return node!=null ? node.color : BLACK;     }     private boolean isRed(RBTNode<E> node) {         return ((node!=null)&&(node.color==RED)) ? true : false;     }     private boolean isBlack(RBTNode<E> node) {         return !isRed(node);     }     private void setBlack(RBTNode<E> node) {         if (node!=null)             node.color = BLACK;     }     private void setRed(RBTNode<E> node) {         if (node!=null)             node.color = RED;     }     private void setParent(RBTNode<E> node, RBTNode<E> parent) {         if (node!=null)             node.parent = parent;     }     private void setColor(RBTNode<E> node, boolean color) {         if (node!=null)             node.color = color;     }            private void leftRotate(RBTNode<E> x) {         // 设置x的右孩子为y         RBTNode<E> y = x.right;          // 将 “y的左孩子” 设为 “x的右孩子”;         // 如果y的左孩子非空,将 “x” 设为 “y的左孩子的父亲”         x.right = y.left;         if (y.left != null)             y.left.parent = x;          // 将 “x的父亲” 设为 “y的父亲”         y.parent = x.parent;          if (x.parent == null) {             this.root = y;            // 如果 “x的父亲” 是空节点,则将y设为根节点         } else {             if (x.parent.left == x)                 x.parent.left = y;    // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”             else                 x.parent.right = y;    // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”         }          // 将 “x” 设为 “y的左孩子”         y.left = x;         // 将 “x的父节点” 设为 “y”         x.parent = y;     }           private void rightRotate(RBTNode<E> y) {         // 设置x是当前节点的左孩子。         RBTNode<E> x = y.left;          // 将 “x的右孩子” 设为 “y的左孩子”;         // 如果"x的右孩子"不为空的话,将 “y” 设为 “x的右孩子的父亲”         y.left = x.right;         if (x.right != null)             x.right.parent = y;          // 将 “y的父亲” 设为 “x的父亲”         x.parent = y.parent;          if (y.parent == null) {             this.root = x;            // 如果 “y的父亲” 是空节点,则将x设为根节点         } else {             if (y == y.parent.right)                 y.parent.right = x;    // 如果 y是它父节点的右孩子,则将x设为“y的父节点的右孩子”             else                 y.parent.left = x;    // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”         }          // 将 “y” 设为 “x的右孩子”         x.right = y;          // 将 “y的父节点” 设为 “x”         y.parent = x;     } }

测试代码,如下:

public class RBTClient {      public static void main(String[] args) {         RBTSolution<Integer> tree = new RBTSolution<Integer>();         //插入节点         System.out.println("========插入元素========");         tree.insert(new Integer(100));         tree.insert(new Integer(85));         tree.insert(new Integer(120));         tree.insert(new Integer(60));         tree.insert(new Integer(90));         tree.insert(new Integer(80));         tree.insert(new Integer(130));         System.out.println("========中序遍历元素========");          //中序遍历         tree.middleTreeIterator(tree.root);         System.out.println("========查找key为100的元素========");          //查询节点         RBTNode<Integer> searchResult = tree.search(100);         System.out.println("查找结果:" + searchResult);         System.out.println("========删除key为90的元素========");          //删除节点         tree.remove(90);         System.out.println("========再次中序遍历元素========");          //中序遍历         tree.middleTreeIterator(tree.root);     } }

输出结果如下:

========插入元素======== 插入[100]: 插入[85]: 插入[120]: 插入[60]: 插入[90]: 插入[80]: 插入[130]: ========中序遍历元素======== key:60 key:80 key:85 key:90 key:100 key:120 key:130 ========查找key为100的元素======== 查找结果:RBTNode{color=red, key=100} ========删除key为90的元素======== ========再次中序遍历元素======== key:60 key:80 key:85 key:100 key:120 key:130

以上就是红黑树的实现原理是什么,小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注编程网行业资讯频道。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-前端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯