你开心就好
rb-tree实现-删除操作-原理
编辑
2025-04-11
记录知识
0

之前介绍了插入操作，简单总结就是如果平衡出现问题，先向上递归染色成父红叔黑状态，然后根据LL/RR/LR/RL进行右旋(针对g节点)/左旋(针对g节点)/左旋(针对p节点)+右旋(针对g节点)/右旋(针对p节点)+左旋(针对g节点)，最后互换颜色。
可以发现对于插入操作，我们可以一句话描述清楚所有场景，而对于删除操作，就比较复杂了。本文介绍删除操作的原理

删除操作

对于红黑树的删除操作，其全部操作分为两个阶段。

  • 删除阶段：找到前驱/后继节点替换待删除节点
  • 修复阶段：修复，平衡破坏，修复平衡

这两步操作宏观看还是非常好理解的，现在逐一介绍

删除阶段

对于删除阶段，主要有三种场景，我们先准备一下必要条件

  1. 如果被删除节点没有子节点，那么其就相当于有两个空黑节点 (一种情况)
  2. 如果被删除节点只有一个节点，那么被删除节点一定是黑色，被删除节点的子节点一定是红色 (两种情况)

因为被删除节点只有一个节点，而黑高必须平衡，所以子节点肯定得红色，又因为子节点必须是红色，所以被删除节点一定是黑色

  1. 如果被删除节点有两个节点，理论上按照有2的3次方共计8种组合方式，但是根据红黑树的规定，不能连续的红色，则只有按照前序遍历的 黑红红/红黑黑/黑红黑/黑黑红 (四种情况) 好了，根据上面的必要条件，一共七种情况，我们可以直接开始逐个根据所有场景分析了。
    本文将相关节点如下称呼
  • 待删除节点(s)
  • 待替换节点(r)
  • 父节点(p)
  • 兄弟节点(b)
  • 侄子节点(n)：兄弟节点的左/右孩子

没有子节点

这种情况下，就相当于有两个空节点，没有人替换它，我们不需要进行第一阶段删除，直接跳转到第二阶段修复去调整平衡

只有一个子节点

这里两种情况，子节点无论是左边还是右边，处理方式都是

  • 删除节点s，把其孩子节点作为节点r替换为节点s
  • 将节点s从红色染色成黑色

因为只有一个子节点的时候，由红色节点替代了被删除的黑色节点，此时修复黑高的方法就是将替代节点r的红色染成黑色即可。
故仅需两步，调整结束

有两个子节点

这种情况对应了其他四种场景，此时我们需要找到前驱节点或后继节点。也就是找到小于此节点的值或者大于此节点的值。所以关键点在于如何找到前驱节点和后继节点作为替代节点r。
而找前驱节点和后继节点的情况分别又是两种。

所以在 黑红红/红黑黑/黑红黑/黑黑红 四种场景下，我们根据红黑树的找前驱还是后继的方式可以两种实现(前驱/后继)来找节点r，在不同的实现下如何找前驱和后继还有两种方式，下面逐一介绍。

前驱方式

先介绍前驱方式寻找小于节点s的节点r

节点s的左子树没有右孩子

如果节点s的左子树没有右孩子，那么节点s的左孩子就是替代节点r，因为此时的节点r就是节点s的前驱节点。那么步骤如下：

  1. 我们将节点r(前驱节点)替换到节点s上
  2. 将节点r的颜色设置为节点s的颜色
  3. 然后将节点r的左孩子强制设置为黑色

我们需要注意的是，节点r的左孩子只能是红色。原因如下：

如果节点r的左孩子是黑色，那么又因为节点r是单节点，黑高肯定不平衡，图示如下。

首先我们假设一个红黑树如下：

image.png

此时我们删除节点3，让其处于如下状态

image.png

此时节点2相当于节点r，节点1相当于节点r的左孩子
我们算上叶子节点来计算黑高，可以发现，4-2 这里黑高是3，而其他的黑高是4。所以黑高一定不平衡。

