深度刨析树布局（从入门到入土讲解AVL树及红黑树的奥秘）

目录

树的表现
二叉树的概念及布局（重点学习）
概念 ：
特点：
树与非树
特殊的二叉树 
二叉树的性质(重点)
二叉树的存储布局
堆的概念及布局 
建堆方式： 
向下调整算法
向上调整算法 
建堆第一步初始化
建堆的复杂度分析
堆的插入 
 堆的删除
堆排序
topK问题
堆排序的稳定性
堆的模拟实现
堆与优先级队列的联系
再次理解less仿函数
二叉树的进阶 
二叉搜索树
二叉搜索树的结点
二叉搜索树的插入
二叉搜索树的删除 （难点及重点）
二叉搜索树的应用 
二叉搜索树的经典使用场景
二叉搜索树的性能分析
map和set的底层布局 
AVL树
AVL树结点的定义 
AVL树的插入
AVL树的旋转讲解
右单旋
左单旋 
左右双旋 
右左双旋 
旋转问题总结：
 AVL树的删除（了解）
AVL树的性能
AVL树的代码实现
红黑树
红黑树的性质 
红黑树结点的定义 
红黑树类的定义
红黑树的颜色计划 
红黑树的插入 
红黑树的颜色调节（重点难点） 
总结颜色调节方案
红黑树的模拟实现
红黑树的删除
红黑树的性能
红黑树的应用
红黑树与AVL树的比力
map和set的模拟实现

---

树是一种非线性的数据布局，它是由n>=0个有限结点组成的一个有层次关系的集合，把它叫做树是由于像一个倒挂的树，根在上，叶子在下
对于树，每颗树都可以看成根节点和子树，全部的子树又可以看成根节点和子树，所以树是递归定义的
结点的度：一个结点含有的子树的个数，也就是它的儿子有多少
根节点：一个特殊的结点，它没有前驱结点（也就是没有父结点）
叶节点（终端结点）：没有子结点的结点（度为0的结点）
父/子结点：一个结点可以为另一个的父结点或者其他的子结点（子与父的概念是相对的）
分支结点（非终端结点）：度不为0
兄弟结点：具有相同的父结点
堂兄弟结点：父结点在同一层的结点
结点的祖先：从根节点到该结点所经分支上的全部结点
树的度：全部结点的度的最大值
结点的层次：从根开始，根为第一层，依次往下为第二第三层
树的高度或者深度：树中结点的最大层次
森林：由多颗互不相交的树的集合（并查集的本质就是森林）
树的表现

树有许多种表现方法，双亲表现法，孩子表现法，孩子兄弟表现法等等 

孩子兄弟表现法

优点

• 同一布局：将复杂的多叉树转换为二叉树，便于使用二叉树的算法和操作。
  
• 节省空间：每个节点只需两个指针（左孩子、右兄弟），无论原树的度多大。
  
• 机动性：支持动态插入和删除节点，调整指针即可。
  

缺点

• 遍历复杂度增加：查找某个节点的全部子节点需要遍历其右子树，时间复杂度为 O(k)（k 为子节点数）。
  
• 不直观：原树的布局被转换为二叉树，理解和调试难度增加。
  
• 不得当频仍查找父节点：若需频仍查找父节点，需额外维护父指针或使用双亲表现法。
  

实用场景

• 多叉树转二叉树：
  
  
  
  • 如文件体系目录树、XML/JSON 布局等，将复杂树转换为二叉树处理。
    
  
  
• 动态树操作：
  
  
  
  • 支持高效插入和删除子节点（调整指针即可）。
    
  
  
• 树的遍历与递归：
  
  
  
  • 可使用二叉树的遍历算法（前序、中序、后序）处理多叉树。
    
  
  
• 存储森林（多棵树）：
  
  
  
  • 森林可视为根节点互为兄弟的树，通过孩子兄弟表现法可将森林转换为一棵二叉树。
    
  
  

                                                               双亲表现法：

这种双亲表现法是每个结点存储它的父亲来表现树，也就相当于有一个数据域，有一个双亲域
数据域存数据，双亲域存父亲
这种布局的上风在于查找父亲时O(1)
得当频仍向上遍历的场景（如并查集、族谱关系等）。
缺点

• 查找子节点效率低：需遍历整个数组，时间复杂度为 O(n)。
  
• 不得当动态插入 / 删除：调整节点大概需要大量移动数组元素。
  
• 无法直接区分左右子树：若需区分，需额外存储左右子树信息。
  

实用场景

• 并查集（Union-Find）：
  
  
  
  • 核心操作是查找元素的根节点和归并集合，双亲表现法能快速找到父节点，优化路径压缩。
    
  
  
• 族谱 / 层次关系：
  
  
  
  • 如家族树、构造架构图等，需频仍查询 “某个节点的父节点是谁”。
    
  
  
• 无需频仍增删节点的静态树：
  
  
  
  • 若树布局稳定，且重要操作是向上回溯（如文件体系路径查找），双亲表现法很高效。
    
  
  
• 某些算法优化：
  
  
  
  • 如 Kruskal 最小生成树算法中，用双亲表现法判定两个节点是否属于同一集合。
    
  
  

                                                   孩子表现法

孩子表现法（Child Representation）是一种用于存储树（尤其是多叉树）的数据布局，它通过为每个节点维护一个子节点列表来表现树的层次关系。这种方法特殊得当需要频仍访问子节点的场景，但查找父节点的效率较低。
优点

• 快速访问子节点：
  
  
  
  • 查找某个节点的全部子节点时间复杂度为 O(1)（直接访问列表）。
    
  
  
• 支持恣意度的树：
  
  
  
  • 每个节点可拥有恣意数量的子节点，只需调整列表大小。
    
  
  
• 动态扩展性：
  
  
  
  • 使用动态数组或链表时，可随时添加 / 删除子节点。
    
  
  

缺点

• 查找父节点效率低：
  
  
  
  • 若需查找某个节点的父节点，需遍历整个树，时间复杂度为 O(n)。
    
  
  
• 空间开销较大：
  
  
  
  • 每个节点需额外存储子节点列表的指针，大概造成空间浪费（尤其是子节点较少的节点）。
    
  
  
• 不得当频仍向上遍历的场景：
  
  
  
  • 如并查集、族谱查询等需要频仍查找父节点的场景，使用孩子表现法效率较低。
    
  
  

实用场景

• 文件体系目录布局：
  
  
  
  • 目录可包含多个子目录 / 文件，得当用孩子表现法快速访问子节点。
    
  
  
• XML/JSON 剖析树：
  
  
  
  • 每个节点（标签 / 键值对）可包含多个子节点，需频仍遍历子节点。
    
  
  
• 游戏场景树：
  
  
  
  • 游戏中的场景元素（如角色、道具）大概包含多个子元素，需快速访问子节点。
    
  
  
• 语法树（AST）：
  
  
  
  • 编译器中的抽象语法树，每个节点（如表达式、语句）大概有多个子节点。
    
  
  

 树在实际中的运用：表现文件体系的目录树布局就可以使用
