红黑树概念

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

红黑树概念

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是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模板网!

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

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

相关文章

  • 【数据结构】红黑树

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

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

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

    2023年04月09日
    浏览(46)
  • 【数据结构-树】红黑树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

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

    现在JAVASE中HashMap中底层源码是由数组+链表+红黑树进行设计的,然后很多地方也是用到红黑树,这里单独对红黑树数据结构进行简单的介绍。 目录 红黑树概念 红黑树的性质 自平衡规则 代码   红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可

    2024年02月01日
    浏览(40)
  • 数据结构入门-11-红黑树

    史上最负盛名的平衡二叉树–红黑树,但其实就是2-3树的一种实现 也是BST,每一个节点都有颜色 性质 看 后面推导出来的结论 2-3树 :和红黑树是等价的 满足BST的基本性质,但不是一种二叉树 有两种节点: 2-3 绝对平衡:根节点到叶子节点 一定相同 2.3.1 如何维护绝对平衡

    2023年04月17日
    浏览(41)
  • 手写红黑树【数据结构】

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

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

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

    2024年02月09日
    浏览(50)
  • 数据结构之红黑树

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

    2024年01月17日
    浏览(43)
  • 数据结构--红黑树详解

    红黑树(Red Black Tree)是一种自平衡二叉查找树。它是在 1972 年由 Rudolf Bayer 发明的,当时被称为平衡二叉 B 树(symmetric binary B-trees)。后来,在 1978 年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。 由于其自平衡的特性,保证了最坏情形下在 O(logn) 时间复杂度内完

    2024年02月22日
    浏览(46)
  • 数据结构——红黑树详解

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

    2024年04月13日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包