那么我们可以得出结论，此情况下，节点r的左孩子一定是红色

根据上面的结论而言，我们的步骤相当于删除前驱节点r的颜色，然后再将节点r的左孩子强制设置为黑色。因为节点r的左孩子一定是红色，我们将节点r的左孩子强制染黑，黑高自然就是平衡了。

再补充一点，我们知道节点r的左孩子一定是红色，根据红色不能连续的规则，那么节点r一定就是黑色，在这种情况下，删除节点r的颜色就是删除了一个黑色，而为了维持黑高，将节点r的孩子染色成黑色，自然就平衡了。

节点s的左子树有右孩子

因为节点s的左子树有右孩子，我们就需要遍历其所有的右孩子，找到节点s的前驱节点。
值得注意的是，此时节点s的前驱节点r和节点s就没有相关性了。如我们步骤如下

  1. 遍历其所有的右孩子，找到节点s的前驱节点

  2. 我们将节点r(前驱节点)替换到节点s上

  3. 将节点r的颜色设置为节点s的颜色

  4. 然后将节点r的左孩子强制设置为黑色

上面三个步骤和节点s的左子树无右孩子的场景一致，但是我们在第三步将节点r的左孩子强制染黑了，而此时节点r和节点s没有相关性。所以黑高平衡破坏了之后，没办法直接修复，需要进行修复第二步骤。也就是如下

补充一下为什么没办法直接修复，因为节点s和节点r相差距离可能很远，我们是删掉了节点r，将节点r的内容放在节点s，实际上是因为节点r的丢失，导致从节点s的左边全部失去平衡。所以才有了第二步骤：修复

  1. 将关注节点变成节点r的左孩子，进行第二步骤修复

后继方式

后继方式和前驱方式逻辑一致，操作方式是镜像的

节点s的右子树没有左孩子

步骤如下：

  1. 我们将节点r(后继节点)替换到节点s上
  2. 将节点r的颜色设置为节点s的颜色
  3. 然后将节点r的右孩子强制设置为黑色

节点s的右子树有左孩子

我们需要遍历其所有的左孩子，找到节点s的前驱节点。
指的注意的是，此时节点s的前驱节点r和节点s就没有相关性了。如我们步骤如下

  1. 遍历其所有的左孩子，找到节点s的后继节点

  2. 我们将节点r(后继节点)替换到节点s上

  3. 将节点r的颜色设置为节点s的颜色

  4. 然后将节点r的右孩子强制设置为黑色

  5. 将关注节点变成节点r的右孩子，进行第二步骤修复

总结

至此，我们针对最后四种场景下，根据找前驱和后继的方式，将原节点进行了删除操作，如果前驱/后继节点和节点s没有相关性，则我们需要开展第二阶段修复操作，否则我们强制染色就能维持平衡。接下来开始介绍红黑树删除的第二阶段：修复操作

修复阶段

在删除阶段，实际上我们目的是先将目标节点s删除，然后通过找前驱/后继的方式找到替代节点r，将其替换目标节点s。(其本质是删除了节点r)
而在修复阶段，实际上我们就需要将无法修复的黑高来进行进一步修复。

在这里，我们将兄弟节点称之为节点b，将侄子节点称之为节点n(ln/rn)，将关注节点称之为节点s，记得关注节点注意和第一阶段区分。

在修复阶段，一共五种情况， 如下：

  1. 兄弟节点b是红色
  2. 兄弟节点b是黑色，且节点b的左右孩子(节点ln和rn)都是黑色(包含空节点)
  3. 兄弟节点b是黑色，且节点b的左孩子(节点ln)是红色，右孩子(节点rn)是黑色
  4. 兄弟节点b是黑色，且节点b的左孩子(节点ln)是黑色，右孩子(节点rn)是红色

这里还有一种情况：

  1. 兄弟节点b是黑色，且节点b的左右孩子(节点ln和rn)都是红色 这种情况和情况4合并