二叉树的概念及布局（重点学习）

概念 ：

一颗二叉树是结点的有限集合，该集合要么为空，要么看成由根+ 左子树 + 右子树 的组成
左子树和右子树又可以依次往下分
特点：

1.一个结点最多只有两颗子树，也就是说它的度不能超过2（不存在度大于2的结点）
2.二叉树的子树有左右之分，其子树的序次不能颠倒
树与非树

树：1.子树不能相交
       2.除了根结点以外，其他每个结点都有且只有一个父结点
       3.一颗树有N个结点，有N-1条边（其实有许多种方法推导这个结论，好比每个结点都提供一条边，除了根结点，所以就少一条边）

特殊的二叉树 

满二叉树：一个二叉树，假如每一个层的结点数都到达最大，则这个二叉树就是满二叉树。也就是说，假如一个二叉树的层数为K，且结点总数是（2^K）-1,则它就是满二叉树
K层的满二叉树结点总数是（2^K）-1如何推导？
第一层是2^0,第二层是2^1……第k层就是2^(k-1)，进行等比数列求和即可
完全二叉树：完全二叉树是效率很高的数据布局，完全二叉树是由满二叉树而引出来的。对于深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树一种特殊的完全二叉树
换句人话就是，第k-1层都满，第k层从左往右依次填

总结 树-->二叉树-->完全二叉树 -->满二叉树
二叉树的性质(重点)

1.若规定根节点的层数为1，则一颗非空二叉树的第K层上最多有2^(K-1)个结点（通过观察得出）
2.若规定根节点的层数为1，则深度为K的二叉树的最大结点数是2^K-1（也就是满二叉树）
3.对任何一颗二叉树，假如度为0的叶子结点数为N0，度为2的分支结点个数为N2，
则有N0=N2+1；
4.若规定根节点的层数为1，具有N个结点的满二叉树的深度，h=log(N+1)
深度为h的结点总数为2^h-1=N     h=log（N+1）
对于普遍结论，2^h-1-x(x为在满二叉树的情况下少的结点数，x范围[0，2^(h-1)-1])
当x等于0时，它就是满二叉树h=log（N+1）
当x大于0小于等于2^(h-1)-1，它就是完全二叉树，2^h-1-2^(h-1)+1=N，h=logN+1
所以在盘算时间复杂度是可以近似为logN
二叉树的存储布局

二叉树一般可以使用两种布局存储，一种顺序布局，一种链式布局
顺序布局：就是使用数组进行存储，一般使用数组只得当表现完全二叉树，由于不是完全二叉树会有空间的浪费。而实际使用中只有对才会使用数组来存储，关于堆后面会讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树

注意:如何得出孩子和父亲的下标 ？？？
假如父亲的下标是i，那左孩子就是2*i+1，右孩子就是2*i+2
假如孩子的下标是i，那父亲的下标就是（i-1）/2
这个坐标必须记住，后面学习堆会大量使用
对于顺序布局存储再次夸大仅仅实用于完全二叉树，不实用于平凡二叉树，会浪费空间
链式布局：就是用链表来表现一颗而擦函数，即用链来只是元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链接点的存储地址。链式布局又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后续学到红黑树等会用到三叉链

堆的概念及布局 

假如有一个关键码的集合K={K0，K1，K2，……Kn-1}，把它的全部元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足Ki<=K2i+1，且Ki<=K2i+2（Ki>=K2i+1，且Ki>=K2i+2）i=0，1，2，3……，则称为小堆（或大堆）。将根结点最大的叫做最大堆，根节点最小的堆叫做最小堆
对应我们之前讲的知道一个父亲结点的坐标，求孩子坐标
这里用简单的话总结就是：基于完全二叉树，大堆：每个父亲都大于等于孩子
                                                                         小堆：每个父亲都小于等于孩子
但没有规定左右孩子谁大，只是跟父亲比力即可

建堆方式： 

起首先了解向下调整算法和向上调整算法（前提都是构建小堆）
向下调整算法

参数说明：a是一个数组，也就是我们上面所讲的顺序布局中的数组，n为数组最后一个元素的下一个元素的下标，root为根节点的坐标。
函数解释：就是给一个根节点，在左子树和右子树都是小堆的前提下，把根结点依次向下调整构建小堆
向上调整算法 

 参数说明：a是一个数组，也就是我们上面所讲的顺序布局中的数组，n为数组最后一个元素的下一个元素的下标，child为孩子元素的下标。
函数解释：按照上面的步骤，我们要找到它的父亲，所以父亲parent=(child-1)/2，由于我们建小堆，小堆就是孩子比父亲大，换句话就是孩子比父亲小就交换，把小的往上换

建堆第一步初始化

初始化的的意思就是当你传进来的是一个数组时，我要把这个数组进行初始化成堆

一、Floyd 建堆算法（自底向上建堆）

核心思想：从最后一个非叶子节点开始，逐个下沉调整，确保每个子树都是堆。也就是用向下调整算法进行初始化，从下往上
步骤：

• 将数组视为完全二叉树，最后一个非叶子节点的索引为 (n-2)/2（n 为数组长度）。（由于最后一个元素的坐标n-1，n为数组的长度，找它的父亲也就是（n-1-1）/2）
  
• 从最后一个非叶子节点开始，向前遍历每个节点：
  
  
  
  • 对当前节点执行下沉操作：将当前节点与其子节点比力，若不满足堆性质，则与较大（大根堆）或较小（小根堆）的子节点交换，继承向下调整，直到满足堆性质。
    
  
  

二、插入法（自顶向下建堆）
核心思想：逐个插入元素，每次插入后通过上浮操作调整堆布局。就是你依次插入元素，使用向上调整算法进行初始化，这种是取数组中的每一个元素进行插入后调整
步骤：

• 初始化一个空堆。
  
• 依次将数组元素插入堆中。
  
• 每次插入后，将新元素与其父节点比力：
  
  
  
  • 大根堆：若新元素比父节点大，则交换二者位置，继承向上比力，直到满足父节点≥子节点。
    
  • 小根堆：若新元素比父节点小，则交换二者位置，继承向上比力，直到满足父节点≤子节点。 
    
  
  

建堆的复杂度分析

Floyd 建堆算法（自底向上建堆）：

