数据结构 - 学习笔记 - 红黑树前传——234树

news/2023/5/28 6:54:53

数据结构 - 学习笔记 - 红黑树前传——234树

  • 简介
  • 结点类型
  • 与红黑树对应关系
  • 插入逻辑
    • 插入步骤演示
    • 2结点插入
    • 3结点插入（红黑树旋转）
      • 共对应6种红黑树情形
      • 有4种情形需要再平衡
    • 4结点插入（红黑树变色）
      • 234树转红黑树
      • 触发分裂
      • 有4种情形需要变色实现平衡
      • 递归调整颜色
  • 删除逻辑
    • 删除步骤演示
    • 234树删除结点
    • 2结点删除
    • 3结点删除
    • 4结点删除
  • 辅助脚本
  • 总结

简介

在学习红黑树前需要先了解234树。因为红黑树就是由234树演变出来的。
了解了234树才能明白红黑树颜色变化的底层逻辑。

  1. 明明是包含123个结点，为什么不叫123树而叫234树。因为树的特性就是分叉，结点的命名是按它的分叉能力来的。我理解为：n结点就是能分n个叉的结点。（这怎么感觉跟制动有异曲同工之妙啊。）
  2. 234树 就是 4阶B树。也就是允许结点最多有4个子结点的平衡多路查找树。
  3. 234树 是倒着长的。新元素插入到叶子，然后触发分裂向上提升元素成父级。

结点类型

结点结点内容子结点 s对应红黑树结点
2结点1元素个。
如：a		2个子结点或无子结点
( , a), (a, )		黑色a
3结点2元素个。
如：a,b		3个子结点或无子结点
( , a) , (a, b) , (b, )		父结点必需是黑色
黑色b—L→红色a
黑色a—R→红色b
4结点3元素个。
如：a,b,c		4个子结点或无子结点
( , a) , (a, b) , (b, c) , (c, )		红色a←L—黑色b—R→红色c

与红黑树对应关系

在这里插入图片描述

  1. 上图中没有画出具体的子结点 仅用虚线框标识了一下子结点的取值范围。
  2. 不难看出，只要将红黑树中的红结点向上一提，与父结点合并，就反推出了234树。
  3. 在平时分析红黑树时，可以直接在脑海里映射成234树来分析。这样变化，旋转操作就有据可依，而不是死记硬背了。

插入逻辑

  1. 新元素插入到叶子结点，如果触发分裂，再提取元素与上级合并。
  2. 如果上提后，父级也触发分裂，则循环此操作，直到根结点。
插入场景插入前插入值插入后结论
当前无结点空1[5]直接插入就完事了。
当前2结点[5]3[3, 5]2结点升级为3结点。
当前3结点[3, 5]7[3, 5, 7]3结点升级为4结点。
当前4结点[3, 5, 7]8[5]
[3, 7, 8]		4结点 插入新值后，出现5结点的临时情况。
触发分裂：2 上升与原本的父结点合并。
1. 原本没有父结点，直接作为父结点。
2. 原父为2结点，合并。父结点变成3结点。
3. 原父为3结点，合并。父结点变成4结点。
4. 原父为4结点，合并。递归触发分裂。

插入步骤演示

下图演示了234树的插入步骤，以及触发分裂的效果。
在这里插入图片描述

下图对应234树插入步骤，在右侧列出对应的红黑树。因为3结点转红黑树存在两种情况，所以按排列组合方式一一列出。
对照前文的与红黑树对应关系，可以看到黑红颜色背后的逻辑来源于234树。
在这里插入图片描述

2结点插入

2结点插入新值，直接升级为3结点，无需任何调整。
在这里插入图片描述

3结点插入（红黑树旋转）

3结点插入新值，直接升级为4结点，无需任何调整。
但在3结点对应的红黑树中，可能出现不平衡的情况。需要旋转调整实现平衡。

共对应6种红黑树情形