在上面五种情况下，我们还需要考虑关注节点s自身作为左孩子还是右孩子，这两种情况下，操作是镜像的。 为了方便介绍，我们先假设节点s自身作为父节点的左孩子。然后再介绍节点s自身作为父节点的右孩子的情况。

节点s是左孩子

假设节点s自身作为父节点的左孩子

兄弟节点b是红色

我们还是和插入的思想一致，如果兄弟节点b是红色的，我们要想办法让其变成黑色。

根据插入的时候的逻辑，假设是LL状态，那么我们对祖父节点右旋。这样自身插入节点向上一级。
同样的，如果是删除的时候，如果兄弟节点b是红色的，在L状态，为了让关注节点s向下降级，我们选择左旋。对谁左旋呢，当然是对父节点的左旋才能让关注节点s下降一级。

当左旋完成之后，节点s自降一级，我们知道节点b是红色的，那么节点b的任何子节点都一定是黑色的。那么左旋完成之后，兄弟节点肯定是黑色的。

这样我们就可以只讨论兄弟节点是黑色的情况了。

关于互换颜色，我们知道在插入操作后，会将兄弟节点b和父节点p颜色互换，同样删除也是。

对于左旋之后，我们需要的是将关注节点s的父节点p和祖父节点g的颜色互换

如果细心的可以了解到，对于颜色互换操作，其和插入操作是镜像的。 我列出如下

  • 对于插入操作，LL状态下，右旋后将兄弟节点和父节点的颜色互换
  • 对于删除操作，LL状态(左旋之后是LL状态)，左旋后将父节点和祖父节点颜色互换

也就是说，如果兄弟节点b是红色，那么再左旋完成之后，需要做一下颜色互换即可。互换的角色是

旋转后的 父节点和祖父节点。

总结一下，那么其步骤如下：

  1. 将父节点p左旋
  2. 将父节点p和祖父节点g交换颜色
  3. 继续检查关注节点(因为左旋会让关注节点降级，所以可以继续关注节点)

至此，我们分析了情况1，它的目的是将兄弟节点染黑，染黑的操作是通过左旋完成(因为兄弟节点的子节点一定是黑色)，自身下降一级。

兄弟节点b是黑色，节点b的子节点都是黑色(包含空节点)

我们知道进入修复阶段的时候，红黑树已经不平衡了，那么如果兄弟节点b是黑色，且其子节点都是黑色，那么我们计算其兄弟的黑高一定是2，而关注节点和子节点的黑高是1或2(自身是红则是1,自身是黑则是2)。所以
我们可以发现，在这个状态，就是黑高不平衡的状态。

我们找到了不平衡的关键点。我们的操作是强制让其染红，也就是

强制给兄弟节点染红

当兄弟节点染红之后，我们得到的结果是兄弟的黑高固定为1，往上递归，找到所有兄弟节点b是黑色且所有侄子节点(ln/rn)是黑色节点的情况，把兄弟节点染红，让其黑高固定为1.(兄弟节点红色,两个侄子节点都是黑色)

此时，我们将兄弟节点强制染红了，那么对父节点p，就需要强制染黑，否则出现了连续的红色节点

总结一下，那么本情况下，其步骤如下：

  1. 将兄弟节点b染色成红色
  2. 将父节点p染色成黑色
  3. 设置关注节点是父节点
  4. 向上递归

兄弟节点b是黑色，左侄子是红色，右侄子是黑色

我们现在剩下三种情况，如下

  1. 节点b是黑色，节点ln是红色，节点rn是黑色
  2. 节点b是黑色，节点ln是黑色，节点rn是红色
  3. 节点b是黑色，节点ln和rn都是红色

为了能够归一化这个问题，我们聚焦在一个点上：

  • 右侄子节点(rn是红色)

为了让节点rn是红色，我们需要对 本情况1:节点b是黑色，节点ln是红色，节点rn是黑色 进行调整，调整步骤如下：

  1. 兄弟节点b右旋
  2. 交换兄弟节点b和节点ln的颜色