时间复杂度：O(n)
精确盘算：
第一层有2^0个节点，每个节点最多向下调整h-1次。
第二层有2^1个节点，每个节点最多向下调整h-2次。
第三层有2^2个节点，每个节点最多向下调整h-3次。
......
第h-1层有2^(h-2)个节点，每个节点最多向下调整1次。
最多需要调整的次数：使用高中的错位相减
F(h)=2^0*(h-1)+2^1*(h-2)+2^2*(h-3)+...+2^(h-2)*1
2F(h)=2^1*(h-1)+2^2*(h-2)+2^3*(h-3)+...+2^(h-1)*1
两式相减得：F(h)=2^(h-1)+2^1+2^2+...+2^(h-2)-2^0*(h-1)
F(h)=2^h-1-h
根据之前得的结论h=logN，带入可得F(h)=N-1-logN.
最后就是时间复杂度就是O（N）
空间复杂度：看你要不要封装一个类单独去存，假如没有仅仅在原数组上操作就是O(1)
插入法（自顶向下建堆）：
时间复杂度：O（nlogn）
第二行2^1个数据，每个数据向上调整1次
第三行2^2个数据，每个数据向上调整2次
......
第h行2^(h-1)个数据，每个数据向上调整h-1次
最多需要调整的次数：T(h)=2^1*1+2^2*2+...+2^(h-1)*(h-1)
                                    2T(h)=2^2*1+2^3*2+...+2^h*(h-1)
两式相减得：T(h)=2^h*(h-1)-2^1-（2^2+2^3+...+2^(h-1))
             T(h)=2^h*(h-1)-2^h+2
最后得：T(h)=(N+1)*(log(N+1)-1)-N+1
省掉一些常数级别，最后就是时间复杂度O(nlogn)
空间复杂度：看你要不要封装一个类单独去存，假如没有仅仅在原数组上操作就是O(1)
对于建堆，使用自底向上的时间复杂度更低，这实用于给一个原生数组，在原生数组上操作，假如是需要读取一个一个的数据在进行插入构建堆，使用自顶向下更好
堆的插入 

开辟完空间，接纳向上调整算法进行调整 
 堆的删除

核心思绪：把堆顶的跟最后一个换，然后在使用向下调整算法，如许时间复杂度就是O（logN）
假如你删除堆顶的数据，然后又在进行建堆，如许时间复杂度高
对于堆的构建我们根本就实现这些功能 
堆排序

学习完堆，你是否发现堆可以进行排序，假如我们构建了小堆，堆顶就是最小的，假如构建了大堆，堆顶就是最大的，因此我们可以进行排序，依次筛选，所以堆也叫选择排序的一种

第一种：你在构建堆那里是O(N)，假如你每次选小的出来后在重新构建堆，那就是N*N
第二种，你在构建堆那里是O(N)，然后每次选小的出来和最后交换，然后在向下调整算法，那就是N*logN
基于这种思想：可以显着得出小堆排降序，大堆排升序
topK问题

TopK 问题是指从海量数据中找出前 K 大或前 K 小的元素，常见于搜索引擎、保举体系、数据分析等场景。
基于堆的实现：
核心思想：好比你现在有一组数组，你需要找到前K大的数据是多少
此时你需要构建一个只能存K个元素的小堆，遍历一遍数据，
遍历数据时，若当前元素比堆顶大，则替换堆顶并调整堆。
那最后竣事堆顶就是前K大的数据
时间复杂度：遍历一遍数据O(N)，向下调整算法那就是logK，最后就是NlogK
假如要找前K小就是构建大堆，前K大就是构建小堆
堆排序的稳定性

什么叫稳定性：就是假如原生数组中有两个相同的数据，一个的下标是3，一个的下标是6，假如排完序，下标为3的还是在下标为6的左边，那就叫稳定，反之就是不稳定
概念：指在排序过程中，相同元素的相对顺序是否保持不变。若相同元素的相对顺序在排序后与排序前划一，则称该排序算法是稳定的；反之则是不稳定的。
对于堆排序的稳定性，我们可以分析得出堆排序是不稳定的，由于你在构建堆和调整过程都会破坏相同元素的相对顺序，包罗你在排序时进行堆顶数据和最后一个元素的位置交换时，你仅仅只能保证当前最大值或者最小值的元素的位置正确
总之，最关键的一点就是你没有标记相同元素如那边理，你只是在构建堆是，好比小堆，你就是比父亲小就交换，你根本没有考虑到二叉树的层级和左右子树关系
堆的模拟实现

June: 这里包含我的c++和Linux及数据布局

https://gitee.com/taifanshu/day2.git
堆与优先级队列的联系

在C++章节中我们曾提到，优先级队列（假如没有学习可以略过）的底层布局就是构建一个堆
默认情况下是构建一个大堆，由于你是优先级队列，优先的意思就是大的先出
那每次top数据时都是取堆顶的数据，然后你pop后，优先级队列会主动把堆顶的数据和最后一个交换，然后在进行向下调整算法，最后你的size--即可
再次理解less仿函数

对于less，我们return是x1<x2是返回true，此时构建的是大堆
大堆就是孩子比父亲大就交换， 
 

但是我们这里在实现小堆的时间时a[child]<a[parent]，假如孩子小就进行交换
那STL应该就是如许实现的，孩子就是x2，父亲就是x1，x1<x2(即孩子大于父亲)，就返回true
就进行交换，所以我们可以大胆推出库是如许实现的_com(parent,child); 
那对于小堆就是greater，return x1>x2，那就是_com(parent,child)；孩子比父亲小就返true，交换
所以联合两篇文章我们已经深度理解堆和优先级队列 
二叉树的进阶 

本节目的
1.二叉搜索树
引入：对于二叉树我们已经进行了初步的理解，二叉树进阶是由于map和set的底层布局需要学习
二叉搜索树

概念：二叉搜索树又称二叉排序树，它或者是一颗空树，或者是具有一下性质的二叉树
1.若它的左子树不为空，则左子树上全部结点的值都小于根节点的值
2.若它的右子树不为空，则右子树上全部结点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

对比堆

没有严酷像二叉搜索树那样左边比跟小，右边比根大 
二叉搜索树的结点

在这里我们为了方便map和set的底层布局，我们的数据就搞成K _key，如许方便后面改成key_value模型等  

我们在BSTree类中构建一个私有成员：根节点，Node为typedef过的
二叉搜索树的插入

a.假如树为空，则直接插入
b.假如树不为空，则按二叉搜索树的性质查找后进行插入

对于相当就返回false，由于key关键字只能为一个，也就是map和set中只能存一个key的情形
二叉搜索树的删除 （难点及重点）

1.起首查找元素是否在二叉搜索树中，假如不存在，则返回false，否则要删除的结点分四种情况
   a.要删除的结点无孩子结点
   b.要删除的结点只有左孩子结点
   c.要删除的结点只有右孩子结点
   d.要删除的结点有左、右孩子结点
看起来有待删除结点有四种情况，实际情况a可以与情况b和c情况归并

