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

    一、红黑树性质

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

    二、旋转变色规则

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

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

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

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

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

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

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

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

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

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

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

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

     

    更多相关内容
  • 红黑树性质 1.不能有连在一起的红色节点 2. 每个红色节点的子节点都是黑色 3. 叶子结点都是黑色 为了满足这些性质,最后就形成AVL,但是其实并不严格,就是说它的左右子树深度差可以大于1,但是正是因为这样,而让...

    红黑树性质

    1.不能有连在一起的红色节点
    2. 每个红色节点的子节点都是黑色
    3. 叶子结点都是黑色
    4. 根节点都是黑色
    5. 对每个结点,从该结点到其后代叶结点的简单路径上,均包含相同数目的黑色结点。
    为了满足这些性质,最后就形成AVL,但是其实并不严格,就是说它的左右子树深度差可以大于1,但是正是因为这样,而让旋转更加容易,因此它的缓冲平衡机制就更容易实现。
    红黑树中最长支路的长度必然“不大于”最短者的2倍,所以不妨设Max者为H,Min者为h。则有:H<=2h。

    但是其实考虑到在操作过程中还有一部上色操作,其实跟普通的AVL操作复杂度差不多,但是又考虑到红黑树更容易实现,因此在C++中map和set底层还是用的红黑树

    红黑树的旋转

    红黑树一共又三种平衡机制: 变色,左旋,右旋;
    这里我们用一种很经典的例子来概括三种变换方式;
    我们有一颗这样的红黑树
    在这里插入图片描述
    然后我们想插入一个节点6,由于查找二叉树的性质,我们必须这样插入
    值得注意的是,插入的点都必须默认为红色
    在这里插入图片描述
    我们发现下方6,和7连续为红色,因此我们首先变色变成这样
    将连续的红色中的一个和其父结点的黑色颜色互换(如果是父结点就与其另外一个子节点换颜色)
    在这里插入图片描述
    然后我们发现还是又12和5连续为红色,这个时候如果再变色是不行的了,因为再变的话根节点就不是黑色了。
    由于连续的在左边,因此我们需要用到左旋,变成这样

    我们先不看19以及右边那一坨,先以只以左子树为准,我么不难发现就是以7及其下面对依托为旋转中心,这一坨不动,其余的向左向左旋转了一圈,旋转之后,12就变成了根,然后我们再讲7这一坨挂到左边就行。

    这就是所谓的左旋
    在这里插入图片描述
    左旋之后,我们发现,其实还是没有满足红黑树性质要求,又因为连续的在右边,这个时候我们需要右旋,变成这样
    其实也就是以13为旋转中心向右旋转一圈,这个时候,12就变成了根节点,然后我们再把13挂到右边一坨就行
    在这里插入图片描述
    然后我们发现其实还是没有满足要求,这个时候我们还需要再来一次颜色的改变变成这样
    这个时候就平衡了
    在这里插入图片描述
    以左旋为例

    enum Color
    {
    	R,
    	B,
    };
    struct BRNode
    {
    	int data;
    	int color = R;
    	BRNode *left;
    	BRNode *right;
    	BRNode *father;
    	BRNode(int data) : data(data){};
    };
    class BRtree
    {
    private:
    	static BRNode *root;
    public:
    	void myinsert(int innum, BRNode* node = root)//应该不允许重复
    	{
    		if (root->data < innum)
    		{
    			if (root->right == NULL)
    			{
    				root->right = new BRNode(innum);
    			}
    			else
    			{
    				myinsert(innum, root->right);
    			}
    		}
    		else
    		{
    			if (root->left == NULL)
    			{
    				root->left = new BRNode(innum);
    			}
    			else
    			{
    				myinsert(innum, root->left);
    			}
    		}
    	}
    	void leftRotate(BRNode* node)
    	{
    		if (node->father == NULL)
    		{
    			BRNode *E = root;
    			BRNode* S = E->right;
    			//将下面一坨移到左边
    			E-> right = S->left;
    			S->left->father = E;
    			//旋转节点
    			S->left = E;
    			E->father = S;
    			S->father = NULL;
    		}
    		else
    		{
    			if (node == node->father->left)//如果要旋转的中心是父结点的左子树根
    			{
    				node->father->left = node->right;//重新定义子树根节点
    			}
    			else
    			{
    				node->father->right = node->right;
    			}
    			//更改新的次根节点的父结点
    			node->right->father = node->father;
    			//更改本结点的父结点
    			node->father = node->right;
    			node->right->left = node;
    			//重新挂载旋转中心
    			node->right = node->right->left;
    			node->right->father = node;
    		}
    
    展开全文
  • 红黑树旋转规则

    千次阅读 2018-12-26 11:43:53
    红黑旋转规则 新插入的节点如果是外部孙子,则进行单旋转,如下图。 如果先插入的节点是内部孙子,则进行双旋转,如下图。 我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能...

    红黑旋转规则
    在插入节点过程中,从根节点开始往下寻找合适的插入位置,若寻找过程中存在节点的左右儿子都是红色节点,将该节点的右儿子换为黑色节点。
    红黑树插入的节点默认是红色的节点,如果父节点也是红色的节点,则进行旋转,按以下规则。
    新插入的节点如果是外部孙子,则进行单旋转,如下图。
    在这里插入图片描述
    如果先插入的节点是内部孙子,则进行双旋转,如下图。
    在这里插入图片描述

    我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能,我们增加了如下几点新功能,帮助你用它写博客:

    1. 全新的界面设计 ,将会带来全新的写作体验;
    2. 在创作中心设置你喜爱的代码高亮样式,Markdown 将代码片显示选择的高亮样式 进行展示;
    3. 增加了 图片拖拽 功能,你可以将本地的图片直接拖拽到编辑区域直接展示;
    4. 全新的 KaTeX数学公式 语法;
    5. 增加了支持甘特图的mermaid语法1 功能;
    6. 增加了 多屏幕编辑 Markdown文章功能;
    7. 增加了 焦点写作模式、预览模式、简洁写作模式、左右区域同步滚轮设置 等功能,功能按钮位于编辑区域与预览区域中间;
    8. 增加了 检查列表 功能。

    功能快捷键

    撤销:Ctrl/Command + Z
    重做:Ctrl/Command + Y
    加粗:Ctrl/Command + B
    斜体:Ctrl/Command + I
    标题:Ctrl/Command + Shift + H
    无序列表:Ctrl/Command + Shift + U
    有序列表:Ctrl/Command + Shift + O
    检查列表:Ctrl/Command + Shift + C
    插入代码:Ctrl/Command + Shift + K
    插入链接:Ctrl/Command + Shift + L
    插入图片:Ctrl/Command + Shift + G

    合理的创建标题,有助于目录的生成

    直接输入1次#,并按下space后,将生成1级标题。
    输入2次#,并按下space后,将生成2级标题。
    以此类推,我们支持6级标题。有助于使用TOC语法后生成一个完美的目录。

    如何改变文本的样式

    强调文本 强调文本

    加粗文本 加粗文本

    标记文本

    删除文本

    引用文本

    H2O is是液体。

    210 运算结果是 1024.

    插入链接与图片

    链接: link.

    图片: Alt

    带尺寸的图片: Alt

    居中的图片: Alt

    居中并且带尺寸的图片: Alt

    当然,我们为了让用户更加便捷,我们增加了图片拖拽功能。

    如何插入一段漂亮的代码片

    博客设置页面,选择一款你喜欢的代码片高亮样式,下面展示同样高亮的 代码片.

    // An highlighted block
    var foo = 'bar';
    

    生成一个适合你的列表

    • 项目
      • 项目
        • 项目
    1. 项目1
    2. 项目2
    3. 项目3
    • 计划任务
    • 完成任务

    创建一个表格

    一个简单的表格是这么创建的:

    项目Value
    电脑$1600
    手机$12
    导管$1

    设定内容居中、居左、居右

    使用:---------:居中
    使用:----------居左
    使用----------:居右

    第一列第二列第三列
    第一列文本居中第二列文本居右第三列文本居左

    SmartyPants

    SmartyPants将ASCII标点字符转换为“智能”印刷标点HTML实体。例如:

    TYPEASCIIHTML
    Single backticks'Isn't this fun?'‘Isn’t this fun?’
    Quotes"Isn't this fun?"“Isn’t this fun?”
    Dashes-- is en-dash, --- is em-dash– is en-dash, — is em-dash

    创建一个自定义列表

    Markdown
    Text-to- HTML conversion tool
    Authors
    John
    Luke

    如何创建一个注脚

    一个具有注脚的文本。2

    注释也是必不可少的

    Markdown将文本转换为 HTML

    KaTeX数学公式

    您可以使用渲染LaTeX数学表达式 KaTeX:

    Gamma公式展示 Γ ( n ) = ( n − 1 ) ! ∀ n ∈ N \Gamma(n) = (n-1)!\quad\forall n\in\mathbb N Γ(n)=(n1)!nN 是通过欧拉积分

    Γ ( z ) = ∫ 0 ∞ t z − 1 e − t d t &ThinSpace; . \Gamma(z) = \int_0^\infty t^{z-1}e^{-t}dt\,. Γ(z)=0tz1etdt.

    你可以找到更多关于的信息 LaTeX 数学表达式here.

    新的甘特图功能,丰富你的文章

    Mon 06 Mon 13 Mon 20 已完成 进行中 计划一 计划二 现有任务 Adding GANTT diagram functionality to mermaid
    • 关于 甘特图 语法,参考 这儿,

    UML 图表

    可以使用UML图表进行渲染。 Mermaid. 例如下面产生的一个序列图::

    张三 李四 王五 你好!李四, 最近怎么样? 你最近怎么样,王五? 我很好,谢谢! 我很好,谢谢! 李四想了很长时间, 文字太长了 不适合放在一行. 打量着王五... 很好... 王五, 你怎么样? 张三 李四 王五

    这将产生一个流程图。:

    链接
    长方形
    圆角长方形
    菱形
    • 关于 Mermaid 语法,参考 这儿,

    FLowchart流程图

    我们依旧会支持flowchart的流程图:

    Created with Raphaël 2.2.0 开始 我的操作 确认? 结束 yes no
    • 关于 Flowchart流程图 语法,参考 这儿.

    导出与导入

    导出

    如果你想尝试使用此编辑器, 你可以在此篇文章任意编辑。当你完成了一篇文章的写作, 在上方工具栏找到 文章导出 ,生成一个.md文件或者.html文件进行本地保存。

    导入

    如果你想加载一篇你写过的.md文件或者.html文件,在上方工具栏可以选择导入功能进行对应扩展名的文件导入,
    继续你的创作。


    1. mermaid语法说明 ↩︎

    2. 注脚的解释 ↩︎

    展开全文
  • 红黑树旋转

    2019-04-17 14:55:05
    当在含有n个关键字的红黑树上运行时,查找树操作插入和删除的时间为O(lgn)。 插入和删除操作对树做了修改可能破坏红黑树的性质,因此需要改变树中某些节点的颜色以及指针结构。 指针结构的修改是通过旋转完成的,这...

    当在含有n个关键字的红黑树上运行时,查找树操作插入和删除的时间为O(lgn)。
    插入和删除操作对树做了修改可能破坏红黑树的性质,因此需要改变树中某些节点的颜色以及指针结构。

    指针结构的修改是通过旋转完成的,这是一种能够保持二叉树性质的查找树局部操作。

    左旋和右旋:

    1. 左旋
      在这里插入图片描述
      对x进行左旋,意味着"将x变成一个左节点"。

    左旋的伪代码《算法导论》:参考上面的示意图和下面的伪代码,理解“红黑树T的节点x进行左旋”是如何进行的。

    LEFT-ROTATE(T, x)  
    01  y ← right[x]            // 前提:这里假设x的右孩子为y。下面开始正式操作
    02  right[x] ← left[y]      // 将 “y的左孩子” 设为 “x的右孩子”,即 将β设为x的右孩子
    03  p[left[y]] ← x          // 将 “x” 设为 “y的左孩子的父亲”,即 将β的父亲设为x
    04  p[y] ← p[x]             // 将 “x的父亲” 设为 “y的父亲”
    05  if p[x] = nil[T]       
    06  then root[T] ← y                 // 情况1:如果 “x的父亲” 是空节点,则将y设为根节点
    07  else if x = left[p[x]]  
    08            then left[p[x]] ← y    // 情况2:如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”
    09            else right[p[x]] ← y   // 情况3:(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”
    10  left[y] ← x             // 将 “x” 设为 “y的左孩子”
    11  p[x] ← y                // 将 “x的父节点” 设为 “y”
    

    理解左旋之后,看看下面一个更鲜明的例子。你可以先不看右边的结果,自己尝试一下。
    在这里插入图片描述

    1. 右旋
      在这里插入图片描述
      对y进行右旋,意味着"将x变成一个右节点"。

    右旋的伪代码《算法导论》:参考上面的示意图和下面的伪代码,理解“红黑树T的节点y进行右旋”是如何进行的。

    RIGHT-ROTATE(T, y)

    01  x ← left[y]             // 前提:这里假设y的左孩子为x。下面开始正式操作
    02  left[y] ← right[x]      // 将 “x的右孩子” 设为 “y的左孩子”,即 将β设为y的左孩子
    03  p[right[x]] ← y         // 将 “y” 设为 “x的右孩子的父亲”,即 将β的父亲设为y
    04  p[x] ← p[y]             // 将 “y的父亲” 设为 “x的父亲”
    05  if p[y] = nil[T]       
    06  then root[T] ← x                 // 情况1:如果 “y的父亲” 是空节点,则将x设为根节点
    07  else if y = right[p[y]]  
    08            then right[p[y]] ← x   // 情况2:如果 y是它父节点的右孩子,则将x设为“y的父节点的左孩子”
    09            else left[p[y]] ← x    // 情况3:(y是它父节点的左孩子) 将x设为“y的父节点的左孩子”
    10  right[x] ← y            // 将 “y” 设为 “x的右孩子”
    11  p[y] ← x                // 将 “y的父节点” 设为 “x”
    

    理解右旋之后,看看下面一个更鲜明的例子。你可以先不看右边的结果,自己尝试一下。
    在这里插入图片描述

    旋转总结:
    (01) 左旋 和 右旋 是相对的两个概念,原理类似。理解一个也就理解了另一个。
    (02) 下面谈谈如何区分 左旋 和 右旋。
    在实际应用中,若没有彻底理解 左旋 和 右旋,可能会将它们混淆。下面谈谈我对如何区分 左旋 和 右旋 的理解。

    1. 区分 左旋 和 右旋
      仔细观察上面"左旋"和"右旋"的示意图。我们能清晰的发现,它们是对称的。无论是左旋还是右旋,被旋转的树,在旋转前是二叉查找树,并且旋转之后仍然是一颗二叉查找树。
      在这里插入图片描述

    左旋示例图(以x为节点进行左旋):

                                   z
       x                          /                  
      / \      --(左旋)-->       x
     y   z                      /
                               y
    

    对x进行左旋,意味着,将“x的右孩子”设为“x的父亲节点”;即,将 x变成了一个左节点(x成了为z的左孩子)!。 因此,左旋中的“左”,意味着“被旋转的节点将变成一个左节点”。

    注:红黑树是当时看算法导论的时候收集的笔记可能是某些博客的合集,不做商用,如果侵权联系我哈。
    红黑树性质:https://blog.csdn.net/wodemale/article/details/89355443

    展开全文
  • 红黑树 红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求: - 性质1. 节点是红色或黑色。 - 性质2. 根节点是黑色。 ...
  • 红黑树的左旋和右旋比较费解,网上很多资料说的很复杂,这里我用望文生义的思维来解释左旋和右旋。可能对搜索资料的网友有帮助。 二叉查找树的定义 二叉查找树是一棵空树,或者是具有下列性质的二叉树:1、若左...
  • 什么是红黑树 红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定...
  • 红黑树-1 介绍与旋转

    2020-09-20 23:07:33
    红黑树是基于二叉树的一种非常重要的数据结构,它在二叉树的基础上加上了一下五点的限制,这也是红黑树的...红黑树存在左旋和右旋两种,在插入节点和删除节点的时候需要进行旋转来调整红黑树使其始终满足上面介绍的五条
  • 红黑树旋转

    2021-01-05 23:07:07
    如果对红黑树还不了解的,建议看上一篇博客。 https://blog.csdn.net/weixin_37909391/article/details/112252930 首先回顾以下红黑树的性质: 结点必须是红色或者黑色。 根节点必须是黑色。 叶节点(NIL)必须是...
  • 一、在理解红黑树之前,先看一些二叉查找树 二叉查找树特性:左字数上所有的节点的值都小于或等于他的根节点上的值 右子树上所有节点的值均大于或等于他的根节点的值 左、右子树也跟别为平衡二叉树 举个...
  • 红黑树的变色与旋转

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

    千次阅读 多人点赞 2019-01-27 22:55:23
    本文主要详解一下红黑树的变色和旋转是如何工作的。 为什么红黑树旋转和变色 这需要从红黑树的特效说起,红黑树发明之初就定义了以下5个特性,因为这几个特性,使得红黑树成为一个相对平衡的二叉树,也就...
  • 红黑树其实是由2-3树演变来的,如果想要理解红黑树,可以先看看2-3树 2-3树插入逻辑: 先找插入结点,若结点有空(即2-结点),则直接插入。如结点没空(即3-结点),则插入使其临时容纳这个元素,然后分裂此结点,把...
  • 它放弃了高度平衡的特性而只追求部分平衡,这种特性降低了插入、删除时对树旋转的要求,从而提升了树的整体性能。 而其他平衡树比如AVL树虽然查找性能为性能是O(logn),但是为了维护其平衡特性,可能要在插入、删除...
  • 红黑树旋转原理和模拟实现 我们了解到AVL树虽然效率很高,但是它是通过多次的旋转才到达一个绝对的平衡,旋转的消耗其实也很大。因此开始引入近似平衡的一棵树----红黑树(RBTree)。红黑树每一个节点不是红色的...
  • 红黑树属于二叉搜索树,但是每个节点增加了一个存颜色的位,它的规则是: 1.根节点为黑色。 2.不能有连续的两个红节点,所以如果一个节点的颜色为红,那么它的子节点若不为空则一定为红。 3.每条路径上黑节点数量...
  • 红黑树-“旋转”实现自平衡概念理解(动图演示) 红黑树(Red-Black Tree),又称“R-B树”,属于“二叉查找树”的一种,但它比较特殊,能够实现树结点的“自平衡”特性,但这种平衡只是近似的,不是绝对平衡。而这一...
  • 有了前面的基础和原理的支持,我们就能更加容易的理解红黑树各种旋转以及染色等操作,而不用再去死记硬背。话不多说开整~ 1. 红黑树的定义 每个节点要么是红色要么是黑色 根节点是黑色 所有的叶子节点都是黑色。 ...
  • 红黑树的介绍2. 红黑树的变换规则3. 红黑树的Java实现(代码说明) 1. 红黑树的介绍 红黑树(Red-Black Tree 简称 R-B Tree),它是一种它一种特殊的二叉查找树。 红黑树是一种特殊的二叉搜索树,意味着它满足二叉查找树...
  • 红黑树是一棵二叉搜索树,每个节点有一个标志位表示颜色,该颜色可以是红(RED)或黑(BLACK)。通过对任何一条从根到叶子的简单路径上各点的颜色进行约束,就能确保没有一条路径会比其他路径长出2倍,因而是近似于平衡...
  • 红黑树( 图解 + 秒懂 + 史上最全)

    千次阅读 2022-05-28 13:29:11
    增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。 AVL树的特性 AVL树本质上还是一棵二叉搜索树,它有以下特性: 特性1: 对于任何一颗子树的root根结点而言,它的左子树任何节点的key一定比root小,而右...
  • 红黑树简介及左旋、右旋、变色

    千次阅读 2020-06-06 09:33:24
    红黑树简介及红黑树的左旋、右旋、变色
  • 红黑树增加旋转两次:插入的是红节点: 红黑树要求从根节点到叶子所有叶子节点上经过的黑色节点个数是相同的,因此如果插入的节点着色为黑色,那必然有可能导致某条路径上的黑色节点数量大于其他路径上的黑色节点...
  • 在HashMap中,我觉得最难的应该是红黑树了吧,我结合代码和画图软件研究了两天,终于总结出规律,现在分享给大家 一、红黑树的特点 下面是红黑树的5条性质,现在大家要对这些性质有印象,后面我会结合图
  • ES6深拷贝重写红黑树旋转 灵感来源:在学习红黑树旋转方法的时候,我们写的旋转绝大部分都是以浅拷贝的方式来实现的,这样指针的指向的逻辑对初学者来说可能有些混乱,于是我尝试着用深拷贝的方法实现了一下红黑树的...
  • 之前就听说过红黑树的大名,是一种非常复杂的数据结构,但是一直没有去了解。最近了解了一下,所以写了这篇文章记录一下,以便于以后复习。 红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中...
  • 红黑树可以实现自平衡,主要依靠于它的旋转和变色的特性 //红黑树节点 typedef struct RBTreeNode { unsigned char color; Type key; struct RBTreeNode* left; struct RBTreeNode* right; struct RBTreeNode* ...
  • 最后,通过旋转和重新着色等方法来修正该树,使之重新成为一颗红黑树。详细描述如下: 第一步: 将红黑树当作一颗二叉查找树,将节点插入。 红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉...
  • 最简单的Java红黑树的变色、旋转与自平衡原理。红黑树的定义性质与原理,红黑树自平衡的原子操作,权威最简单红黑树的新增操作。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,032
精华内容 8,812
关键字:

红黑树旋转

友情链接: Atividade 3.rar