这样之后，我们发现，上述剩下的三种情况就变成两种情况了，我们继续情况4和5

兄弟节点b是黑色，左侄子是黑色，右侄子是红色

对于此情况，考虑到我们是删除操作，我们找到替代节点是前驱节点，前驱节点是找到左孩子的最右节点，实际上对于关注节点s，其黑高是少于右边的(因为删除过节点)，为了修复黑高，此时应该做的是左旋

因为左旋会将左侄子节点rn给关注节点作为关注节点的右节点

故步骤如下

  1. 先左旋父节点p
  2. 将祖父节点g的颜色设置为父节点p的颜色
  3. 将父节点p的颜色设置为黑色
  4. 将叔叔节点u的颜色设置为黑色

此时调整结束

兄弟节点b是黑色，左右侄子都是红色

其实根据插入的定义，我们插入时必须要保证父红叔黑，所以插入节点后，不会出现非底层节点出现两个红色

那么出现左右侄子都是红色的情况是 左右侄子节点ln/rn都只含有空节点

此时，我们的行为可以和情况4合并，因为最后将 左侄子节点rn给关注节点作为关注节点的右节点 的时候，这个右节点是红色的，它本身就维持平衡了，调整结束。

节点s是右孩子

这种情况和节点s是左孩子的情况是镜像的，主要如下

兄弟节点b是红色

那么此时的步骤如下：

  1. 将父节点p右旋
  2. 将父节点p和祖父节点g交换颜色
  3. 继续检查关注节点(因为左旋会让关注节点降级，所以继续关注节点来修复)

兄弟节点b是黑色，节点b的子节点都是黑色(包含空节点)

那么此时的步骤如下

  1. 将兄弟节点b染色成红色
  2. 将父节点p染色成黑色
  3. 设置关注节点是父节点
  4. 向上递归

兄弟节点b是黑色，左侄子是黑色，右侄子是红色

那么此时的步骤如下

  1. 兄弟节点b左旋
  2. 交换兄弟节点b和节点ln的颜色

兄弟节点b是黑色，左侄子是红色，右侄子是黑色

那么此时的步骤如下

  1. 先右旋父节点p
  2. 将祖父节点g的颜色设置为父节点p的颜色
  3. 将父节点p的颜色设置为黑色
  4. 将叔叔节点u的颜色设置为黑色

兄弟节点b是黑色，左右侄子都是红色

此情况和 兄弟节点b是黑色，左侄子是红色，右侄子是黑色 情况一致，步骤也是一致

总结

红黑树的删除操作比较复杂，捋清楚需要认真思考很久，作为总结，删除操作简单来说如下，以节点s为左孩子为例：

  1. 先进行删除操作
  2. 删除操作中要找到替换节点，替换节点可能是左右子树，也可能是前驱节点，不同的红黑树实现，也可能使用后继节点实现
  3. 当平衡产生破坏的情况下，需要进行修复操作
  4. 修复操作的场景有五种，需要归一化处理
  5. 先让兄弟节点变黑，向下继续
  6. 如果兄弟节点和其子节点的黑高是2(都是黑的)，强行染色兄弟节点，让其黑高暂时是1
  7. 根据5和6的操作，兄弟节点肯定是黑色，黑高不会一定是2
  8. 此时想办法固定右侄子节点为红色
  9. 如果右侄子为黑色，则对兄弟节点右旋，并交换颜色，此时右侄子一定为红色(因为原左侄子的红色给了右侄子)
  10. 此时所有情况都归一化到：兄弟节点是黑，右侄子是红的情况
  11. 将父节点左旋，完成后，强行将祖父节点设置为父节点颜色，并强行将父节点和叔叔节点染黑
  12. 调整结束

在节点为右孩子时，我们左旋右旋的操作镜像即可。

本文将删除的原理彻底弄清楚了，为了方便理解，下一篇文章将所有的场景示例出来，加深印象。

阅读全文
rb-tree实现-插入操作-演示
编辑
2025-04-09
记录知识
0