1.         bool erase(const K&key)
2.         {
3.                
4.                 //第一步先找到要删除的结点
5.                 Node* parent = _root;
6.                 Node* cur = _root;
7.                 while (cur)
8.                 {
9.                         if (key > cur->_key)
10.                         {
11.                                 parent = cur;
12.                                 cur = cur->_right;//如果大于就到右边去找
13.                         }
14.                         else if (key < cur->_key)
15.                         {
16.                                 parent = cur;
17.                                 cur = cur->_left;//如果小于就到左边去找
18.                         }
19.                         else
20.                         {
21.                                 //找到要删除的结点
22.                                 //分为三类
23.                         //1.一个结点的左结点为空，父亲指向我的右结点（叶子结点可以归结与第一或者第二种情况）
24.                                 if (cur->_left == nullptr)
25.                                 {
26.                                         if (cur == _root)
27.                                         {
28.                                                 _root = cur->_right;//注意删除的情况为根的时候要特殊处理，不然找不到parent从而崩溃，因为你后面把根释放了，这颗树连根都没有了
29.                                         }
30.                                         else {
31.                                                 if (key > parent->_key)//这个结点是父亲的右结点
32.                                                 {
33.                                                         parent->_right = cur->_right;
34.                                                 }
35.                                                 else
36.                                                 {     //这个结点是父亲的左结点
37.                                                         parent->_left = cur->_right;
38.                                                 }
39.                                         }
40.                                         delete cur;
41.                                 }
42.                                 //2.一个结点的右结点为空，父亲指向我的左结点
43.                                 else if (cur->_right == nullptr)
44.                                 {
45.                                         if (cur == _root)
46.                                         {
47.                                                 _root = cur->_left;
48.                                         }
49.                                         else
50.                                         {
51.                                                 if (key > parent->_key)//这个结点是父亲的右结点
52.                                                 {
53.                                                         parent->_right = cur->_left;
54.                                                 }
55.                                                 else
56.                                                 {     //这个结点是父亲的左结点
57.                                                         parent->_left = cur->_left;
58.                                                 }
59.                                         }
60.                                         delete cur;
62.                                 }
63.                         //3.一个结点的左右结点都不为空，则用替换法，用左子树的最大或者右子树的最小结点替换
64.                                 else
65.                                 {
66.                                         //找有子树的最小结点
67.                                         Node* rightMinparent = cur;
68.                                         Node* rightMin = cur->_right;
69.                                         while (rightMin->_left)
70.                                         {
71.                                                         rightMinparent = rightMin;
72.                                                         rightMin = rightMin->_left;
73.                                         }
74.                                         //替换
75.                                         cur->_key = rightMin->_key;
76.                                         //删除
77.                                         if (rightMinparent->_left==rightMin)
78.                                         {
79.                                                 rightMinparent->_left = rightMin->_right;
80.                                         }
81.                                         else
82.                                                 rightMinparent->_right = rightMin->_right;
84.                                         delete rightMin;
85.                                 }
86.                                 return true;
87.                         }
88.                 }
89.                 //没找到要删除结点
90.                 return false;
91.         }

复制代码

第一步肯定是先要找到删除的结点
第二步假如找到了就进行删除，(找到的结点为cur)根据分类进行删除

a. 要删除的结点左孩子为nullptr，判定这个删除的结点是父亲的左边还是右边
    假如删除的结点是父亲的左边，要把删除结点的右边连接到父亲的左边
    假如删除的结点是父亲的右边，要把删除结点的右边连接到父亲的右边
同时注意：这个删除的结点大概是根节点，假如是根节点而且左边为nullptr，直接把根给右边即可

b.要删除的结点右孩子为nullptr，判定这个删除的结点是父亲的左边还是右边
   假如看懂了a的操作逻辑，b这种情况就是一样的
注意：叶子结点的删除可以视为a或者b情况，由于叶子是属于左右都为空（也就是上面我们归类时所说的可以把这些情况归为一类）
c.要删除的结点有左右结点

好比你要删除3，需要用到替换法，此时你是否发现只需要把4往上替换原来3的位置即可
替换法的原理：简单来说，就是找到一个结点，要能替代你当前结点的作用，从而重新到达二叉搜索树的性质，好比这里你要删除3，你要找3的下面找，不能去右边找10/14等，由于你在左边找是要满足左边的都比8小，那找谁比力合适？？？找左子树的最小，好比1，左子树的最小替换后，是不是还满足二叉树的性质，找右子树的最大，好比7，也满足
当要删除的结点左右都不为空时，找删除的结点的左子树的最大或者右子树的最小结点替换

我们只需要理解删除和插入即可，对于别的的可以自行实现 
June: 这里包含我的c++和Linux及数据布局

https://gitee.com/taifanshu/day2.git代码已经上传gitee 
二叉搜索树的应用 

K模型：K模型即只有key作为关键码，布局中只需要存储Key即可，关键码即为需要搜索的值
好比：给一个单词word，判定该单词是否拼写正确，详细方式如下：
           a.以单词集合中的每个单词作为Key，构建一颗二叉搜索树
           b.以二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误
K-V模型：每一个关键码Key，都有与之对应的值value，即<Key,value>的键值对。这种方式在实际生活中非常常见：
好比英汉辞书就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word,chinese>就构成一种键值对
好比统计次数，统计乐成后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word,count>就构成一种键值对
二叉搜索树的经典使用场景

1.搜索
2.排序：中序遍历出来就是有序的
二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能
对有n个结点的二叉搜索树，若每个元素查找的概率相当，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，比力次数越多
但对于同一个关键码集合，假如个关键码插入的序次差别，大概得到差别布局的二叉搜索树

最优情况下：二叉搜索树是完全二叉树，时间复杂度为O（logN）
最差情况下：假如插入的元素是有序的或者接近有序的，二叉搜索树退化为单支树（上图情况还可以更严重），此时退化称链表的布局，时间复杂度为O（N） 
学到这里可以看一下C++栏的STL关于map和set的讲解
map和set的底层布局 

学到这里发现假如以平凡的二叉搜索树作为map和set的底层布局，大概会导致出现单支树，或者平均一点大概会出现畸形，就是一边高一边低，时间复杂度就会上来，因此map和set等关联式容器的底层布局式对二叉树进行了平衡处理，即接纳平衡树来实现
AVL树

AVL树的概念：基于平凡二叉搜索树的缺陷，两位前苏联数学家格奥尔吉・阿杰尔松 - 韦利斯基（G.M. Adelson-Velsky）和叶夫根尼・兰迪斯（E.M. Landis）在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新的结点后，假如能保证每个结点的左右子树高度之差的绝对值不超过1（反之超过就需要对树中的结点进行调整），即可低落树的高度，从而减少平均搜索长度
平衡因子：右子树的高度-左子树的高度（这个平衡因子只是一种实现方式，不是必须如许）
AVL树具有以下性质：
1.左右子树都是AVL树
2.左右子树的高度差（平衡因子）的绝对值不超过1（1/0/-1）

假如一颗二叉搜索树是高度平衡的，它就是AVL树，假如有n个结点，时间复杂度在O（logN）
AVL树结点的定义 

这里为了后续方便与map和set做底层布局，所以实现是接纳键值对的实现方法
实现三叉链的布局，而且引入平衡因子，键值对

对于AVLTree的私有成员就是一个根结点，这个结点我们进行了typedef，方便后续使用
AVL树的插入

AVL树就是在二叉搜索树的根本上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。
那么AVL树的插入过程就可以分为两步：
1.按照二叉搜索树的方式插入新结点
2.更新结点的平衡因子
3.假如出现了不平衡，则需要旋转
1.插入新结点

