文章详情

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

请输入下面的图形验证码

提交验证

短信预约提醒成功

红黑树是怎么实现的,看这篇真的就够了!

2024-12-24 18:45

关注

红黑树由来:在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees),后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树,就此红黑树出现在软件开发者的视野里!

一、摘要

在上篇文章中,我们详细的介绍到平衡二叉查找树的算法以及代码实践,我们知道平衡二叉查找树是一个高度平衡的二叉树,也就是说树的高度差不能大于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次!

三、代码实践

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

 

  1. public class RBTNode> { 
  2.  
  3.      
  4.     boolean color; 
  5.  
  6.      
  7.     E key
  8.  
  9.      
  10.     RBTNode parent; 
  11.  
  12.      
  13.     RBTNode left
  14.  
  15.      
  16.     RBTNode right
  17.  
  18.     public RBTNode(E key, boolean color, RBTNode parent, RBTNode left, RBTNode right) { 
  19.         this.key = key
  20.         this.color = color; 
  21.         this.parent = parent; 
  22.         this.left = left
  23.         this.right = right
  24.     } 
  25.  
  26.     @Override 
  27.     public String toString() { 
  28.         return "RBTNode{" + 
  29.                 "color=" + (color ? "red":"black") + 
  30.                 ", key=" + key + 
  31.                 '}'
  32.     } 

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

 

  1. public class RBTSolution> { 
  2.  
  3.      
  4.     public RBTNode root; 
  5.  
  6.      
  7.     private static final boolean RED = false
  8.     private static final boolean BLACK = true
  9.  
  10.  
  11.      
  12.     public void insert(E key) { 
  13.         System.out.println("插入[" + key + "]:"); 
  14.         RBTNode node=new RBTNode(key, BLACK,null,null,null); 
  15.         // 如果新建结点失败,则返回。 
  16.         if (node != null
  17.             insert(node); 
  18.     } 
  19.  
  20.      
  21.     private void insert(RBTNode node) { 
  22.         int cmp; 
  23.         RBTNode y = null
  24.         RBTNode x = this.root; 
  25.  
  26.         // 1. 将红黑树当作一颗二叉查找树,将节点添加到二叉查找树中。 
  27.         while (x != null) { 
  28.             y = x; 
  29.             cmp = node.key.compareTo(x.key); 
  30.             if (cmp < 0) 
  31.                 x = x.left
  32.             else 
  33.                 x = x.right
  34.         } 
  35.  
  36.         node.parent = y; 
  37.         if (y!=null) { 
  38.             cmp = node.key.compareTo(y.key); 
  39.             if (cmp < 0) 
  40.                 y.left = node; 
  41.             else 
  42.                 y.right = node; 
  43.         } else { 
  44.             this.root = node; 
  45.         } 
  46.  
  47.         // 2. 设置节点的颜色为红色 
  48.         node.color = RED; 
  49.  
  50.         // 3. 将它重新修正为一颗二叉查找树 
  51.         insertFixUp(node); 
  52.     } 
  53.  
  54.      
  55.     private void insertFixUp(RBTNode node) { 
  56.         RBTNode parent, gparent; 
  57.  
  58.         // 若“父节点存在,并且父节点的颜色是红色” 
  59.         while (((parent = parentOf(node))!=null) && isRed(parent)) { 
  60.             gparent = parentOf(parent); 
  61.  
  62.             //若“父节点”是“祖父节点的左孩子” 
  63.             if (parent == gparent.left) { 
  64.                 // Case 1条件:叔叔节点是红色 
  65.                 RBTNode uncle = gparent.right
  66.                 if ((uncle!=null) && isRed(uncle)) { 
  67.                     setBlack(uncle); 
  68.                     setBlack(parent); 
  69.                     setRed(gparent); 
  70.                     node = gparent; 
  71.                     continue
  72.                 } 
  73.  
  74.                 // Case 3条件:叔叔是黑色,且当前节点是右孩子 
  75.                 if (parent.right == node) { 
  76.                     RBTNode tmp; 
  77.                     leftRotate(parent); 
  78.                     tmp = parent; 
  79.                     parent = node; 
  80.                     node = tmp; 
  81.                 } 
  82.  
  83.                 // Case 2条件:叔叔是黑色,且当前节点是左孩子。 
  84.                 setBlack(parent); 
  85.                 setRed(gparent); 
  86.                 rightRotate(gparent); 
  87.             } else {    //若“z的父节点”是“z的祖父节点的右孩子” 
  88.                 // Case 1条件:叔叔节点是红色 
  89.                 RBTNode uncle = gparent.left
  90.                 if ((uncle!=null) && isRed(uncle)) { 
  91.                     setBlack(uncle); 
  92.                     setBlack(parent); 
  93.                     setRed(gparent); 
  94.                     node = gparent; 
  95.                     continue
  96.                 } 
  97.  
  98.                 // Case 2条件:叔叔是黑色,且当前节点是左孩子 
  99.                 if (parent.left == node) { 
  100.                     RBTNode tmp; 
  101.                     rightRotate(parent); 
  102.                     tmp = parent; 
  103.                     parent = node; 
  104.                     node = tmp; 
  105.                 } 
  106.  
  107.                 // Case 3条件:叔叔是黑色,且当前节点是右孩子。 
  108.                 setBlack(parent); 
  109.                 setRed(gparent); 
  110.                 leftRotate(gparent); 
  111.             } 
  112.         } 
  113.  
  114.         // 将根节点设为黑色 
  115.         setBlack(this.root); 
  116.     } 
  117.  
  118.      
  119.     public void remove(E key) { 
  120.         RBTNode node; 
  121.  
  122.         if ((node = search(root, key)) != null
  123.             remove(node); 
  124.     } 
  125.  
  126.  
  127.      
  128.     private void remove(RBTNode node) { 
  129.         RBTNode child, parent; 
  130.         boolean color; 
  131.  
  132.         // 被删除节点的"左右孩子都不为空"的情况。 
  133.         if ( (node.left!=null) && (node.right!=null) ) { 
  134.             // 被删节点的后继节点。(称为"取代节点"
  135.             // 用它来取代"被删节点"的位置,然后再将"被删节点"去掉。 
  136.             RBTNode replace = node; 
  137.  
  138.             // 获取后继节点 
  139.             replace = replace.right
  140.             while (replace.left != null
  141.                 replace = replace.left
  142.  
  143.             // "node节点"不是根节点(只有根节点不存在父节点) 
  144.             if (parentOf(node)!=null) { 
  145.                 if (parentOf(node).left == node) 
  146.                     parentOf(node).left = replace
  147.                 else 
  148.                     parentOf(node).right = replace
  149.             } else { 
  150.                 // "node节点"是根节点,更新根节点。 
  151.                 this.root = replace
  152.             } 
  153.  
  154.             // child是"取代节点"的右孩子,也是需要"调整的节点"。 
  155.             // "取代节点"肯定不存在左孩子!因为它是一个后继节点。 
  156.             child = replace.right
  157.             parent = parentOf(replace); 
  158.             // 保存"取代节点"的颜色 
  159.             color = colorOf(replace); 
  160.  
  161.             // "被删除节点""它的后继节点的父节点" 
  162.             if (parent == node) { 
  163.                 parent = replace
  164.             } else { 
  165.                 // child不为空 
  166.                 if (child!=null
  167.                     setParent(child, parent); 
  168.                 parent.left = child; 
  169.  
  170.                 replace.right = node.right
  171.                 setParent(node.rightreplace); 
  172.             } 
  173.  
  174.             replace.parent = node.parent; 
  175.             replace.color = node.color; 
  176.             replace.left = node.left
  177.             node.left.parent = replace
  178.  
  179.             if (color == BLACK) 
  180.                 removeFixUp(child, parent); 
  181.  
  182.             node = null
  183.             return ; 
  184.         } 
  185.  
  186.         if (node.left !=null) { 
  187.             child = node.left
  188.         } else { 
  189.             child = node.right
  190.         } 
  191.  
  192.         parent = node.parent; 
  193.         // 保存"取代节点"的颜色 
  194.         color = node.color; 
  195.  
  196.         if (child!=null
  197.             child.parent = parent; 
  198.  
  199.         // "node节点"不是根节点 
  200.         if (parent!=null) { 
  201.             if (parent.left == node) 
  202.                 parent.left = child; 
  203.             else 
  204.                 parent.right = child; 
  205.         } else { 
  206.             this.root = child; 
  207.         } 
  208.  
  209.         if (color == BLACK) 
  210.             removeFixUp(child, parent); 
  211.         node = null
  212.     } 
  213.  
  214.      
  215.     private void removeFixUp(RBTNode node, RBTNode parent) { 
  216.         RBTNode other; 
  217.  
  218.         while ((node==null || isBlack(node)) && (node != this.root)) { 
  219.             if (parent.left == node) { 
  220.                 other = parent.right
  221.                 if (isRed(other)) { 
  222.                     // Case 1: x的兄弟w是红色的 
  223.                     setBlack(other); 
  224.                     setRed(parent); 
  225.                     leftRotate(parent); 
  226.                     other = parent.right
  227.                 } 
  228.  
  229.                 if ((other.left==null || isBlack(other.left)) && 
  230.                         (other.right==null || isBlack(other.right))) { 
  231.                     // Case 2: x的兄弟w是黑色,且w的俩个孩子也都是黑色的 
  232.                     setRed(other); 
  233.                     node = parent; 
  234.                     parent = parentOf(node); 
  235.                 } else { 
  236.  
  237.                     if (other.right==null || isBlack(other.right)) { 
  238.                         // Case 4: x的兄弟w是黑色的,并且w的左孩子是红色,右孩子为黑色。 
  239.                         setBlack(other.left); 
  240.                         setRed(other); 
  241.                         rightRotate(other); 
  242.                         other = parent.right
  243.                     } 
  244.                     // Case 3: x的兄弟w是黑色的;并且w的右孩子是红色的,左孩子任意颜色。 
  245.                     setColor(other, colorOf(parent)); 
  246.                     setBlack(parent); 
  247.                     setBlack(other.right); 
  248.                     leftRotate(parent); 
  249.                     node = this.root; 
  250.                     break; 
  251.                 } 
  252.             } else { 
  253.  
  254.                 other = parent.left
  255.                 if (isRed(other)) { 
  256.                     // Case 1: x的兄弟w是红色的 
  257.                     setBlack(other); 
  258.                     setRed(parent); 
  259.                     rightRotate(parent); 
  260.                     other = parent.left
  261.                 } 
  262.  
  263.                 if ((other.left==null || isBlack(other.left)) && 
  264.                         (other.right==null || isBlack(other.right))) { 
  265.                     // Case 2: x的兄弟w是黑色,且w的俩个孩子也都是黑色的 
  266.                     setRed(other); 
  267.                     node = parent; 
  268.                     parent = parentOf(node); 
  269.                 } else { 
  270.  
  271.                     if (other.left==null || isBlack(other.left)) { 
  272.                         // Case 4: x的兄弟w是黑色的,并且w的左孩子是红色,右孩子为黑色。 
  273.                         setBlack(other.right); 
  274.                         setRed(other); 
  275.                         leftRotate(other); 
  276.                         other = parent.left
  277.                     } 
  278.  
  279.                     // Case 3: x的兄弟w是黑色的;并且w的右孩子是红色的,左孩子任意颜色。 
  280.                     setColor(other, colorOf(parent)); 
  281.                     setBlack(parent); 
  282.                     setBlack(other.left); 
  283.                     rightRotate(parent); 
  284.                     node = this.root; 
  285.                     break; 
  286.                 } 
  287.             } 
  288.         } 
  289.  
  290.         if (node!=null
  291.             setBlack(node); 
  292.     } 
  293.  
  294.  
  295.      
  296.     public RBTNode search(E key) { 
  297.         return search(root, key); 
  298.     } 
  299.  
  300.  
  301.      
  302.     private RBTNode search(RBTNode x, E key) { 
  303.         if (x==null
  304.             return x; 
  305.  
  306.         int cmp = key.compareTo(x.key); 
  307.         if (cmp < 0) 
  308.             return search(x.leftkey); 
  309.         else if (cmp > 0) 
  310.             return search(x.rightkey); 
  311.         else 
  312.             return x; 
  313.     } 
  314.  
  315.      
  316.     public void middleTreeIterator(RBTNode node){ 
  317.         if(node != null){ 
  318.             middleTreeIterator(node.left);//遍历当前节点左子树 
  319.             System.out.println("key:" + node.key); 
  320.             middleTreeIterator(node.right);//遍历当前节点右子树 
  321.         } 
  322.     } 
  323.  
  324.  
  325.  
  326.     private RBTNode parentOf(RBTNode node) { 
  327.         return node!=null ? node.parent : null
  328.     } 
  329.     private boolean colorOf(RBTNode node) { 
  330.         return node!=null ? node.color : BLACK; 
  331.     } 
  332.     private boolean isRed(RBTNode node) { 
  333.         return ((node!=null)&&(node.color==RED)) ? true : false
  334.     } 
  335.     private boolean isBlack(RBTNode node) { 
  336.         return !isRed(node); 
  337.     } 
  338.     private void setBlack(RBTNode node) { 
  339.         if (node!=null
  340.             node.color = BLACK; 
  341.     } 
  342.     private void setRed(RBTNode node) { 
  343.         if (node!=null
  344.             node.color = RED; 
  345.     } 
  346.     private void setParent(RBTNode node, RBTNode parent) { 
  347.         if (node!=null
  348.             node.parent = parent; 
  349.     } 
  350.     private void setColor(RBTNode node, boolean color) { 
  351.         if (node!=null
  352.             node.color = color; 
  353.     } 
  354.  
  355.  
  356.      
  357.     private void leftRotate(RBTNode x) { 
  358.         // 设置x的右孩子为y 
  359.         RBTNode y = x.right
  360.  
  361.         // 将 “y的左孩子” 设为 “x的右孩子”; 
  362.         // 如果y的左孩子非空,将 “x” 设为 “y的左孩子的父亲” 
  363.         x.right = y.left
  364.         if (y.left != null
  365.             y.left.parent = x; 
  366.  
  367.         // 将 “x的父亲” 设为 “y的父亲” 
  368.         y.parent = x.parent; 
  369.  
  370.         if (x.parent == null) { 
  371.             this.root = y;            // 如果 “x的父亲” 是空节点,则将y设为根节点 
  372.         } else { 
  373.             if (x.parent.left == x) 
  374.                 x.parent.left = y;    // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子” 
  375.             else 
  376.                 x.parent.right = y;    // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子” 
  377.         } 
  378.  
  379.         // 将 “x” 设为 “y的左孩子” 
  380.         y.left = x; 
  381.         // 将 “x的父节点” 设为 “y” 
  382.         x.parent = y; 
  383.     } 
  384.  
  385.      
  386.     private void rightRotate(RBTNode y) { 
  387.         // 设置x是当前节点的左孩子。 
  388.         RBTNode x = y.left
  389.  
  390.         // 将 “x的右孩子” 设为 “y的左孩子”; 
  391.         // 如果"x的右孩子"不为空的话,将 “y” 设为 “x的右孩子的父亲” 
  392.         y.left = x.right
  393.         if (x.right != null
  394.             x.right.parent = y; 
  395.  
  396.         // 将 “y的父亲” 设为 “x的父亲” 
  397.         x.parent = y.parent; 
  398.  
  399.         if (y.parent == null) { 
  400.             this.root = x;            // 如果 “y的父亲” 是空节点,则将x设为根节点 
  401.         } else { 
  402.             if (y == y.parent.right
  403.                 y.parent.right = x;    // 如果 y是它父节点的右孩子,则将x设为“y的父节点的右孩子” 
  404.             else 
  405.                 y.parent.left = x;    // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子” 
  406.         } 
  407.  
  408.         // 将 “y” 设为 “x的右孩子” 
  409.         x.right = y; 
  410.  
  411.         // 将 “y的父节点” 设为 “x” 
  412.         y.parent = x; 
  413.     } 

测试代码,如下:

 

  1. public class RBTClient { 
  2.  
  3.     public static void main(String[] args) { 
  4.         RBTSolution<Integer> tree = new RBTSolution<Integer>(); 
  5.         //插入节点 
  6.         System.out.println("========插入元素========"); 
  7.         tree.insert(new Integer(100)); 
  8.         tree.insert(new Integer(85)); 
  9.         tree.insert(new Integer(120)); 
  10.         tree.insert(new Integer(60)); 
  11.         tree.insert(new Integer(90)); 
  12.         tree.insert(new Integer(80)); 
  13.         tree.insert(new Integer(130)); 
  14.         System.out.println("========中序遍历元素========"); 
  15.  
  16.         //中序遍历 
  17.         tree.middleTreeIterator(tree.root); 
  18.         System.out.println("========查找key为100的元素========"); 
  19.  
  20.         //查询节点 
  21.         RBTNode<Integer> searchResult = tree.search(100); 
  22.         System.out.println("查找结果:" + searchResult); 
  23.         System.out.println("========删除key为90的元素========"); 
  24.  
  25.         //删除节点 
  26.         tree.remove(90); 
  27.         System.out.println("========再次中序遍历元素========"); 
  28.  
  29.         //中序遍历 
  30.         tree.middleTreeIterator(tree.root); 
  31.     } 

输出结果如下:

 

  1. ========插入元素======== 
  2. 插入[100]: 
  3. 插入[85]: 
  4. 插入[120]: 
  5. 插入[60]: 
  6. 插入[90]: 
  7. 插入[80]: 
  8. 插入[130]: 
  9. ========中序遍历元素======== 
  10. key:60 
  11. key:80 
  12. key:85 
  13. key:90 
  14. key:100 
  15. key:120 
  16. key:130 
  17. ========查找key为100的元素======== 
  18. 查找结果:RBTNode{color=red, key=100} 
  19. ========删除key为90的元素======== 
  20. ========再次中序遍历元素======== 
  21. key:60 
  22. key:80 
  23. key:85 
  24. key:100 
  25. key:120 
  26. key:130 

四、总结

本篇文章,前前后后写了大概一个星期,尤其是删除逻辑,比较复杂,如果有理解不对的地方,欢迎网友们指出!

以下是红黑树总结:

五、参考

简书 - 遇见技术 - JAVA学习-红黑树详解

博客园 - skywang12345 - 红黑树(五)之 Java的实现

ivanzz1001 - 红黑树的原理及实现

来源:Java极客技术内容投诉

免责声明:

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

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

软考中级精品资料免费领

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

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

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

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

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

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

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