根据文章《rb-tree实现-插入操作-原理》中的内容，我们归类了红黑树的所有操作，光有理论不行，本文演示插入的所有场景

基础红黑树

现在我们构建了一个10个元素的红黑树，其值从0-20，默认是偶数，其形状如下

image.png

父节点是黑色

我们测试插入节点1，则遍历到节点2上，往左边插入即可，如下

image.png

父节点和叔叔节点都是红色

为了让父节点和叔叔节点都是红色，需要先插入节点3，则情况如下

image.png

然后插入节点0，则此时会将叔叔和父亲染色为黑色，祖父设置为红色，然后向上递归，如下

image.png

父红叔黑LL状态

为了满足上述状态，需要先删掉节点0和3，其现状如下

image.png

此时我们添加节点0，它满足LL状态(祖父的左孩子是父，父的左孩子是节点0)

  • 第一步：将节点2(祖父节点)进行右旋，右旋后如下

image.png

  • 第二步：将节点0的兄弟节点2和父节点1的颜色互换，如下

image.png

父红叔黑RR状态

根据现在的情况，如果插入节点21，则满足父红叔黑RR状态(祖父的右孩子是父，父的右孩子是节点0)

  • 第一步：将节点18(祖父节点)进行左旋，左旋后如下

image.png

  • 第二步：将节点21的兄弟节点18和父节点20的颜色互换，如下

image.png

父红叔黑LR状态

为了满足父红叔黑LR状态，需要先删除节点21，则初始情况如下

image.png

此时如果我们插入节点19，则满足父红叔黑LR状态

  • 第一步：对节点18(父节点)进行左旋，关注节点变成节点18(父节点)。左旋后如下

image.png

  • 第二步：对节点20(节点18(此时的关注节点)的祖父节点)右旋。右旋后如下

image.png

  • 第三步：将节点18(此时的关注节点)的兄弟节点20和父节点19的颜色互换，如下

image.png

父红叔黑RL状态

为了满足父红叔黑RL状态，需要先删除节点0，2，再插入节点3，则初始情况如下

image.png

此时我们插入节点2，则满足父红叔黑RL状态

  • 第一步：对节点3(父节点)进行右旋，关注节点变成节点3(父节点)。右旋后如下

image.png

  • 第二步：对节点1(节点3(此时的关注节点)的祖父节点)左旋。左旋后如下

image.png

  • 第三步：将节点3(此时的关注节点)的兄弟节点1和父节点2的颜色互换，如下

image.png

总结

至此，对于红黑树的插入操作的所有情况已经图示介绍了。

阅读全文
rb-tree实现-插入操作-原理
编辑
2025-04-08
记录知识
0

在了解了红黑树的基本概念之后，接下来我们详细了解一下红黑树的插入操作的几种场景

默认规定

对于红黑树而言，需要默认遵守如下两个规定

  • 插入节点一定是红色(为了代码简化,默认黑色节点维持平衡)
  • 插入操作都是在叶子节点执行

所有场景

根据前面的规定的插入操作，我们可以将全部的插入场景列举出来，将确定的场景在后面标号为(n)

  • 将插入节点self称之为: (s)
  • 将父亲节点parent称之为: (p)
  • 将祖父节点grandfather称之为: (g)
  • 将叔叔节点uncle称之为: (u)

如下：

首先根据父节点颜色区分：

如果插入节点(s)的父节点(p)是黑色的 (1)

  • 那么插入节点(s)什么都不做，维持平衡

如果插入节点(s)的父节点(p)是红色的

  • 那么平衡破坏，需要进一步调整

然后根据叔叔节点的颜色区分

现在假设所有的插入操作，父节点(p)都是红色的，那么得出其祖父节点(g)一定是黑色的。 这时候叔叔节点(u)的颜色是红色或者黑色。 那么场景如下：