第一步跟二叉搜索树一样，找到要插入的位置
找到之后，cur就是你要插入的位置

直接对cur新开一块空间，而且使用kv进行初始化
然后对比parent的kv，假如大于就插右边，小于插左边
注意：上面查找cur时仅仅是查找位置，你并没有进行连接，就是你的parent的左指针右指针都没改变，不要误以为查找到了位置就行了，还要把它连接起来
2.更新平衡因子 
起首要知道平衡因子出现问题只会出现在cur的直系祖宗上，由于你只改变了一边，沿着这条边往上直到根都大概会变，所以我们要依次往上更新到根，只要出现问题就处理
平衡因子（1/-1/0）正常就不需要处理
起首对于插入cur结点的平衡因子，插入的肯定是叶子结点，平衡因子为0
其次更新父亲，判定cur是父亲的左还是父亲的右，假如cur是父亲的左，父亲的平衡因子就--，cur是父亲的右就++，由于平衡因子是右-左
检查平衡因子：分三种情况
原理：假如一个结点的平衡因子更新完之后是0，那就证明它原来是1或者-1，更新完之后平衡了，假如一个结点的平衡因子更新完之后是1或者-1，那就证明原来是0，那原来是平衡的，插入后大概以parent为根结点的树高度增加，需要在向上更新平衡因子，假如一个平衡因子更新完之后是-2或者2，那就证明出现平衡出现了问题，需要旋转。
a.假如父亲的平衡因子等于0，是不是证明原来是1或者是-1，假如--或者++操作变成了0，也就是新插入的结点并没有影响平衡，那此时就不需要在往上更新平衡因子了，此时整棵树已经平衡了
b.假如父亲的平衡因子等于-1或者1，那父亲原来是0，通过++或者--才会出现1/-1，那此时就要更新父亲的父亲（一直到root）
c.假如父亲的平衡因子等于-2或者2，那就是原来是-1或者1，此时需要旋转，这种最麻烦
AVL树的旋转讲解

右单旋

这里h表现下面是以h高度的结点，讲的是一种普遍情况，也就是抽象出来的
h+1新增一个结点，此时30这个结点的平衡因子变成-1，原来是0现在变成-1，会导致全部含有这个结点的树的高度增加，大概会出现平衡问题，我们在往上更新60这个结点时，发现结点变成-2，那此时就需要进行旋转，旋转的意思就是把60按下去，让它高度降下来，从而到达平衡
右单旋就是把不是30新增的那边接到60的左边，由于他们都比60小，然后把60接到30的下面
需要考虑的特殊情况：
1.30结点的右孩子大概存在，大概不存在（也就是当h=0时，只是新增一个结点在30的左边）
2.60大概是根结点，也大概是某一棵子树，假如是根结点，旋转完之后需要更新根结点，假如是子树，大概是某个结点的左子树或者右子树（需要判定）

1.         //右单旋
2.         void RotateR(Node* parent)
3.         {
4.                 //parent的左边指向subR的右边边
5.                 //subR的右边指向parent
6.                 Node* subL = parent->_left;
7.                 Node* subLR = subL->_right;//subR的右子树
8.                 parent->_left = subLR;
9.                 if (subLR)//判断subRL是否为null
10.                 {
11.                         subLR->_parent = parent;//如果不是null才改变父亲，否则会出现问题，解引用空指针
12.                 }
13.                 subL->_right = parent;
14.                 Node* pparent = parent->_parent;//记录原父亲，方便找到并链接subR的父亲
15.                 parent->_parent = subL;
16.                 //不能简单的将subR的父亲为pparent，有可能subR为_root
17.                 if (parent == _root)
18.                 {
19.                         _root = subL;
20.                         subL->_parent = nullptr;
21.                 }
22.                 else
23.                 {
24.                         //如果不是根，还要明确改动的是左子树还是右子树
25.                         if (parent == pparent->_left)
26.                         {
27.                                 pparent->_left = subL;
28.                         }
29.                         else
30.                         {
31.                                 pparent->_right = subL;
32.                         }
33.                         subL->_parent = pparent;
34.                 }
35.                 parent->_bf = 0;
36.                 subL->_bf = 0;
37.         }

复制代码

参数说明：subL是父亲的左结点，subLR是父亲左结点的右子树
最后进行更新平衡因子即可 
左单旋 

 

通过右单旋的学习，左单旋就是反着来，好比此时你右边新增一个，先更新60的平衡因子，变成1，说明以60这个结点为分支结点的全部路径的高度出现变更，需要继承往上更新，发现更新到30时变成了2，出现了问题，不要在往上更新了，说明不平衡了，此时需要进行旋转
特殊情况：
1.60结点的右孩子大概存在，大概不存在（也就是当h=0时，只是新增一个结点在60的右边）
2.30大概是根结点，也大概是某一棵子树，假如是根结点，旋转完之后需要更新根结点，假如是子树，大概是某个结点的左子树或者右子树（需要判定）

1. //左单旋
2. void RotateL(Node* parent)
3. {
4.         //parent的右边指向subR的左边
5.         //subR的左边指向parent
6.         Node* subR = parent->_right;
7.         Node* subRL = subR->_left;//subR的左子树
8.         parent->_right = subRL;
9.         if (subRL)//判断subRL是否为null
10.         {
11.                 subRL->_parent = parent;//如果不是null才改变父亲，否则会出现问题，解引用空指针
12.         }
13.         subR->_left = parent;
14.         Node* pparent = parent->_parent;//记录原父亲，方便找到并链接subR的父亲
15.         parent->_parent = subR;
16.         //不能简单的将subR的父亲为pparent，有可能subR为_root
17.         if (parent == _root)
18.         {
19.                 _root = subR;
20.                 subR->_parent = nullptr;
21.         }
22.         else
23.         {
24.                 //如果不是根，还要明确改动的是左子树还是右子树
25.                 if (parent == pparent->_left)
26.                 {
27.                         pparent->_left = subR;
28.                 }
29.                 else
30.                 {
31.                         pparent->_right = subR;
32.                 }
33.                 subR->_parent = pparent;
34.         }
35.         parent->_bf = 0;
36.         subR->_bf = 0;
37. }

复制代码

左右双旋 

 

新增结点在b下面，导致b的高度变成h，所以60的结点就变成了-1，此时需要往上更新30，由于60是30的右子树，所以++，就变成了1，在往上更新90，30是90的左子树，所以--，变成了-2
此时出现了-2，需要进行旋转，先对30进行左单旋，然后在对90进行右单旋，全部旋转完后在考虑平衡因子 

