精华内容
下载资源
问答
  • 红黑树变色
    千次阅读
    2019-12-07 10:43:52

    一、红黑树性质

    1. 结点必须是红色或者黑色。
    2. 根节点必须是黑色。
    3. 叶节点(NIL)必须是黑色(NIL节点无数据,是空节点)。
    4. 红色结点不能连续。
    5. 从任一节点出发到其每个叶子节点的路径,黑色节点的数量必须相等。

    二、旋转变色规则

    已知插入根节点涂为黑色,其他节点都是涂红色;如果插入结点的父节点为黑色,就不需要进行旋转变色调整,其他情况都需要根据实际选择合适的处理策略进行调整,使其符合红黑树性质。最开始调整的时候是将插入结点作为当前节点。

    红黑树元素插入旋转变色规则
     实际情况处理策略
    第一种当前节点的父节点是红色,且其祖父节点的另一个子节点(叔叔节点)也是红色,祖父节点不是根节点。

    (1)将父节点和叔叔节点设为黑色。

    (2)将祖父节点设为红色。

    (3)将祖父节点作为新的当前节点。

    第二种当前节点的父节点是红色,叔叔节点也是红色,且当前节点在最边上(即每行最左边或最右边的节点),祖父节点是根节点。

    (1)将根节点作为新的当前节点,以根节点为支点进行左旋(插入的是右孩子)或者右旋(左孩子)。

    (2)旋转后将新的根节点变黑色,其他节点根据需要变色,只要保证不出现红红连续节点即可。

    (3)判断性质5是否已满足,不满足则以当前节点为支点进行一次左旋或右旋,旋转后依旧要保证不出现红红连续节点,否则进行变色。

    第三种其他所有情况,前提是当前节点的父节点是红色。

    (1)将父节点作为新的当前节点。

    (2)以新的当前节点为支点进行左旋(插入的是右孩子)或者右旋(左孩子)。

     

    更多相关内容
  • 最简单的Java红黑树变色、旋转与自平衡原理。红黑树的定义性质与原理,红黑树自平衡的原子操作,权威最简单红黑树的新增操作。
  • 红黑树的五个规则是什么? 节点是红色或黑色的; 根节点是黑色的; 每个叶子节点都是黑色的空节点(NIL节点); 每个红色节点的两个子节点都是黑色的(从每个叶子到根的所有路径上不可能有两个连续的红色节点); ...

    红黑树理解 (一) 从2-3树到红黑树
    红黑树理解(二)插入过程图解
    红黑树理解(三)变色
    红黑树理解(四)左旋
    红黑树理解(五)右旋

    什么情况下,节点需要变色?

    插入新的节点后,新的红黑树不再满足原先的5个规则,需要对原来的树进行调整。调整的措施有变色和旋转。多数情况下,既要变色,又要旋转。少数情况是只需要变色就能平衡的。

    变色过程举例

    这里举一个,只需要变色,就能使红黑树平衡的例子。并不意味着,只通过变色,就能够使红黑树平衡。
    当前节点的父节点和叔节点都是红色, 如下图:

    新节点默认是红色(如果默认为黑色,直接就违反规则5了),插入后,4和5都是红色,不满足规则四。如下图:

    进行变色操作,5和7变黑色,6变红色。如下图,当然根节点6还是不符合规则2。

    将根节点也改为黑色。如下图,红黑树再次平衡。

    连续插入5,10,15,20会怎么样?

    在15插入时,会有一次左旋,左旋比较复杂,后面文章会分析。继续插入20时,只需要变色,就能完成自平衡。如下图:
    在这里插入图片描述

    红黑树,超强动静图详解,简单易懂

    红黑树的原理 (插入+ 删除) 案例分析

    展开全文
  • 红黑树变色规则

    千次阅读 2021-10-24 15:05:25
    红黑树变色规则

    什么是红黑树

    我们平时说的平衡二叉查找树一般指的是AVL树,在AVL树中,任一节点对应的两棵子树的最大高度差为1,因此它也被称为高度平衡树。红黑树也是自平衡的二叉查找树,红黑树由自己的性质约束,通过变色和旋转保持相对平衡的结构。与AVL树相比,条件没那么苛刻,插入和删除数据时会用较少的时间,查询数据时也不会用慢太多。

    红黑树性质

    性质1. 结点是红色或黑色。

    性质2. 根结点是黑色。

    性质3. 所有叶子都是黑色。(叶子是NIL结点)

    性质4. 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)

    性质5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。

    这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。

    是性质4导致路径上不能有两个连续的红色结点确保了这个结果。最短的可能路径都是黑色结点,最长的可能路径有交替的红色和黑色结点。因为根据性质5所有最长的路径都有相同数目的黑色结点,这就表明了没有路径能多于任何其他路径的两倍长。

    示例

      在线创建红黑树的网站:Red/Black Tree Visualization

    展开全文
  • 红黑树变色与旋转

    2021-03-12 16:24:10
    红黑树是自平衡的二叉查找树,所以了解红黑树之前我们需要先了解什么是二叉查找树。 二叉查找树 1.某节点的左子树节点值仅包含小于该节点的值 2.某节点的右子树节点值仅包含大于该节点的值 3.左右子树也...
            红黑树是自平衡的二叉查找树,所以了解红黑树之前我们需要先了解什么是二叉查找树。
     

    二叉查找树

     
         1.某节点的左子树节点值仅包含小于该节点的值
         2.某节点的右子树节点值仅包含大于该节点的值
         3.左右子树也必须是二叉查找树
     
              这样的数据结构的好处就在于,当我查询10这个节点时,10>9,查看右孩子13,10<13,查看左孩子11,10<11,查看左孩子10,发现10正是要查找的节点,大大提交查询效率,这种方式是二分查找的思想,查询所需的最大次数等同于二叉查找树的高度。
     

    二叉查找树的局限性

     
          当我们插入7,6,5,4,3时,我们会发现树结构是这样的。
             这样我们会发现也符合二叉树的结构,但是这样线性的结构会导致我们的查找性能大打折扣,所以我们需要解决二叉树多次插入新节点而导致的不平衡,红黑树就出现了。
     

    红黑树

     
         红黑树是自平衡的二叉树,除了满足二叉树的特性外,还应具备以下特性:
          1.每个节点只有黑红两色
          2.树的根节点是黑色的
          3.没有两个相邻的红色节点,即一个红色节点它的父节点和子结点中不能存在红色节点
          4.从节点(包括根节点)到其任何后代的NULL节点(每个叶子节点下面有两个空节点)的路径上黑色节点的数量是相同的
     
         当我们插入新节点时,新节点是红色的,应为黑色节点会导致第4条规则更难去调节子树。当新节点的父节点是黑色时,就不需要去变化了,但是当是红色时,我们需要对其进行处理。
    主要两大操作:
         1.recolor(变色)
         2.rotation(旋转)
     
          假设我们新插入节点为X
           1.将新插入的节点标记为红色
           2.如果x是根节点,则标记为黑色
           3.如果x的parent不是黑色,同时x也不是root
           x的uncle(叔叔)颜色不同,操作也分为两种情况
     

    (1) 变色

     
            如果x的uncle(叔叔)是红色
    •   将x的parent和uncle标记为黑色
    •   将x的祖父标记为红色
    •  让x颜色与x祖父的颜色相同,然后重复不走2,3直到符合红黑树的特性       
     
                
            跟着上面的公式走:
    1.  将新插入的x节点标记为红色
    2. 发现x的父节点p是红色,违反了红黑树的第3条特性
    3. 发现x的uncleu同样是红色
    4. 将p和u标记为黑色
    5. 将x的祖父标记为红色,此时g就是新的x,继续重复2和3的步骤
    6. 发现g是根节点,标记为黑色,结束
     

    (2)旋转

     
            如果x的叔叔是黑色,要考虑四种情况,左左,左右,右左,右右,主要演示旋转,第4条特性先忽略。
          

            左左

            这种情况很简单,想象这是一根绳子,手提起 P 节点,然后变色即可
     

            左右

            左旋: 使 X 的父节点 P 被 X 取代,同时父节点 P 成为 X 的左孩子,然后再应用 左左情况
     

            右左

            右旋: 使 X 的父节点 P 被 X 取代,同时父节点 P 成为 X 的右孩子,然后再应用 右右情况
         

     

           右右

             与左左情况一样,想象成一根绳子
     
     

     

    案例:

         在一个二叉树插入节点21:
    首先,我们需要做的是变色,把节点25及其下方的节点变色:
    此时节点17和节点25是连续的两个红色节点,那么把节点17变成黑色节点?恐怕不合适。这样一来不但打破了规则4,而且根据规则2(根节点是黑色),也不可能把节点13变成红色节点。 变色已无法解决问题,我们可以用到旋转。
    由于根节点必须是黑色节点,所以需要变色,变色结果如下:
    这样就结束了吗?并没有。因为其中两条路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4,其他路径的黑色节点个数是3,不符合规则5。
     
    这时候我们需要把节点13看做X,节点8看做Y,像刚才的示意图那样进行右旋转
    最后根据规则来进行 变色
    如此一来,我们的红黑树变得重新符合规则。这一个例子的调整过程比较复杂,经历了如下步骤:
     
    变色 -> 左旋转 -> 变色 -> 右旋转 -> 变色
     
     

     
    展开全文
  • 什么是红黑树 红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定...
  • 红黑树 红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构, 1. 红黑树五大特性 所有节点非红即黑 根节点是黑色 所有节点非红即黑 根节点是黑色 页节点是黑色 不能有连续的...
  • 红黑树简介及左旋、右旋、变色

    千次阅读 2020-06-06 09:33:24
    红黑树简介及红黑树的左旋、右旋、变色
  • 红黑树是一种平衡二叉树,除了有二叉树的特点外,还有以下特点 节点是红色或者黑色 根节点是黑色 每个叶子的节点都是黑色的空节点(NULL) 每个红色节点的两个子节点都是黑色的。 从任意节点到其每个叶子的所有路径...
  • 红黑树的旋转与变色

    千次阅读 多人点赞 2019-01-27 22:55:23
    本文主要详解一下红黑树变色和旋转是如何工作的。 为什么红黑树要旋转和变色 这需要从红黑树的特效说起,红黑树发明之初就定义了以下5个特性,因为这几个特性,使得红黑树成为一个相对平衡的二叉树,也就...
  • 红黑树 概念 调整 变色 左旋和右旋 插入 插入情况分析 插入平衡总结 插入实例 删除 概述 删除情况分析 删除平衡总结 删除实例 参考链接 红黑树 概念 红黑树同样是解决二叉排序树不平衡的问题的,...
  • 树是数据结构中经典的结构之一,也是面试中常问的面试题之一,最近复习了一个红黑树的知识,做一下整理 文章目录 前言 一、pandas是什么? 二、使用步骤 1.引入库 2.读入数据 总结 前言 提示:这里...
  • 红黑树变换规则

    2020-08-04 21:17:56
    红黑树选择和颜色变换规则:所有插入点默认为红色 1. 变颜色情况:当前节点的父亲节点、叔叔节点均为红色 (1)把父亲节点设为黑色 (2)叔叔节点设为黑色 (3)祖父节点设为红色 (4)指针定位到祖父节点 2. ...
  • 红黑树是怎么实现的,看这篇真的就够了!
  • 红黑树的介绍2. 红黑树的变换规则3. 红黑树的Java实现(代码说明) 1. 红黑树的介绍 红黑树(Red-Black Tree 简称 R-B Tree),它是一种它一种特殊的二叉查找树。 红黑树是一种特殊的二叉搜索树,意味着它满足二叉查找树...
  • C++红黑树

    千次阅读 多人点赞 2022-03-26 18:13:48
    C++红黑树零、前言一、红黑树的概念及性质二、红黑树结点的定义三、红黑树的插入操作1、变色处理2、单旋+变色3、双旋+变色4、插入实现四、红黑树的验证五、红黑树的删除六、红黑树与**AVL**树的比较 零、前言 本...
  • 红黑树介绍

    2022-05-26 12:19:33
    红黑树一、红黑树的概念红黑树的性质红黑树节点的定义红黑树结构二、使用步骤1.引入库2.读入数据总结 一、红黑树的概念 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。...
  • 根据之前一节,描述了红黑树原理,这次把相关代码进行实现一下。 原理如下: https://blog.csdn.net/jenie/article/details/105871388 #include <stdio.h> #include <stdlib.h> #include <string.h...
  • 045:手写Java红黑树(下-变色左旋转)1 手写红黑树左旋转代码演示2 纯手写红黑树左旋转3 纯手写红黑树变色4 红黑树查询最大值与最小值 1 手写红黑树左旋转代码演示 课程内容: 1.完全纯手写红黑树变换颜色 2.10行...
  • 1、链表是什么时候转红黑树的? 1、在putVal()方法中如果链表长度大于阈值8;会进入到treeifyBin()方法中执行链表转红黑树操作; 2、HashMap中有个MIN_TREEIFY_CAPACITY变量 等于64,表示允许执行treeifyBin()链表...
  • 红黑树系列2——红黑树的删除(码字中,待发表) 红黑树系列3——红黑树的应用(码字中,待发表) 红黑树系列4——红黑树的代码实现(码代码中,待发表) 红黑树动态建立,删除网站(强强强强烈推荐,根据网页上...
  • 红黑树源码

    2018-10-12 21:26:28
    里面提供了红黑树算法的插入、删除等算法,还有内部的变色,左旋和右旋等算法。另外,里面还提供了冒泡排序、选择排序、插入排序、快速排序等排序算法
  • 步骤一:实现红黑树 定义红黑树节点类 package rbtree; import java.util.List; public class RBTreeNode<T> { private T val;//值 private boolean red;//是否为红 private RBTreeNode<T> ...
  • 狂肝半个月的学习笔记,最通俗易懂的红黑树讲解。带你快速掌握红黑树~
  • 2,当链表长度超过8时,ConcurrentHashMap会考虑把链表转为红黑树,但不一定真的转。 3,当链表长度超过8,但Node数组长度小于64时,优先考虑数组扩容。如果Node数组长度大于64,则把链表转为红黑树红黑树...
  • 硬核图解面试最怕的红黑树【建议反复摩擦】

    万次阅读 多人点赞 2020-11-05 09:26:58
    第三,算法导论中对于红黑树删除场景的阐述并不够具体,许多关键环节都用“经过一定的旋转和变色处理”来带过,不利于新手的学习。(我花了很长时间还原具体过程)。 考虑到部分读者有充足的精力研究以2-3-4树为...
  • 红黑树详解(下)(红黑树的删除操作)

    千次阅读 热门讨论 2022-01-22 00:01:26
    红黑树的删除和对应修复操作详解。
  • 本篇主要谈谈对红黑树的理解,大家都晓得JDK8中的hashmap底层是数组+链表+红黑树实现的,当面试官问你:为啥要加上红黑树实现呢?? 那我们首先从概念来了解一下: 一、什么是红黑树红黑树是一个接近平衡的二叉...
  • 红黑树的基本编写 红黑树的概念 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,707
精华内容 1,882
关键字:

红黑树变色