在这里插入图片描述

  1. 旋转方向的逻辑可以想象天平。左边重了往右挪（旋），右边重了往左挪（旋）。
  2. 从上图可以看到有3个位置能插入子结点。对应 6 种红黑树的情形。
  3. 其中有2种是平衡的，无需调整。剩下4种 需要再平衡。

有4种情形需要再平衡

虽然共有4种 情形，但其中 LR可以转为LL， RL可以转为RR。总之就是有拐弯的，最终也是转为一条直线，再处理。

  1. LL 右旋1次，实现平衡。
  2. RR 左旋1次，实现平衡。
  3. LR 左旋1次，转为 LL，重复 LL 的平衡操作。
  4. RL 右旋1次，转为 LL，重复 RR 的平衡操作。
    在这里插入图片描述

4结点插入（红黑树变色）

234树转红黑树

先简单的把 4结点 与 红黑树 对应关系，罗列出来。根据新结点插入的位置不同，对应的红黑树也有所差异：
在这里插入图片描述

对应上图的步骤序号。

  1. 原234树为 357.
  2. 插入新元素。将要触发分裂。
  3. 先分裂。然后找到目标位置，与原有的2结点 合并成为3结点
    3.1. 如果还有父结点，分裂出去的结点，与原父结点合并。
    3.2. 如果原来的父结点也是一个4结点，将递归触发分裂。
  4. 234树结点转红黑树结点。
    4.1. 所有 2结点 变为黑色。
    4.2. 3结点 展开，上黑下红。

触发分裂

单独分析一下触发分裂效果。

  1. 演示了从234树的角度来染色的逻辑（左）。
  2. 演示了从红黑树的角度来染色的公式（右）。
  3. 如果当前操作的只是一颗子树。比如结点2也是红色（需要旋转，对应RR公式），则需要继续处理，直至根。

在这里插入图片描述

有4种情形需要变色实现平衡

在这里插入图片描述

  1. 【234树】 插入新元素。将要触发分裂。
  2. 【234树】 先分裂。然后找到待插入的目标位置，与原有的2结点 合并成为3结点
  3. 【红黑树】 这是一个中间状态，为了便于观察才把它画出来。（3结点展开，但未调色，暂时还保持着不平衡的状态，便于观察）
  4. 【红黑树】 父结点、叔伯结点变成黑色，祖父结点变成红色。
    4.1. 父结点与祖父结点调换颜色：满足红结点子必黑的定义。同时对于插入新结点的这一路径来说黑结点数未发生变化。
    4.2. 叔伯结点变成黑色：祖父结点原本作为公共的黑结点，挪给左路后，右路就少了一个黑结点。因此 叔伯要站出来变黑维持平衡。
  5. 【红黑树】 最后祖父结点更新为当前结点。
    5.1. 判断曾祖是否为红色。如果是，则需要向上递归调整颜色，一直到根。
    5.2. 如果是根，直接染黑。

递归调整颜色

插入新结点 1 后递归触发变色。直到根结点为止。
在这里插入图片描述

删除逻辑

  1. 先删除。（作为一颗二叉树，删除结点）
  2. 再平衡。（作为一颗红黑树，调整颜色）

删除步骤演示

下图演示了234树的删除步骤，以及触发合并的效果。
同时，右则列表出对应的红黑树。
234树中删除结点，为满足特性（子结点数量），需要向父兄结点借元素。此过程可能会引发合并。下图中也用虚线框标出了借兵过程。
在这里插入图片描述

234树删除结点

234树删除结点时，根据被删除的结点所包含的子结点个数不同，共有3种场景：

结点子结点数删除操作
2结点0个子结点直接删除。
3结点1个子结点1. 删除当前结点。
2. 子结点顶上来。（还要染成黑色，维持平衡）
4结点2个子结点1. 找到前驱或后继结点。
2. 替换当前结点。
3. 再删除前驱或后继结点。

2结点删除

删除结点后，当前位置空出，红黑树失去平衡。需要向父兄结点借元素来补位。
在这里插入图片描述

3结点删除

删除一个元素，变成2结点。保持平衡。

  • 红结点：直接删除即可。
  • 黑结点：删除黑结点，红结点补位，并变成黑色。