1.         //左右双旋
2.         void RotateLR(Node* parent)
3.         {
4.                 Node*subL = parent->_left;
5.                 Node* subLR = subL->_right;
6.                 int bf = subLR->_bf;
7.                 RotateL(subL);
8.                 RotateR(parent);
9.                 if (bf == 1)
10.                 {
11.                         //在subLR的右边插入
12.                         parent->_bf = 0;
13.                         subL->_bf = -1;
14.                         subLR->_bf = 0;
15.                 }
16.                 else if (bf == -1)
17.                 {
18.                         //在subLR的左边插入
19.                         parent->_bf = 1;
20.                         subL->_bf = 0 ;
21.                         subLR->_bf = 0;
22.                 }
23.                 else
24.                 {
25.                         //subLR作为新的结点插入构成折线
26.                         parent->_bf = 0;
27.                         subL->_bf = 0;
28.                         subLR->_bf = 0;
29.                 }
31.         }

复制代码

右左双旋 

1. //右左双旋
2. void RotateRL(Node* parent)
3. {
4.         Node* subR = parent->_right;
5.         Node* subRL = subR->_left;
6.         int bf = subRL->_bf;
7.         //先右旋
8.         RotateR(subR);
9.         //在左旋
10.         RotateL(parent);
11.         //更新平衡因子
12.         if (bf == -1)
13.         {   //当新插入的结点是subRL的左边时
14.                 parent->_bf = 0;
15.                 subR->_bf = 1;
16.                 subRL->_bf = 0;
17.         }
18.         else if (bf == 1)
19.         {
20.                 //当新插入的结点时subRL的右边时
21.                 parent->_bf = -1;
22.                 subR->_bf = 0;
23.                 subRL->_bf = 0;
24.         }
25.         else
26.         {
27.                 //特殊情况，当没有其他时，subRL为新插入的结点，那所有的平衡因子最后都是0
28.                 parent->_bf = 0;
29.                 subR->_bf = 0;
30.                 subRL->_bf = 0;
31.         }
32. }

复制代码

 至此，我们学习了右单旋，左单旋，左右双旋，右左双旋
旋转问题总结：

1.为什么当更新平衡因子为1/-1时需要继承往上更新？？？
这是由 AVL 树的平衡性维护机制和高度通报特性决定的
AVL 树的平衡因子依赖于子树高度，而子树高度的变化会向上传播。当插入或删除节点导致某棵子树的高度改变时，其全部祖先节点的平衡因子都大概需要重新盘算。
当某一个结点的左右子树的高度变化时，也就是你变成了1/-1，那这个结点的父节点的高度依赖于该节点的高度，因此父节点的平衡因子也大概需要更新，形成连锁反应。
平衡因子的更新不仅是为了检测失衡，更是为了正确通报子树高度的变化，确保整棵树的高度信息正确，从而维持 AVL 树的平衡性质。
2.为什么当更新为0时就停止更新？？？
由于当某一个结点更新为0时就代表此时以这个结点为子树的高度没有发生变化，那它的父亲就没须要更新
3.什么时间进行右单旋/左单旋/左右双旋/右左双旋？？？
右单旋：失衡的结点平衡因子为-2，此时假如是-2，是不是代表左边高，在判定左子树的平衡因子，假如平衡因子=-1，代表左子树的左边高，就进行右单旋
左单旋：失衡的结点平衡因子为2，代表右边高，判定右子树的平衡因子，假如平衡因子=1，代表右子树的右边高，就进行左单旋
左右双旋：失衡的结点平衡因子为-2，代表左子树高，判定左子树的平衡因子，假如平衡因子=1，代表左子树的右边高，就进行左右双旋
右左双旋：失衡的结点平衡因子为2，代表右子树高，判定右子树的平衡因子，假如平衡因子=-1，代表右子树的左边高，就进行右左双旋
双旋的本质是先调整子树的方向，使失衡节点与子树的 BF 符号划一，再进行单旋。
 

insert：全部细节以讲完毕 

1. bool insert(const pair<K, V>& kv)
2. {
3.         //第一步先找到要插入的位置
4.         if (_root == nullptr)
5.         {
6.                 _root = new Node(kv);
7.                 return true;
8.         }
9.         Node* cur = _root;
10.         Node* parent = nullptr;
11.         while (cur)
12.         {
13.                 if (kv.first > cur->_kv.first)
14.                 {
15.                         //大于往右边找
16.                         parent = cur;
17.                         cur = cur->_right;
18.                 }
19.                 else if (kv.first < cur->_kv.first)
20.                 {   //小于往左边找
21.                         parent = cur;
22.                         cur = cur->_left;
23.                 }
24.                 else
25.                 {
26.                         return false;
27.                 }
28.         }
29.                 cur = new Node(kv);
30.                 if (kv.first > parent->_kv.first)
31.                 {
32.                         parent->_right = cur;
33.                         cur->_parent = parent;
35.                 }
36.                 else
37.                 {
38.                         parent->_left = cur;
39.                         cur->_parent = parent;
40.                 }
42.                 //第二步调整平衡因子
43.                 //平衡因子出现问题只会出现在cur的直系祖宗上
44.                 //平衡因子正常时只会为-1/0/+1（右子树-左子树的高度差）
45.                 while (parent)//往上更新平衡因子，当为根时则更新完毕       
46.                 {
47.                         //更新插入结点的父亲的平衡因子，如果cur是parent的左边则--，反之++（与这个规则有关右子树-左子树的高度差）
48.                         //插入结点cur的平衡因子为0，因为新插入的肯定为叶子结点
49.                         if (cur == parent->_left)
50.                                 parent->_bf--;
51.                         else
52.                                 parent->_bf++;
54.                         //检查父亲的平衡因子
55.                         if (parent->_bf == 0)
56.                         {//如果父亲的平衡因子更新完后为0，则说明之前是+1或者-1，也就是插入的结点并没有影响平衡，弥补了坑位
57.                                 break;
58.                         }
59.                         else if (parent->_bf == 1 || parent->_bf == -1)
60.                         {
61.                                 //说明父亲之前是0，更新完后出现了问题，我们此时要更新parent的parent（一直到_root）
62.                                 parent = parent->_parent;//在进入while循环去更新平衡因子
63.                                 cur = cur->_parent;
64.                         }
65.                         else if (parent->_bf == 2 || parent->_bf == -2)
66.                         {
67.                                 //根据实际情况进行相应的旋转调整
68.                                 if (parent->_bf == 2 && cur->_bf == 1)
69.                                 {
70.                                         RotateL(parent);
71.                                 }
72.                                 else if (parent->_bf == -2 && cur->_bf == -1)
73.                                 {
74.                                         RotateR(parent);
75.                                 }
76.                                 else if (parent->_bf == -2 && cur->_bf == 1)
77.                                 {
78.                                         RotateLR(parent);
79.                                 }
80.                                 else if (parent->_bf == 2 && cur->_bf == -1)
81.                                 {
82.                                         RotateRL(parent);
83.                                 }
84.                                 else
85.                                 {
86.                                         assert(false);
87.                                 }
88.                                 //旋转完结束，就不需要再往上更新了
89.                                 break;
90.                         }
91.                         else
92.                         {
93.                                 //非正常情况
94.                                 assert(false);
95.                         }
96.                 }
97.                 return true;
98. }

复制代码

 AVL树的删除（了解）