如果插入节点的叔叔节点(u)是红色的 (2)

  • 那么将关注节点的父节点(p)，叔叔节点(u)的颜色都设置为黑色
  • 然后将关注节点的祖父节点(g)设置为红色.（维持红黑树的颜色）
  • 将关注节点转换成祖父节点(g)
  • 进一步调整（迭代）

这里进一步调整后，我们可以知道从自身修改为祖父节点(g)之后，情况肯定会发生改变，所以代码需要迭代来确定下一步动作

如果插入节点的叔叔节点(u)是黑色的

  • 那么需要进一步调整

再根据插入节点相对于父节点(p)的位置区分

根据上面的统计，目前红黑树的已知现状为：
插入节点本身是红色的，插入节点的父节点(p)是红色的，插入节点的叔叔节点(u)是黑色的，插入节点的祖父节点(g)是黑色的，但是对于插入节点而言，不清楚其位于父节点(p)的左子树还是右子树

如果插入节点属于父节点(p)的右子树(3)

  • 那么将关注节点设置为父节点(p)
  • 然后将父节点(p)进行左旋。也就是让父节点(p)和父节点(p)的右节点断开，改变其父子关系
  • 此时因为关注节点为父节点(p),经过左旋之后，它是原插入节点的左子树，所以进入情况(4)

提前说明的是，这里假定父节点(p)是祖父节点(g)的左子树，所以在此情况下执行左旋

因为其父节点(p)左旋，则其右子树会变为原父节点(p)的父节点。
这里父节点(p)的右节点其实就是之前的关注节点，那么也就是将原关注节点作为原父节点(p)的父节点

因为此时我们的关注节点是父节点(p)，父节点(p)经过左旋之后，自然成为插入节点的左子树。所以我们直接按照情况(4)进行调整，如下介绍情况(4)

如果插入节点属于父节点的左子树(4)

  • 那么将关注节点的祖父节点(g)进行右旋
  • 调整完成之后，关注节点的父节点(p)和兄弟节点(b)颜色互换

提前说明的是，这里假定父节点(p)是祖父节点(g)的左子树，所以在此情况下执行右旋

这里值得注意的是，将祖父节点(g)进行右旋之后，则祖父节点(g)和父节点(p)会断开，从而形成祖父节点(g)会成为父节点(p)的右子树。然后我们知道祖父节点(g)是黑色，父节点(p)是红色，那么右旋之后，形成的关系按照前序遍历是
父节点(p)--->关注节点(s)--->祖父节点(g)
其颜色状态如下
红(p)--->红(s)--->黑(g)
明显不满足红黑树的规则，所以就需要将父节点(p)的颜色红色和祖父节点(g)的黑色颜色互换，则颜色改变后如下：
黑(p)--->红(s)--->红(g)

最后根据叔叔节点相对于祖父节点的位置区分

根据之前的解析，我们确定的信息如下：

  1. 插入节点(s)是红色的
  2. 父节点(p)是红色的
  3. 叔叔节点(u)是黑色的
  4. 祖父节点(g)是黑色的
  5. 插入节点(s)位于父节点(p)的左子树情况已解析
  6. 插入节点(s)位于父节点(p)的右子树情况已解析

这个时候，我们发现，父节点(p)位于祖父节点(g)的左右情况并没有分析。而上面的情况(3)和(4)都假定了插入节点(s)的父节点(p)位于祖父节点(g)的左子树。而实际上父节点(p)相对于祖父节点(g)的关系既可能是左子树，也可能是右子树。所以出现如下情况：

如果父节点(p)位于祖父节点(g)的左子树

  • 按照情况(3)和(4)执行

如果父节点(p)位于祖父节点(g)的左子树

  • 对于情况(3)，那么将关注节点设置为父节点(p)后，执行的是右旋
  • 对于情况(4)，那么将关注节点设置为祖父节点(g)后，执行的是左旋，然后再染色

简化记忆