在这里插入图片描述

  1. 原234树结点，蓝色 标出是要删除的目标。
  2. 转为对应的红黑树。
  3. 删除目标结点。
  4. 如果删的是父结点。子结点上移补位。
  5. 补上来的结点染成原父结点的颜色。如果是根结点 直接填充黑色。

4结点删除

删除一个元素，变成3结点。保持平衡。
4结点 的删除，如果忽略掉它的兄弟结点。本质上还是一个3结点的删除。
对应红黑树：

  • 红结点：直接删除即可。
  • 黑结点：删除黑结点，红结点补位，并变成黑色。

在这里插入图片描述

  1. 234树结点，蓝色 标出是要删除的目标。
  2. 转为对应的红黑树。
  3. 删除目标结点。
  4. 如果删的是父结点。子结点上移补位。
  5. 补上来的结点染成原父结点的颜色。如果是根结点 直接填充黑色。（虽然单看234树转过来的这个局部，父结点必定是黑色。但在一个完整红黑中，父结点有可能是红色）

辅助脚本

红黑树可视化演示

var sleep = (delaytime = 1000) => {return new Promise(resolve => setTimeout(resolve, delaytime))
}
async function delayDo(arr, callback = data=>console.log(`数据：${data}`), delaytime) {var len = arr.length;for (let i = 0; i <len  ; i++) {        await sleep(delaytime);callback(arr[i]);}
};
// 获取文本框
var [insertTxt, deleteTxt, findTxt] = [...document.querySelectorAll("#AlgorithmSpecificControls [type=Text]")];
// 获取按钮
var [insertBtn, deleteBtn, findBtn] = [...document.querySelectorAll("#AlgorithmSpecificControls [type=Button]")];
var process = {insert: function insert(v){	insertTxt.value = v; insertBtn.click();	},del: function del(v){ deleteTxt.value = v; deleteBtn.click(); },find: function find(v){ findTxt.value = v; findBtn.click(); }
}
// 遍历数组，间隔 n 秒处理一个元素。
function main(arr = [...Array(10).keys()], cb = v=>console.log(v), delaytime=200){delaytime = delaytime<200 ? 200 : delaytimedelayDo(arr, v => cb(v), delaytime);
}
// 插入元素，间隔 200 毫秒
main([...Array(20).keys()].map(v=>v+1), process.insert, 200);

总结

  1. 可以将红黑树看作是234树的一个具体实现。
  2. 一颗234树可以对应多个234树。（因为 3结点 对应 红黑树 时可以左倾，也可以右倾）

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.exyb.cn/news/show-4553851.html

如若内容造成侵权/违法违规/事实不符，请联系郑州代理记账网进行投诉反馈，一经查实，立即删除！

相关文章

求一元二次方程的根【C++】

求一元二次方程的根【C++】

哈哈哈这个就图一乐&#xff0c;各位看官要铭记&#xff0c;眼过千遍不如手过一遍 求一元二次方程axbxc0&#xff08;a≠0&#xff09;的根 求根公式哦一元二次方程的求根公式是什么&#xff1f;_百度知道 #include<iostream> #include<cmath> using namespace s…
阅读更多...
c语言怎样调用求根函数,编写函数求一元二次方程的根,并在main主函数中调用该函数 用c++编写...

c语言怎样调用求根函数,编写函数求一元二次方程的根,并在main主函数中调用该函数 用c++编写...

满意答案sIXzVDhc2014.01.10采纳率&#xff1a;58% 等级&#xff1a;12已帮助&#xff1a;7410人#include #include void b1 (){float l,s,k;int a,b,c,h;printf ("************这是求根方程****************\n");printf("\n");printf("输入a,b,c的…
阅读更多...
Solidity 中的数学（第 1 部分：数字）

Solidity 中的数学（第 1 部分：数字）