由于AVL树也是二叉搜索树，可按照二叉搜索树的方式将结点删除，然后在跟更新平衡因子，只不过删除结点后的平衡因子要更新，最差情况下一直要调整到根节点的位置
1.按搜索树中的规则删除
2.更新平衡因子
3.更新过程中出现平衡因子为-2/2时，则根据情况判定时哪种旋转，进行旋转处理
详细实现可参考《算法导论》或《数据布局-用面向对象方法与C++描述》殷人昆版
AVL树的性能

AVL树一颗绝对平衡的二叉搜索树，其要求每个结点的左右子树高度差的绝对值都不超过1，如许可以保证查询时高效的时间复杂度，即O（logN）。但是假如要对AVL树做一些修改的操作时，性能非常低下，好比：插入时要维护其绝对的平衡，旋转的次数比力多，更差的是在删除时，有大概一直要让旋转连续到根的位置。因此：假如需要一直查询高效且有序的数据布局，而且数据的个数为静态时（既不会改变），可以考虑AVL树，但一个布局经常修改，就不太合适
AVL树的代码实现

June: 这里包含我的c++和Linux及数据布局

https://gitee.com/taifanshu/day2.git已上传gitee，需要可以自行拿取
红黑树

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

红黑树的性质 

1.每个结点的颜色不是赤色就是玄色
2.根节点是玄色的
3.假如一个结点是赤色的，则它的两个孩子结点是玄色的
4.对于每个结点，从该结点到其全部后代叶子结点的简单路径上，均包含相同数目的玄色结点
5.每个叶子结点都是玄色的（此处的叶子结点是指空结点，也就是上图的NULL）
解读性质：第三条可以发现不存在连续的红结点，由于一个红它的孩子必黑
思索问题：为什么满足上述5条性质，红黑树就能保证：其最长路径中结点个数不会超过最短路径结点个数的两倍？
思索最短路径会是什么样？
很显着就是全黑（但你要保证每个结点到叶子结点的黑的个数一样）

在全黑的根本上我们增加赤色结点，且要满足性质的前提下，就是一红一黑一红一黑 
此时增加完最多的赤色结点后，最长路径是最短路径的2倍
红黑树结点的定义 

解释说明 
对于结点的计划根本和AVL树一样，三叉链，键值对，与AVL树不一样的是，AVL树是平衡因子，红黑树是颜色，通过enum枚举类型来计划
enum：是一种编程布局，用于定义一组具名的常量值。它让代码更清晰、安全，得当表现固定的、有限的取值集合。（也就是你把一些全局常量放在一起，用一个enum的命名空间限定，如许会使得更加安全）
红黑树类的定义

红黑树的颜色计划 

思索问题：在结点的定义中，为什么要将结点的默认颜色给赤色？给玄色行不可？赤色有什么优点
RBLTree性质：1.根节点是黑的
                         2.没有连续的红结点
                         3.每个结点到叶节点（NULL）的路径玄色数量一样 
对于先给红，会违反第二条性质，但不会破坏的三条
对于先给黑，会违反第三条性质
对比起来，先给红利益理，给红可以经过局部的调整（通常是旋转和改颜色），而你先给黑，全部经过这条路径的玄色数量都会+1，如许处理起来就是全局的，时间代价高
红黑树的插入 

牢记红黑树的性质：1.根节点是黑的
                                2.没有连续的红结点
                                3.每个结点到叶节点（NULL）的路径玄色数量一样 
第一步：起首按照搜索树的规则进行插入
先进行查找位置，大于往右边，小于往中间，特殊情况：一开始插入是根节点

截至到这里：你的cur已经指向正确位置了，但你没有完成插入工作，此时要解决的时如何连接到红黑树的布局内里
此时你就可以进行链接了，把他的父亲和cur连起来

第二步：也是最紧张的一步，进行改颜色，然后接着维持红黑树的性质 
红黑树的颜色调节（重点难点） 

原理：我们插入的新结点的颜色是赤色的，假如父亲结点的颜色是玄色的，这不会违法红黑树的性质，我们此时不需要更改颜色，假如插入赤色结点，父亲是赤色的，由于不能有连续的赤色结点，所以我们此时需要进行更改颜色
此时需要对红黑树分情况讨论：
约定：cur为当前结点，p为父结点，g为祖父节点，u为叔叔节点
情况一：cur为红，p为红，g为黑，u存在且为红

注意：这些abcde是抽象出来的，这里的树大概是真实的一颗树（也就是它就长如许），也大概是某一棵子树，g大概是某个结点的孩子
对于这种情况，由于有连续的赤色结点，我们肯定需要更改颜色，假如是把cur改为黑，肯定是错的，由于这种违背了每个结点到叶子结点的玄色数量一样，在想一想如何克制连续的赤色结点，是不是只要把g改为红，p和u改为玄色即可，cur不变
解决方案：g改为红，p和u改为黑，cur红

注意：假如这个是一颗完整的树，也就是g它就是根节点，直接把g变为黑即可
假如这个是某个结点的子树，还需要检查g的父亲，假如g的父亲是赤色，需要继承向上调整
最终解决方案：将p和u改为黑，g改为红，然后把g当成cur继承往上调整

情况二：cur为红，p为红，g为黑，u不存在/u为黑 

 说明：u的情况有两种
1.假如u结点不存在，则cur肯定是新插入的结点，由于假如cur不是新插入的结点，则cur和p肯定有一个结点的颜色是玄色的，就不满足性质：每条路径玄色结点个数相同（简单来说就是你的g是叶子结点，由于u不存在也就是null，那是不是证明g是叶子结点，cur）
2.假如u结点存在，则其肯定为玄色的，那么cur节点原来的颜色肯定是玄色的，现在看到其是赤色的缘故原由是由于cur的子树在调整的过程中将cur结点的颜色由玄色变为了赤色，就好比情况一，你向上调整的时间改变了颜色，导致cur变为了红，也就是a，b内里存在玄色结点
处理方案：此时不能简单的通过变色解决问题，需要进行旋转
假如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进行右单旋
此时旋转完是否发现变成了情况二：把cur的名改为p，p的名改为cur，在进行一次右单旋