根据上面所有场景的介绍，为了方便记忆，本章以容易记忆的方式将场景简单列举出来，简化的场景如下

  1. 对黑色节点的插入无需操作
  2. 对红色节点的插入，如果叔叔节点(u)都是红色，想办法染色成黑色
    具体染色操作是：将父节点(p)和叔叔节点(u)设置为黑色，并将祖父节点(g)设置为红色。然后将关注节点设置为祖父节点(g)，向上递归，这样就把所有红黑树的叔叔节点(u)染色为黑色了
  3. 根据父节点(p)相对于祖父节点(g)，插入节点(s)相对于父节点(p)的位置设置标号
    具体标号操作是：从上往下的视角，如果父节点(p)在祖父节点(g)左边则记作L，右边记作R，插入节点(s)和父节点(p)的关系同理
  4. 如果是LL，则对祖父节点(g)右旋
  5. 如果是RR，则对祖父节点(g)左旋
  6. 如果是LR，则对父节点(p)左旋后，再按照LL操作给祖父节点(g)右旋
  7. 如果是RL，则对父节点(p)右旋后，再按照RR操作给祖父节点(g)左旋

进一步简化记忆，可以如下：

  • 插入是红色才调整
  • 如果叔叔是红色，则先染色
  • 如果叔叔是黑色，根据LL/RR/LR/RL来执行操作

总结

至此，我们详细的了解了红黑树关于插入的操作步骤。并进一步的进行了简化记忆，接下来通过实验演示的方式验证所有的场景，下一个文章见

阅读全文
cache的策略
编辑
2025-04-07
记录知识
0

在学习cache的时候，有看到一系列的cache策略，这里汇总cache的策略，方便记忆

cache种类

cache分cacheable和non-cacheable
non-cacheable就是数据没有cache，而cacheable则又可以细分为如下

  • read/write allocate
  • write-back cacheable
  • write-through cacheable
  • shareability

分配策略

我们知道到数据miss的时候会分配cache line，那么主要有两种分配方式

  • read allocation

读取操作miss时，分配一个cache line，并记录cache

  • write allocation

写入操作miss时，分配一个cache line，并记录cache

回写策略

数据更新也就是write的时候，cache对回写的策略如下

  • write-back

写操作只会更新到cache，然后标记cache line为dirty，不会更新到内存中

image.png

  • write-through

写操作会直接更新到cache中，并同时更新到内存中

image.png

shareability

cache的共享属性分为 inner和outer，对于共享属性，我们可以这样记忆

  • 对于每个cluster内部，cache是inner shareable属性的
  • 两个cluster之间，cache是outer shareable属性的

image.png

cache可见性

  • PoU： point of unification : 对于inner share的cache，整个cluster内部看到的都是同一份cache的拷贝，不会出现两份不同的cache

image.png

  • PoC： point of coherency ： 对于系统的硬件，如GPU,DMA,多个Cluster的CPU之间，看到的都是同一份cache的拷贝，不会出现两份不同的cache

image.png

阅读全文
rb-tree实现-基本要素
编辑
2025-04-07
记录知识
0

操作系统在实现调度的时候会使用rb-tree，可见红黑树对于操作系统而言是多么的重要，本文首先介绍一下rb-tree的基本要素，后面连载逐渐了解rb-tree

树的结构

对于一个树的结构，默认的实现应该如下

struct Node {
	struct Node *left;		/* left element */
	struct Node *right;		/* right element */
}

这里通过Node就是树的节点，left是树的左子树，right是树的右子树

此时我们新增一个parent的Node指针，这样我们可以查找树里面的元素就无需每次从根节点遍历，结构体如下

struct Node {
	struct Node *left;		/* left element */
	struct Node *right;		/* right element */
	struct Node *parent;		/* parent element */
}

红黑树结构

对于红黑树，我们需要对Node添加颜色标识，可以如下

struct Node {
	struct Node *left;		/* left element */
	struct Node *right;		/* right element */
	struct Node *parent;	        /* parent element */
	int rbe_color;			/* node color */
}

这样，我们基本的红黑树的数据结构就完成了，接下来说明红黑树的特性

红黑树特性