本文开启了一系列关于在 Solidity 中进行数学运算的文章。第一个要讨论的话题是&#xff1a;数字。 介绍 以太坊是一个可编程的区块链&#xff0c;其功能可以通过将称为智能合约的可执行代码片段发布到区块链本身来扩展。这将以太坊与第一代区块链区分开来&#xff0c;在第一代…
阅读更多...
WC2023游记

WC2023游记

今年&#xff0c;我势必打破铜牌魔咒 Day -?~? 虽然已年及高二&#xff0c;但WC的讲课还是没有听懂多少&#xff0c;这段时间&#xff0c;北师大还有一名E队来我校训练&#xff0c;我只能感慨&#xff1a;“如果一个选手比你强&#xff0c;还比你小&#xff0c;那你就再也打…
阅读更多...
计算机中顺序结构,2.逻辑结构（一）：顺序结构

计算机中顺序结构,2.逻辑结构（一）：顺序结构

今天我们开始学习计算机科学中的逻辑结构。逻辑结构有三种&#xff1a;顺序结构、循环结构、条件结构(分支结构)。顺序结构&#xff1a;计算机命令是有先后执行顺序的&#xff0c;执行完一条再执行下一条命令。这样才能保证计算机根据我们的命令一步步完成不同的、复杂的操作。…
阅读更多...
C语言基础——执行顺序

C语言基础——执行顺序

一.语句 在C语言中&#xff0c;程序的执行顺序是由语句组成的。程序的功能也是由执行语句实现的&#xff0c;一个语句执行一个功能&#xff0c;语句可以分为表达式语句与空语句。 1.表达式语句 表达式语句由表达式与分号组成。表达式是表达式语句的内容&#xff0c;分号是表…
阅读更多...
编程逻辑及思想

编程逻辑及思想

1、“!”,"not"(逻辑非)、“&&”,"and",(逻辑与)、“||”,"or"(逻辑或)是三种逻辑运算符。不同语言符号不同&#xff0c;但是逻辑一样。 2、顺序结构&#xff0c;分支结构&#xff0c;循环结构&#xff0c;是编程或算法的三种基本结构&a…
阅读更多...
计算机逻辑算法,算法逻辑

计算机逻辑算法,算法逻辑

算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤&#xff0c;或者看成按照要求设计好的有限的确切的计算序列&#xff0c;并且这样的步骤和序列可以解决一类问题。一般算法有顺序结构、选择结构、循环结构三种基本逻辑结构。中文名算法逻辑外文名Algorithm lo…
阅读更多...
顺序表的原理

顺序表的原理

1、顺序表 1&#xff0c;顺序表特点 线性表的逻辑顺序与物理顺序一致&#xff0c;数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。对顺序表中的所有表项&#xff0c;即可以进行顺序的访问&#xff0c;也可以随机的访问&#xff0c;也就是说&#xff0c; 　　 既…
阅读更多...
问题:编译策略之代码逻辑顺序不正确(Optimization Level)

问题:编译策略之代码逻辑顺序不正确(Optimization Level)

问题 曾经遇到过一个问题, 运行一段代码发现执行的逻辑顺序不正确, 而且在添加了其他语句后, 还会有不同的顺序, 但是都是不正确的. 如下: Debug 一下发现, 逻辑顺序为: 1> – 2> – 1> – 3>,而且在其中的添加 NSLog 后顺序还会发生变化 分析 在过程中 tes…
阅读更多...
297. 二叉树的序列化与反序列化

297. 二叉树的序列化与反序列化

297. 二叉树的序列化与反序列化 难度困难 序列化是将一个数据结构或者对象转换为连续的比特位的操作&#xff0c;进而可以将转换后的数据存储在一个文件或者内存中&#xff0c;同时也可以通过网络传输到另一个计算机环境&#xff0c;采取相反方式重构得到原数据。 请设计一个…
阅读更多...
C++ 单链表基本操作分析与实现 链表 　　链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结

C++ 单链表基本操作分析与实现 链表 　　链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结

C 单链表基本操作分析与实现链表 链表是一种物理存储单元上非连续、非顺序的存储结构&#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点&#xff08;链表中每一个元素称为结点&#xff09;组成&#xff0c;结点可以在运行时动态生成。每个结点…
阅读更多...
阿里巴巴离职DBA职业生涯总结