1.         bool insert(const pair<K,V>& kv)
2.         {
3.                 //RBLTree性质：1.根节点是黑的
4.                 //             2.没有连续的红结点
5.                 //             3.每个结点到叶节点（NULL）的路径黑色数量一样
6.                
7.                 //第一步先按照搜索树的规则进行插入
8.                 if (_root == nullptr)
9.                 {
10.                         _root = new Node(kv);
11.                         _root->_col = BLACK;//保证根结点是黑的
12.                         return true;
13.                 }
14.                 Node* cur = _root;
15.                 Node* parent = cur->_parent;
16.                 while (cur)
17.                 {
18.                         if (kv.first > cur->_kv.first)
19.                         {
20.                                 //大于往右边走
21.                                 parent = cur;
22.                                 cur = cur->_right;
23.                         }
24.                         else if(kv.first<cur->_kv.first)
25.                         {
26.                                 //小于往左边走
27.                                 parent = cur;
28.                                 cur = cur->_left;
29.                         }
30.                         else
31.                         {
32.                                 //相等就退出
33.                                 return false;
34.                         }
35.                 }
36.                 cur = new Node(kv);
37.                 if (kv.first > parent->_kv.first)
38.                 {
39.                         //大于链接右边
40.                         parent->_right = cur;
41.                         cur->_parent = parent;
42.                 }
43.                 else
44.                 {
45.                         //小于链接左边
46.                         parent->_left = cur;
47.                         cur->_parent = parent;
48.                 }
50.                 //第二步调颜色
51.                 //先给红的，这会破环第二条规则，但是如果都给黑的，会破坏第三条规则，这对比起来全给黑的不好调
52.                 //先给红的好调
53.                 cur->_col = RED;
55.                 //以下三种情况的调节其实是看叔叔（U）
56.        
57.                 //第一种情况：cur是红的，父亲p是红的，祖父g是黑的，叔叔u存在且是红的
58.                 //p u变黑，cur红，g红
59.                 //这样变能够保证没有连续的红，且如果这是一颗子树的话能确保每条路径上的黑色结点不变
60.                 //如果g是根，把g变会黑即可，如果g不是根，要考虑g的p是否为红
61.                 // 如果g的p是黑的则结束，如果g的p是红的，继续以此方式往上处理
62.                 while (parent&&parent->_col == RED)//父亲存在且为红（祖父一定是黑），当父亲存在为黑时不需要处理
63.                 {
64.                         Node* grandfather = parent->_parent;//一定有它，因为父亲是红的，证明父亲不是根
65.                         if (grandfather->_left == parent)
66.                         {
67.                                 Node* uncle = grandfather->_right;
68.                                 if (uncle && uncle->_col == RED)
69.                                 {
70.                                         //情况1：如果unclu存在且为红的
71.                                         parent->_col = BLACK;
72.                                         uncle->_col = BLACK;
73.                                         grandfather->_col = RED;
74.                                         cur = grandfather;
75.                                         parent = cur->_parent;//接着往上调
76.                                 }
77.                                 else
78.                                 {   //情况2：如果unclu不存在或存在且为黑的
79.                                         //第二种情况：cur是红的，p为红的，g为黑的，u不存在或者为黑
80.                                         //如果u不存在，那么cur肯定是新增结点
81.                                         //如果u存在，那么cur肯定不是新增结点，且cur是作为下面的祖父，因为下面的变化也就是情况1，导致cur变成红
82.                                         //处理方式 单旋加变色（直线）
84.                                         // 情况3：如果unclu不存在或存在且为黑的
85.                                         //第三种情况：cur为红，p为红，g为黑，u不存在或u为黑
86.                                         //如果u存在，那么cur肯定不是新增结点，且cur是作为下面的祖父，因为下面的变化也就是情况1，导致cur变成红
87.                                         //处理方式：先双旋在变色（折线）
89.                                         //上面的大情况是父亲是祖父的左边
90.                                         //如果cur是父亲的左边只要进行单旋即可（情况二），如果cur是父亲的右边就双旋（情况三）
91.                                         if (cur == parent->_right)
92.                                         {
93.                                                 //先进行左单旋
94.                                                 RotateL(parent);
95.                                                 swap(parent, cur);//交换位置，把第三种情况进行单旋后归为第二种情况，但是parent和cur跟第二种情况不一样
96.                                         }
98.                                         //全部都是第二种情况（有可能是由第三种情况变来的）
99.                                         RotateR(grandfather);
100.                                         grandfather->_col = RED;
101.                                         parent->_col = BLACK;
102.                                         break;
103.                                 }
104.                         }
105.                         else//grandfather->right==parent
106.                         {
107.                                 Node* uncle = grandfather->_left;
108.                                 if (uncle && uncle->_col == RED)
109.                                 {
110.                                         //情况1：如果unclu存在且为红的
111.                                         parent->_col = BLACK;
112.                                         uncle->_col = BLACK;
113.                                         grandfather->_col = RED;
114.                                         cur = grandfather;
115.                                         parent = cur->_parent;//接着往上调
116.                                 }
117.                                 else
118.                                 {
119.                                         if (cur == parent->_left)
120.                                         {
121.                                                 //先进行右单旋
122.                                                 RotateR(parent);
123.                                                 swap(parent, cur);//交换位置，把第三种情况进行单旋后归为第二种情况，但是parent和cur跟第二种情况不一样
124.                                         }
126.                                         //全部都是第二种情况（有可能是由第三种情况变来的）
127.                                         RotateL(grandfather);
128.                                         grandfather->_col = RED;
129.                                         parent->_col = BLACK;
130.                                         break;
131.                                 }
132.                                  
133.                         }
134.                 }
135.                 _root->_col = BLACK;//保证根是黑色的
136.                 return true;
138.         }

复制代码

总结颜色调节方案

红黑树的颜色调节是维护其平衡性质的核心机制，重要通过颜色变更和旋转操作来修复插入或删除后大概违反的红黑树性质
其实分了这么多类，到头来是否发现都是根据uncle来划分的，也就是分uncle存不存在，存在的话是什么颜色？？？
那就可以分三类，u存在为红，u存在为黑，u不存在
当u存在且为红时：把g改为红，u和p改为红，cur为红，假如g为根节点就改为黑，假如g不是根节点就向上接着调整（由于g的p肯定是赤色，由于g的p是玄色的话就不满足性质四）
当u存在且为黑时：进行旋转操作，详细是左旋还是右旋需要根据cur是p的左边还是右边详细划分
当u不存在时：进行旋转操作，详细是左旋还是右旋需要根据cur是p的左边还是右边详细划分
注意：旋转的位置是那里
红黑树的模拟实现

June: 这里包含我的c++和Linux及数据布局

https://gitee.com/taifanshu/day2.git已上传gitee，需要可以自行拿取
红黑树的删除

可以进行参考《算法导论》或者《STL源码刨析》
 红黑树 - _Never_ - 博客园
红黑树的性能

增删查改：最短路径O(logN)，最长路径2*O（logN），但对于现代盘算机速度来说，可以忽略
红黑树的应用

http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html
红黑树与AVL树的比力

红黑树和AVL树都是高效的平衡二叉树，增删查改的时间复杂度都是O（logN），红黑树不寻求绝对的平衡，其只需要保证最长路径不超过最短路径的2倍，而AVL树是高度平衡的二叉搜索树，它的左右子树的平衡因子的绝对值维持在小于等于1，如许也就导致它在插入时需要进行多次旋转，而红黑树的旋转次数相比AVL树来说低落了，所以在经常进行增删的布局中性能比AVL树更优，而且红黑树实现比力简单，所以实际运用中红黑树更多
map和set的模拟实现

June: 这里包含我的c++和Linux及数据布局

https://gitee.com/taifanshu/day2.git已上传gitee，需要可以自行拿取
重点学习迭代器











免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告