红黑树概念

这篇具有很好参考价值的文章主要介绍了红黑树概念。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

红黑树概念

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
红黑树概念,算法,数据结构

红黑树的性质

  1. 最长路径做多是最短路径的2倍
  2. 每个结点不是红色就是黑色
  3. 根节点是黑色的
  4. 如果一个节点是红色的,则它的两个孩子结点是黑色的【没有2个连续的红色节点】
  5. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均 包含相同数目的黑色结点
  6. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

红黑树节点的定义

class RBTreeNode{
	RBTreeNode left = null;
	RBTreeNode right = null;
	RBTreeNode parent = null;
	COLOR color = RED; // 节点的颜色
	int val;
	public RBTreeNode(int val){
		this.val = val;
	}
}

红黑树的插入

红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:

  1. 按照二叉搜索的树规则插入新节点
  2. 检测新节点插入后,红黑树的性质是否造到破坏
    因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连在一起的红色节点,此时需要对红黑树分情况来讨论:
    约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点
    情况一: cur为红,p为红,g为黑,u存在且为红

红黑树概念,算法,数据结构
cur和p均为红,违反了性质三,此处能否将p直接改为黑?
解决方式:将p,u改为黑,g改为红,然后把g当成cur,继续向上调整。
情况二: cur为红,p为红,g为黑,u不存在/u为黑

红黑树概念,算法,数据结构
p为g的左孩子,cur为p的左孩子,则进行右单旋转;相反,
p为g的右孩子,cur为p的右孩子,则进行左单旋转
p、g变色–p变黑,g变红

情况三: cur为红,p为红,g为黑,u不存在/u为黑
红黑树概念,算法,数据结构
p为g的左孩子,cur为p的右孩子,则针对p做左单旋转;相反,
p为g的右孩子,cur为p的左孩子,则针对p做右单旋转
则转换成了情况2文章来源地址https://www.toymoban.com/news/detail-602663.html

public boolean insert(int val){
// ...


	// 新节点插入后,如果parent节点的颜色是红色,一定违反性质三
	while(null != parent && COLOR.RED == parent.color){
		RBTreeNode grandFather = parent.parent;
		if(parent == grandFather.left){
			RBTreeNode uncle = grandFather.right;
		if(null != uncle && uncle.color == COLOR.RED){
		// 情况一:叔叔节点存在且为红,
		// 解决方式:将叔叔和双亲节点改为黑色,祖父节点改为红色
		// 如果祖父的双亲节点的颜色是红色,需要继续往上调整
			parent.color = COLOR.BLACK;
			uncle.color = COLOR.BLACK;
			grandFather.color = COLOR.RED;
			cur = grandFather;
			parent = cur.parent;
		}else{
		// 情况二和情况三
		// 叔叔节点不存在 || 叔叔节点存在,但是颜色是黑色
			if(cur == parent.right){
				// 情况三
				rotateLeft(parent);
				RBTreeNode temp = parent;
				parent = cur;
				cur = temp;
			}
			// 情况二
			rotateRight(grandFather);
			parent.color = COLOR.BLACK;
			grandFather.color = COLOR.RED;
		}}else{

		}
	}
	// 在上述循环更新期间,可能会将根节点给成红色而违反性质1,因此此处必须将根节点改为黑色
	root.color = COLOR.BLACK;
	return true;
}

到了这里,关于红黑树概念的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构 | 红黑树

    节点的左边比节点的值小,右边比节点的值大。 节点要么是 红色 ,要么是 黑色 根节点 是黑色 叶子节点都是黑色的空节点 红黑树中红色节点的子节点都是黑色 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点 在添加或者删除节点的时候,如果不满足这些性质会

    2024年01月21日
    浏览(41)
  • 数据结构——红黑树

    目录 概念 性质 结点的定义  插入 调整 当p是g的左孩子时 当p为g的右孩子时 插入完整代码 红黑树的检测 红黑树完整代码(包括测试数据)   红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是RED或BLACK。 通过对任何一条从根到叶子的路径

    2023年04月09日
    浏览(42)
  • [数据结构]-红黑树

    前言 作者 : 小蜗牛向前冲 名言: 我可以接受失败,但我不能接受放弃   如果觉的博主的文章还不错的话,还请 点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录 一、红黑树的基本知识  1、红黑树的概念 2、性质  二、红黑树的模拟实

    2024年02月04日
    浏览(44)
  • 【数据结构】红黑树

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 在学习AVL树的时候,我们知道,当修改AVL树的结构(插入,删除)时,会通过旋转来保证平衡因子不超过1,所以频繁的修改结构会导致效率低下,今天我们学习的红黑树就完美解

    2023年04月17日
    浏览(46)
  • 数据结构——红黑树详解

    红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树 确保没有一条路径会比其他路径长出两倍 ,因而是接近平衡的。(说它是接近平衡因为它并没有像AVL树的

    2024年04月13日
    浏览(38)
  • C++数据结构--红黑树

    红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路 径会比其他路径长出俩倍,因而是接近平衡的。如图所示: 每个结点不是红色就是黑色。

    2024年02月09日
    浏览(46)
  • 数据结构篇十:红黑树

      红黑树是解决单支树问题的另一种解决方法,它相比较AVL树减少了调整的次数,AVL是一格绝对平衡的树,而红黑树只要求最长路径不超过最短路径的二倍,相比较大大减少了调整次数。在实际中更多的也是使用红黑树,就比如后面的map和set,我们就是以红黑树进行封装的

    2024年03月12日
    浏览(49)
  • 数据结构之红黑树

    数据结构可视化演示链接,也就是图片演示的网址 数据结构之AVL Tree 数据结构之B树和B+树 数据结构之Radix和Trie 数据结构之二叉搜索树 红黑树是一种二叉查找树,但在每个结点上增加了一个存储位表示结点的颜色,可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个

    2024年01月17日
    浏览(42)
  • 手写红黑树【数据结构】

    2024-3-30 10:52:57 昨天晚上B站看到的视频 00:00~01:00 以下内容源自《【数据结构】》 仅供学习交流使用 禁止其他平台发布时删除以下此话 本文首次发布于CSDN平台 作者是CSDN@日星月云 博客主页是https://jsss-1.blog.csdn.net 禁止其他平台发布时删除以上此话 我红黑树那么牛,你们凭什

    2024年04月25日
    浏览(33)
  • 【数据结构】红黑树详解

    目录 前言: 红黑树的概念: 红黑树的性质: 红黑树节点的定义: 红黑树的插入: 情况1:cur为红,p为红,g为黑,u存在且为红  情况2:cur为红,p为红,g为黑,u不存在或者u为黑(p和cur都在其父亲节点同一侧) 情况3:cur为红,p为红,g为黑,u不存在或者u为黑(p和cur在其父

    2024年04月14日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包