阿里巴巴离职DBA职业生涯总结

阿里巴巴离职DBA职业生涯总结 导读 去年很多朋友私下或新浪微博上在总结自己的职业生涯与职业规划&#xff0c;也感觉到很纠结与彷徨&#xff0c;尤其技术人的职业生涯&#xff0c;随年龄增加&#xff0c;一些优势逐渐丧失。4月13日数据库技术大会的主办方举行的晚宴上&#xf…
阅读更多...
阿里巴巴离职DBA 35岁总结的职业生涯-职业规划

阿里巴巴离职DBA 35岁总结的职业生涯-职业规划

----------------------学习java、广州 java培训、期待与您交流&#xff01; ---------------------- 转载自&#xff1a;阿里巴巴离职DBA 35岁总结的职业生涯 http://www.apkbus.com/android-43723-1-1.htm 导读&#xff1a; 去年很多朋友私下或新浪微博上在总结自己的职业…
阅读更多...
第五届字节跳动青训营 前端进阶学习笔记（四）TypeScript入门

第五届字节跳动青训营 前端进阶学习笔记（四）TypeScript入门

文章目录前言TypeScript概要1.什么是TypeScript2.TypeScript基本语法基础数据类型对象类型函数类型函数重载数组类型补充类型泛型约束和泛型默认参数类型别名和类型断言高级类型1.联合类型2.交叉类型3.类型守卫类型谓词总结前言 课程重点&#xff1a; TypeScript概要TypeScri…
阅读更多...
回溯法之旅行商问题解题思路详解

回溯法之旅行商问题解题思路详解

问题定义 输入&#xff1a; 完全无向带权图G&#xff08;V,E&#xff09; |V|n, |E|m 对于E中的某条边e&#xff0c;其长度为c(e) 输出&#xff1a; 最短哈密顿回路&#xff08;经过每个节点一次且仅一次的回路&#xff09; ps.这是一个NP问题&#xff0c;没有有效的算法…
阅读更多...
【精讲】PCIe基础篇——Memory IO 地址空间

【精讲】PCIe基础篇——Memory IO 地址空间

在早期的PC中&#xff0c;IO设备中的内部寄存器/存储是通过IO地址空间(由Intel定义)来访问的。然而&#xff0c;由于与IO地址空间相关的一些限制和不良影响(我们在这里不讨论)&#xff0c;IO地址空间很快就失去了软件和硬件供应商的青睐。这导致IO设备的内部寄存器/存储被映射到…
阅读更多...
Matlab遗传算法用于旅行商问题优化TSP

Matlab遗传算法用于旅行商问题优化TSP

Matlab遗传算法用于旅行商问题优化要求第一步&#xff1a;参数编码和初始群体设定第二步&#xff1a;计算路径长度的函数设计第三步&#xff1a;计算选择算子第四步&#xff1a;计算交叉算子第五步&#xff1a;计算变异算子结果及分析MATLAB总代码要求 利用遗传算法求旅行商问…
阅读更多...
（三）计算机组成原理——总线

（三）计算机组成原理——总线

文章目录&#xff08;三&#xff09;计算机组成原理——总线总线的基本概念单总线双总线面向CPU以存储器为中心总线的分类片内总线系统总线数据总线地址总线控制总线通信总线总线特性及性能指标总线特性机械特性电气特性功能特性时间特性性能指标总线标准总线结构单总线多总线双…
阅读更多...
TSP_旅行商问题 - 蛮力法DFS（一）

TSP_旅行商问题 - 蛮力法DFS（一）

一、前言 【旅行商问题】旅行商问题(TravelingSalesmanProblem&#xff0c;TSP)是一个经典的组合优化问题。经典的TSP可以描述为&#xff1a;一个商品推销员要去若干个城市推销商品&#xff0c;该推销员从一个城市出发&#xff0c;需要经过所有城市后&#xff0c;回到出发地。应…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023