之后我们将来实现map与set的封装！！！ 红黑树的平衡性质使其在数据库系统中也得到了广泛的应用，特别是在实现索引结构时。...2.2 ❤️红黑树的插入函数 整体框架 现在我们来进行红黑树核心函数的实现，在这个插入函数中，会深刻体会到红黑树的抽象程度，也会大大加强代码能力！！！...} 寻找到合适的位置可以进行插入了，这里要进行一个思考：新插入的节点是什么颜色？？？...我们来分类讨论一下： 新插入黑色节点：如果我们新插入一个黑色节点，那么毋庸置疑会违反规则4 ：对于任意一个节点，从该节点到其所有后代叶子节点的简单路径上，必须包含相同数目的黑色节点。...是有可能违反的： 如果父节点是黑色，插入一个红色节点刚刚好，没有破坏红黑树的规则！！！ 如果父节点是红色，插入一个红色节点就违反了规则3。
1.当前节点存入上一节点和下一节点的引用（双向链表） 2.当前节点存入多个下一节点的引用（树） 我们把一个节点中存入多个下一节点的数据结构称为树，首节点称为根节点，如图： ?...树：每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。...二叉树 上图是树这种数据结构的定义，我们比较长用到的二叉树有是怎么样的呢？如图： ? 二叉树：是每个结点最多有两个子树的树结构。...在不知元素位置的时候，也是不能加快访问速度的，这还是一种无序的状态，需要访问元素还是需要遍历一次才可以找到。...= root && x.parent.color == RED) { //当X的父节点为黑时，满足红黑树性质 if (parentOf(x) == leftOf(parentOf
，先找到合适的位置，然后插入新节点，当节点插入后，需要对颜色进行判断，看看是否需要进行调整 插入流程： 判断根是否为空，如果为空，则进行第一次插入，成功后返回 true 找到合适的位置进行插入，如果待插入的值比当前节点值大...黑色，在返回 true 前统一设置即可 2.4、左单旋 + 染色 单旋：右右、左左，此时在 右半区，所以当 叔叔 不存在或者为 黑色 且节点位于 父亲 的 右边 时，可以通过 左单旋 降低高度 如果在左半区...所以不同区域的抽象图有不同的情况，必须确保能符合红黑树的性质 2.5、右左双旋 + 染色 双旋：右左、左右，此时在 右半区，所以当 叔叔 不存在或者为 黑色 且节点位于 父亲 的 左边 时，可以通过 右左双旋...逻辑与 AVL 树一致，这里额外分享一个 DeBug 技巧： 当 随机插入 数据出错时，可以借助文件读写操作，将出错的数据保存下来，然后再次输入，反复进行调试，即可找出 Bug 因为是 随机插入 时出现的问题...孩子不一定存在，但父亲一定存在（当前节点为 红色 的情况下） 所以当节点为 红色 时，判断父亲是否为黑色，如果不是，则非法！
步骤2：找到祖父节点 g 和叔叔节点 u 我们首先通过 p 找到它的父节点 g，以及 g 的另一个子节点（p 的兄弟节点）u，即叔叔节点。...抽象图 情况2：p为红，u为空或不存在，单旋+变色 在红黑树的插入过程中，情况2 涉及的是当新插入的节点 c 和它的父节点 p 都是红色，而 p 的兄弟节点 u（叔叔节点）不存在或是黑色的情况。...步骤2：找到祖父节点 g 和叔叔节点 u 首先找到 p 的父节点 g（祖父节点）和 p 的兄弟节点 u（叔叔节点）。根据 p 在 g 的左侧还是右侧，分为两种处理情况。...抽象图 情况3：双旋+变色 在红黑树的插入过程中，当新插入的节点 c 和其父节点 p 都是红色，而 p 的兄弟节点 u（叔叔节点）不存在或是黑色时，若 c 和 p 处于特定位置关系，无法通过单次旋转解决平衡问题...步骤2：找到祖父节点 g 和叔叔节点 u 首先通过 p 找到其父节点 g，并找到 p 的兄弟节点 u，即 p 的叔叔节点。由于 u 为黑色或不存在，需要进行旋转和变色。
一般来说，当人们谈论以太坊时，他们指的是网络的主要公共无许可实例（版本）。但是，像比特币一样，您可以采用以太坊软件，稍微修改它，并创建未连接到主要公共网络的专用网络。...ETH一代的未来变化 当Ethereum从工作证明（包括Ghost发行规则）移动到股权证明作为块添加机制时，发行时会发生什么情况尚未真正确定。...当一个块被开采时，获胜的矿工将把块发布到网络的其他部分，其他计算机将验证他们得到了相同的结果，然后将块添加到他们自己的区块链中。这就是以太坊区块链的状态如何得到更新。...当更多块创建得更快时，“块冲突”的速度就会增加 - 即几乎同时可以创建多个有效块，但其中只有一个可以将其加入主链。另一个“失败”，其中的数据不被视为主分类账的一部分，即使这些交易在技术上是有效的。...这实现了两件重要的事情： 尽管创建非主链块的机会很高（区块创建的高速度导致更多的叔叔与孤儿），但它激励矿工挖矿， 它通过承认创建叔叔块的能量来增加区块链的安全性 Gas和Gas价格 当您激活智能合约时，
答：当该路径所有节点都是黑色节点时，该路径最短 (2) 从最短路径的情况能推断出最长路径应该长什么样？...答：当该路径黑红相间时，该路径最长 举例 当每条路径上的黑色节点数为3时 ❁ 当所有节点为黑色 时，该路径长为3 ❁ 当该路径黑红相间时，该路径长为6 所以红黑树满足： 最长路径的节点个数...“叔叔”这个角色，叔叔就是自己的父亲的兄弟，也就是自己爷爷的另一个儿子，“叔叔”将会是插入操作的重要部分。...插入原则 ❁ 保证目前子树的所有路径的黑色节点数不变，否则和插入黑色节点没区别（将影响所有路径） ❁ 根节点必须是黑色 插入的准备工作 在插入前，我们首先要做的就是找到 ❁ 插入位置 ❁ 插入位置的父亲...左左情况 根据叔叔不存在且为“左左”的情况，我们同样可以知道，叔叔存在时的“左左”情况可以写为： 1、右旋grandfather 2、更改颜色（parent变黑色，cur和grandfather
的父节点G变成红色 这样,G的所有子系节点就得到了统一,从而整棵树得到了统一 可能G和这个G节点的父节点会违反第二条规则,只需要重复调用即可 叔叔节点为黑色: 如果向已有的红黑树中插入新节点N时,根据第一条规则...红父和右黑子的旋转,会使红父的左子节点的子系增加一个黑色节点 黑父和右红子的旋转,会使红子的右节点减少一个黑色节点 当父节点P和子节点N都为红色,且N的叔节点Q为黑色时: 旋转节点P, N.但P...如果叔叔节点的颜色为红色,直接变色 如果叔叔节点的颜色为黑色,需要先选择,再交换颜色 删除节点 删除节点首先要确定待删除节点有几个孩子: 如果有两个孩子,不能直接删除节点.先找到该节点的前驱,即左子树中最大的节点...: 如果被删除的节点有两个子节点 这个节点 将与子节点的值进行交换 这个交换在交换后的子节点不多于一个子节点时停止 可以对二叉树的删除节点操作进行修改: 只要被删除节点有子节点 该节点的值就要和子节点的值进行交换...,当插入新节点时,新节点的size值为1 途中经历的的所有指针指向的节点 ,size值都增加1 while (temp = root -> value < val ?
然后还要保证了传输过去的比特流是正确的，有纠错功能。定义了如何让格式化数据以进行传输，以及如何让控制对物理介质的访问。这一层通常还提供错误检测和纠正，以确保数据的可靠传输。...小明连忙找到资料，上面写着：“ 发正确的发比特流数据到另一台计算机了，但是当我发大量数据时候，可能需要好长时间，例如一个视频格式的，网络会中断好多次（事实上，即使有了物理层和数据链路层，网络还是经常中断...那就是通过IP协议来完成的（复用，多个进程都可以把信息通过传输层到IP层，再传输到另外一台计算机中）。 那如何找到另外一台计算机的进程（pid）？...（三次握手和四次挥手时说的SYN或ACK会消耗一个序号就是指该序号） 3.确认号（占4字节）：因为一次数据传输会分成多个报文段，接收方接收完一次报文段后如果要发送确认（有可能不用确认，因为是接收完发送窗口的报文段才确认的...发送窗口有两部分组成，已发送的报文段 和 能够发送但未发送的报文段（等待已发送报文段全部接收完发回来的确认就可以发送了） 当收到确认后发送窗口会向右移动到7位置，作为窗口的起始位置。
然后还要保证了传输过去的比特流是正确的，有纠错功能。定义了如何让格式化数据以进行传输，以及如何让控制对物理介质的访问。这一层通常还提供错误检测和纠正，以确保数据的可靠传输。...小明连忙找到资料，上面写着：“ 发正确的发比特流数据到另一台计算机了，但是当我发大量数据时候，可能需要好长时间，例如一个视频格式的，网络会中断好多次（事实上，即使有了物理层和数据链路层，网络还是经常中断...应为进程是资源分配的基本单位，计算机之间的信息传输也只是一台计算机的进程传输到另外一台计算机的进程中 一台计算机如何找到另外一台计算机呢，那就是通过IP协议来完成的（复用，多个进程都可以把信息通过传输层到...（三次握手和四次挥手时说的SYN或ACK会消耗一个序号就是指该序号） 三、确认号（占4字节）：因为一次数据传输会分成多个报文段，接收方接收完一次报文段后如果要发送确认（有可能不用确认，因为是接收完发送窗口的报文段才确认的...，当接收缓存慢了才回把接收到的数据交付到接收应用进程中，而如果发送端把报文的PSH设为1，接收方接收到该报文会立即交付到应用的进程中 九、复位RST：两个作用，1、当RST=1时，表示TCP连接中出现严重差错
当搜索“赵丽颖和冯绍峰啥时候结婚的”，百度会对搜索内容先进行分词，解析出了“赵丽颖、冯绍峰、结婚、时候”，然后通过查询索引找到了最符合查询条件的网页A，然后把结果返回给了搜索者。...很自然会想到的问题：当搜索“赵丽颖”的时候，网页A和网页B都满足条件，返回给搜索者的时候，A和B的顺序如何决定的？这篇文章张叔叔就带大家来揭开它的神秘面纱。...给大家介绍一种主流的计算方法:TF-IDF，英文全称term frequency–inverse document frequency，千万不要被这复杂的词汇吓到，有叔叔在，一切且可理解。...其实和叔叔之前的文章《当妈妈在淘宝的时候，都发生了什么？》...百度一下背后的故事有一定的难度喔，希望大家能够仔细思考，下次再百度的时候你就明白这背后的逻辑了！ 【张叔叔科普数据】 2018年6月，百度APP日活超过1.5亿，这个只是每天使用百度APP的用户量。
int cmp; // 用来寻找待插入节点的父节点 Entry parent; // 根据是否有comparator使用不同的分支 Comparator的情况有以下几种处理方式： 插入的元素如果是根节点，则直接涂成黑色即可，不用平衡； 插入的元素的父节点如果为黑色，不需要平衡； 插入的元素的父节点如果为红色，则违背了特性4，需要平衡...，平衡时又分成下面三种情况： （如果父节点是祖父节点的左节点） 情况 策略 1）父节点为红色，叔叔节点也为红色 （1）将父节点设为黑色；（2）将叔叔节点设为黑色；（3）将祖父节点设为红色；（4）将祖父节点设为新的当前节点...，进入下一次循环判断； 2）父节点为红色，叔叔节点为黑色，且当前节点是其父节点的右节点 （1）将父节点作为新的当前节点；（2）以新当节点为支点进行左旋，进入情况3）； 3）父节点为红色，叔叔节点为黑色，...且当前节点是其父节点的左节点 （1）将父节点作为新的当前节点；（2）以新当节点为支点进行右旋； 3）父节点为红色，叔叔节点为黑色，且当前节点是其父节点的右节点 （1）将父节点设为黑色；（2）将祖父节点设为红色
然后还要保证了传输过去的比特流是正确的，有纠错功能。定义了如何让格式化数据以进行传输，以及如何让控制对物理介质的访问。这一层通常还提供错误检测和纠正，以确保数据的可靠传输。...小明连忙找到资料，上面写着：“ 发正确的发比特流数据到另一台计算机了，但是当我发大量数据时候，可能需要好长时间，例如一个视频格式的，网络会中断好多次（事实上，即使有了物理层和数据链路层，网络还是经常中断...那就是通过IP协议来完成的（复用，多个进程都可以把信息通过传输层到IP层，再传输到另外一台计算机中）。 那如何找到另外一台计算机的进程（pid）？...（三次握手和四次挥手时说的SYN或ACK会消耗一个序号就是指该序号） 3.确认号（占4字节）：因为一次数据传输会分成多个报文段，接收方接收完一次报文段后如果要发送确认（有可能不用确认，因为是接收完发送窗口的报文段才确认的...当接收缓存慢了才回把接收到的数据交付到接收应用进程中，而如果发送端把报文的PSH设为1，接收方接收到该报文会立即交付到应用的进程中 9.复位RST：两个作用，1、当RST=1时，表示TCP连接中出现严重差错
当插入一个新的节点时，可能会破坏这种平衡性，那么红-黑树是如何修正的呢？ 2. 平衡性的修正 红-黑树主要通过三种方式对平衡进行修正，改变节点颜色、左旋和右旋。这看起来有点抽象，我们分别来介绍它们。...由于红-黑树是二叉搜索树的改进，所以插入操作的前半工作时相同的，即先找到待插入的位置，再将节点插入，先来看看插入的前半段代码： /*********************** 向红黑树中插入节点 **...于这种情况，我们要做的操作有：将当前节点(4)的父节点(5)和叔叔节点(8)涂黑，将祖父节点(7)涂红，变成上右图所示的情况。...对于情况2：插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的右子节点。我们要做的操作有：将当前节点(7)的父节点(2)作为新的节点，以新的当前节点为支点做左旋操作。...于情况3：插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点。我们要做的操作有：将当前节点的父节点(7)涂黑，将祖父节点(11)涂红，在祖父节点为支点做右旋操作。
黑色平衡是当我们将红黑树中的红色节点全部删除时，此时你会发现都平衡因子为小于1的。红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父节点）作为父节点。...7节点时 3.删除的节点有左右子树，找到删除节点的后继，然后将后继替换为删除节点，再删除需要删除的节点，这里的后继就是指删除节点右子树中最小的叶子节点值，当然我们也可以用左子树中最大的叶子节点值。...基于上述的删除特点有可以我们将二叉树转换为如下场景 当为场景2的时候，也就是删除节点只有一个子节点时，将删除节点替换为子节点，然后此时我们要删除的就是替换后的子节点，此时子节点还有左右子节点，那么我们又可以转换为场景...3的情况，如果只有一个节点相当于有是场景2的情况，然后一直自顶向下进行处理 当为场景3的时候，也就是删除节点有左右子节点时，找到删除节点的后继，然后替换掉要删除的节点，然后再删除替换后重复的那个节点...下面图中在删除有左右子节点的数据时，实际上找的并不是后继，而是我们前面提到的找左子树中最大的叶子节点，后面涉及两个删除带有左右子树节点情况时，所有动图都是按照这种模式。 ?
从根节点往下，根据二叉排序树的特点，找到新的节点应该插入的合适位置 // 2....当找到合适位置后，根据键值大小，决定它要作为它爸爸的左孩子还是右孩子 // 3....如果它的爸爸是黑色，不进行变色也不用旋转，直接返回 // 3. 如果他的爸爸是红色，而且肯定是有个循环逐步向上一直进行到根 while (x !...super K> cpr = comparator; // 我们构造一个TreeMap时可以传入一个自己实现的比较器，作为节点直接比较大小的规则 // 下面这个if和else...= null); } // 当找到合适位置后，parent中保存的是它的爸爸 MyTreeMap.Entry e = new MyTreeMap.Entry
这里没有电锯男 没有三角头怪物 也没有可爱的护士姐姐 只有一位头戴面具、手持斧头的光头胖叔叔 是不是觉得更兴奋了呢？ 这只是一款逃生类游戏啦！ 所以嘛 操作什么的 很简单喽！...拿着一只核能手电筒 去寻找你的安全出口吧 不要担心满地血浆 或者突然冒出奇怪的东西 这里只有一间间的小黑屋 每个屋子都有四扇门 做一个四选一的选择题 很简单吧 不过 有的门是锁着的 你就需要寻找钥匙啦...要是数量稀少 使用前请三思 当然啦 我们的光头胖叔叔也不是摆设哦 他会一直尾随着你的 所以 注意听脚步声 不要一边放歌一边玩哦 其实这款游戏还是挺贴心的 许多门边会贴着照片和小纸条 小纸条会给你一些温馨小提示...它会提示你正确的道路 也会细心地提醒你回头看看 照片是需要我们收集的重要道具 至于照片内容嘛 丰富多彩 有胖叔叔的自拍 也有门钥匙的特写照…… 你问我这有何意义 可能是给你逃生路上增加些乐趣吧 说了这么多...其实你也免不了死很多次啦 只是希望大家记住 当你打开一扇门 然后发现是胖叔叔时 不要慌 请心平气和的接受死亡 《RUN ROOMS》 第一人称逃生类恐怖游戏 最后温馨提醒 路痴请珍惜生命 远离这款游戏
红黑树，是一种自平衡的二叉查找树，它的性质比较复杂，但却非常重要，常用于C++中的STL库中的set、map等容器。红黑树的节点有两种颜色：红色（red）和黑色（black）。...这里我将当前结点的父亲（parent）的兄弟称为叔叔结点。 示例： 当我们新增一个结点时，默认新节点的颜色为RED，如果它的父亲结点是黑色的，则不需要做任何调整，直接插入成功！...当父亲结点是红色的时候，则与新增结点一起，会构成连续的红色结点，此时需要调整。 调整规则主要看uncle叔叔结点。 情况1： 父亲是爷爷的左，cur结点是父亲的左。...也许我们会遇到各种问题，好不容易跑通代码后，我们缺无法判断自己实现的红黑树是否正确，是否符合红黑树的规则。...nullptr } 三、结语： 看完本篇文章，我们不难知道，对于插入操作，无论是红黑树还是avl树，要维持对应的“平衡”，会进行沿路径的更新，其中涉及大量的旋转操作，而红黑树较于avl树那种严格的高度差在
插入步骤： 根据二叉搜索树的特性，找到新的节点合适的插入位置，也就是找到它的爸爸 决定将它作为它爸爸的左孩子还是右孩子(还是二叉搜树的特点) 把它标记为红色节点，因为它可能破坏了原红黑树的规则，所以需要变色...它一上来就是一个while循环，我们可以看到，它的条件里面就说明了除非它的爸爸是红色节点，所以，当它的爸爸是黑色节点的时候，会直接跳过，也就是说，我们的结论是正确的。...，是的，就是我们刚才看的fixAfterInsertion()一进来的那个while 另外，我们再想一下，当【51】和【49】都是红色时，是不是【43】和【49】这两个红的会一起变成黑的，当【45】和【...56】都是红色时，【56】和【68】这两个红的是不是会一起变成黑的？...其实也不难，第一种情况是插入红色，它爸爸是黑色，不破坏黑色节点树也没有连续红色，所以不用操作；第二种是插入红色，它爸爸是红色，而且它叔叔也是红色，所以它爸爸和它叔叔会一起变色，它爷爷会随之变色，所以能够达到同一层红色统一变黑色
首先我们先找到了大小关系合适的节点；然后如果我们插入的是黑色就破坏了黑色相等的规则，故插入的节点一定是红色，那么就可以推出它的父亲是红或者黑，如果是黑色那么可以直接成功插入了，但是如果是红色的话，爷爷节点一定是黑色...2.2.3.1 左单旋+变色（叔叔节点为黑色或者不存在）： 注：这里是由于要进行不同方向的那四种旋转我们才分孩子连接的是父亲的左还是右。 我们首先要想什么时候会左单旋然后变色呢？...肯定不可能，下面看一张图解释一下： 但是当叔叔不存在时候（虽然也是黑色）但是它只能是新插入的节点而不是向上调整才会出现： 这样我们就明白了把。...因此接下来如果要进行左旋故父亲肯定是爷爷的右，孩子也是父亲的右（无论叔叔存在还是存在为黑都一样当黑色处理进行左旋。）...因为当叔叔是其他的时候就会旋转，此时最顶上就是黑色，而旋转带来的改变犹如上调，故可以类似于做到了上调操作。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
云直播
