目录一、红黑树的概念二、红黑树的操作1、红黑树的定义2、红黑树的插入2.1、cur为红，p为红，g为黑，u存在且为红2.2、cur为红，p为红，g为黑，u不存在/u存在且为黑2.3、cur为红，p为红，g为黑，u不存在/u存在且为黑（变种）3、红黑树的验证3.1、检测一 3.2、检测二三、红黑树的性能四、附完整代码 本篇文章以前一篇文章《AVL树》为基础，在阅读本篇文章之前，需要具备该文章中所讲解的旋转等知识。一、红黑树的概念 红黑树，是一种二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一
红黑树的实现会比AVL简单-.-文章目录判断是否是AVL树一、红黑树二、红黑树的实现总结判断是否是AVL树上一篇文章我们详细介绍了AVL树并且实现了AVL树，这篇文章我们将在前言中引入判断是否是AVL树的方法，然后我们就进入红黑树的实现，如果是能自己实现AVL树的同学那么实现起红黑树就会非常简单了，下面我们介绍一下如何判断AVL树：首先AVL树本质是根据平衡因子的调节来实现平衡，所以我们可以根据平衡因子来判断，代码如下：boolIsBalance() { return_IsBalance(_root); }int_Height(Node*root) { if(root==null
前言相信很多人初学者听到了红黑树后心中不免有些心慌，那你看到了这篇文章后相信会有所收获，我其实刚开始也是对红黑树抱着一种害怕甚至是恐惧，但是在老师的帮助下也终于慢慢的不在恐惧了，你想知道为什么的话就继续往下看吧。（注意本篇博客只讲解了红黑树的插入，没有讲解红黑树的删除，删除比插入还要难一些，为了更好的阅读体验，就不再讲解了）1红黑树的概念红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。如果说AVL树是大佬设计的话，那么红黑树就是大
平衡的关键书接前文。在前文《二叉搜索树的本质》中我们提到，二叉搜索树在实践中有个很大的问题：树倾斜。按如下顺序插入数据会让二叉搜索树退化成普通链表，进而相关操作的时间复杂度退化到O(n)：怎样让这棵树在写操作后仍然保持平衡呢？R教授一边呷着黑咖啡，一边盯着这棵“畸形”的二叉树发愣。“要怎样才能在添加新节点的时候不会破坏树的平衡性呢——或许应该这样问：添加新节点的过程是如何破坏树的平衡性的？”R教授紧锁双眉喃喃道。忽然，他两眼放光，好像发现了什么！“对！问题就出现在这：向下生长。”R教授发现，每次添加新节点，都会给现有的叶节点生成新的孩子节点，如此，每次添加一个新节点，都使得树的高度加1，最终变
引言北京时间：2023/5/17/22:19，不知道是以前学的不够扎实，还是很久没有学习相关知识，对有的知识可以说是遗忘了许多，以该篇博客有关知识为例，我发现我对迭代器和模板的有关知识的理解还不够透彻，不知道是对以前知识的遗忘，还是现在所学确实有难度，反正导致我很懵，希望当该篇博客写完，能让我的理解更上一层楼吧！并且今天是周三，没课，但是有些摆烂，因素很多，可能是前几天学习强度有一些大导致的，也可能是自我要求变高了，也可能是整个宿舍都去图书馆，独独我没去而感到一定的压力，当然也可能是最近的课程难度上升，不容易学进去，从而导致容易摆烂，反正各个因素都有，在此值得思索，该篇博客是一个过度，因为只要
现在JAVASE中HashMap中底层源码是由数组+链表+红黑树进行设计的，然后很多地方也是用到红黑树，这里单独对红黑树数据结构进行简单的介绍。目录红黑树概念红黑树的性质自平衡规则代码 红黑树概念红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。二叉查找树，也称有序二叉树（orderedbinarytree），或已排序二叉树（sortedbinarytree），是指一棵空树或者具有下列性质的二叉树：若任意节点的左子树不空，则左子树上所
我正在浏览JAVA中的TreeMap的源代码。根据JAVA文档:ARed-BlacktreebasedNavigableMapimplementation.Themapissortedaccordingtothenaturalorderingofitskeys,orbyaComparatorprovidedatmapcreationtime,dependingonwhichconstructorisused.Thisimplementationprovidesguaranteedlog(n)timecostforthecontainsKey,get,putandremoveoperat
我正在浏览JAVA中的TreeMap的源代码。根据JAVA文档:ARed-BlacktreebasedNavigableMapimplementation.Themapissortedaccordingtothenaturalorderingofitskeys,orbyaComparatorprovidedatmapcreationtime,dependingonwhichconstructorisused.Thisimplementationprovidesguaranteedlog(n)timecostforthecontainsKey,get,putandremoveoperat
文章目录1.红黑树概念2.红黑树性质3.结构定义关于默认节点为红/黑色的讨论4.insert情况1——uncle节点存在且为红色(gpc左斜形成一条直线)情况2——uncle节点不存在/存在且为黑色(gpc左斜形成直线右单旋)uncle节点不存在uncle节点存在并且为黑色情况3——uncle节点不存在/存在且为黑色(gpc形成左折线双旋)uncle节点不存在uncle节点存在并且为黑色情况1——uncle节点存在且为红色(gpc右斜形成一条直线)情况2——uncle节点不存在/存在且为黑色(gpc右斜形成直线左单旋)情况3——uncle节点不存在/存在且为黑色(gpc形成右折线双旋)5.判断
引言：北京时间：2023/5/12/20:30，今天周五，周五不摆烂从我做起，虽然刚睡醒，但是今天如果论学习时长，那可能是许久以来最长的一天，从早上6:40晨跑回来坐在凳子上，一坐久坐到了下午13:40，然后睡了10分钟去上了一节心理课，心理课结束去吃了个饭，回到宿舍16:20，帮同学下载了一个软件，可能是很久没下了，搞了半天才搞好，最终在17:10分进入学习状态，直到19:00左右，把自己目前手头上的任务搞定的差不多，然后洗了个澡，洗澡出来好像是19:08，最终调好闹钟，刚刚起床，在这个时间点，首先是我的舍友快从我没有的选修课上回来了，其次是我准备把博客给总结一下，该篇博客我们就来学习一下有