对于红黑树的基本特性，主要是如下四点

  • 根节点是黑色的
  • 叶子节点都是黑色的，这里叶子节点包括最后一个null的节点（左右均null）
  • 相邻的节点之间不能出现连续的红色
  • 从根节点到叶子节点的黑色节点数目相等

这里以 Data Structure Visualizations 网站绘图

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

下面展示一个从1-10共10个元素的红黑树图

image.png

可以发现：

  • 对于特性1，节点6是黑色的
  • 对于特性2，图中我故意未画出
  • 对于特性3，节点1，3，9并不连续
  • 对于特性4，节点6，4，2和6，4，5和6，8，7和6，8，10的黑色节点数目相等

红黑树基本操作

红黑树的操作主要是左旋和右旋，以及插入和删除和搜索和染色，本文仅讨论左旋和右旋基本操作，插入，删除，搜索，染色等操作后面文章详细介绍。

关于左旋和右旋操作，是在红黑树出现不平衡的情况下，主动通过左旋和右旋调整使得整个红黑树平衡

左旋

对于左旋，就是红黑树不平衡的时候，对不平衡的节点向左旋转
假设有节点 x，y，a，b，r， 对其进行围绕x的左旋，如下所示

image.png

那么其具体步骤如下

  • 将节点x的right断开
  • 设置x的right节点y作为自己的parent
  • 如果节点y有left节点，则将y的left设置为x的right

简单理解就是，基于谁的节点左旋，就是将那个节点的右节点作为自己的父节点，然后重建叶子节点

为了更清楚的了解左旋步骤，我基于最上面10个元素的示例演示，先删除了节点8，则此时的树结构如下

image.png

此时因为节点7没有左孩子，但是节点10有左孩子，这并不平衡，所以需要对节点10进行右旋，右旋我们还没解释，简单理解就是将自己的左孩子作为自己的父亲。所以右旋后结构如下

0003a0705c258bbc994c8c5ade228be.png

我们发现节点9不平衡，其左孩子的黑色个数是3，而其他个数是4，所以将其染色如下

image.png

现在重点来了，但是此时节点7的左孩子是空，也就是其黑色节点数是3，我们需要左旋，步骤如下：

  1. 此时左旋的操作是针对节点7
  2. 对于7，断开节点9的连接，让其成为7的父节点
  3. 然后让节点7成为节点9的左孩子
  4. 因为节点9没有左孩子，所以无需进一步操作

这样左旋完成之后，结果如下

34d97652a4d4deb029511c5fce407b3.png

此时还是黑色个数不对，我们将节点10染色成黑色即可。如下

01ee401dbf545346968218c0ea4a8c4.png

右旋

我们介绍了左旋，对于右旋，就是红黑树不平衡的时候，对不平衡的节点向右旋转
假设有节点 x，y，a，b，r， 对齐进行围绕x的右旋，如下所示

image.png

那么其具体步骤如下

  • 将节点x的left断开
  • 设置x的left节点y作为自己的parent
  • 如果节点y有right节点，则将y的right设置为x的left

简单理解就是，基于谁的节点右旋，就是将那个节点的左节点作为自己的父节点，然后重建叶子节点

还是为了示例，还是基于上图删掉节点8之后的红黑树，此时我删除节点6，这里节点5会取代节点6，如下

image.png

此时红黑树在节点4上不平衡了，我们需要针对节点4进行右旋
步骤如下：

  1. 此时左旋的操作是针对节点4
  2. 对于4，断开节点2的连接，让其成为4的父节点
  3. 然后让节点4成为节点2的右孩子
  4. 因为节点2有右孩子，所以将节点2的右孩子给节点4作为节点4的左孩子

这样右旋完成之后，结果如下

image.png

最后发现节点2的黑色节点不平衡，个数不对，所以将节点1染色成黑色即可完成，如下

image.png

总结

本文作为红黑树介绍的开头，简单介绍了红黑树的基础，例如红黑树的特性，红黑树的左旋和右旋操作。

阅读全文