C，红黑树一.红黑树的概念和性质1.红黑树的概念和性质2.AVL树和红黑树的区别二.咱们要成功的大抵框架1.红黑树节点的定义2.为什么新节点自动是白色?1.共识2.新节点是彩色的坏处3.新节点是白色的好处三.红黑树的拔出1.拔出逻辑跟BST相反的那一局部2.分类探讨拔出逻辑1.新拔出节点的父亲是彩色2.新拔出节点的父亲是白色1.详细...。

C++红黑树

• 一.红黑树的概念和性质
• • 1.红黑树的概念和性质
  • 2.AVL树和红黑树的区别
• 二.咱们要成功的大抵框架
• • 1.红黑树节点的定义
  • 2.为什么新节点自动是白色?
  • • 1.共识
    • 2.新节点是彩色的坏处
    • 3.新节点是白色的好处
• 三.红黑树的拔出
• 1.拔出逻辑跟BST相反的那一局部
• 2.分类探讨拔出逻辑
• • 1.新拔出节点的父亲是彩色
  • 2.新拔出节点的父亲是白色
  • • 1.详细分类的说明
    • 2.新拔出节点的叔叔存在是白色
    • • 1.说明:
      • 2.动图展示
      • 3.总结:
    • 3.新拔出节点的叔叔不存在或许存在是彩色
    • • 1.叔叔是祖父的右孩子
      • • 1.说明
          • 2.旋转打算
          • • 1.cur是parent的左孩子(右旋)
              • 2.cur是parent的右孩子(左右双旋)
      • 2.叔叔是祖父的左孩子
      • • 1.cur是parent的右孩子(左旋)
          • 2.cur是parent的左孩子(右左双旋)
      • 3.叔叔不存在
      • 4.总结:
• 3.拔出代码
• 四.红黑树的验证

• 五.完整代码

  前置说明:
  须要学习AVL树的旋转之后再来看红黑树的旋转
  由于红黑树的旋转是复用的AVL树的旋转的:
  大家可以看我的这篇博客,外面详细引见了AVL树的四种旋转
  C++ AVL树(四种旋转,拔出)

  一.红黑树的概念和性质

1.红黑树的概念和性质

2.AVL树和红黑树的区别

二.咱们要成功的大抵框架

1.红黑树节点的定义

关于色彩咱们驳回枚举类型定义
关于红黑树节点,照旧驳回Key-Value模型存储pair

enum ColorREDBLACKtemplateclass Kclass V
struct RBTreeNodeRBTreeNodeKV _pLeftRBTreeNodeKV _pRightRBTreeNodeKV _pParentColor _colorpairKV _data//新拔出的节点自动是白色RBTreeNodeconst pairKV>)_pLeftnullptr_pRightnullptr_pParentnullptr_colorRED_datadata

2.为什么新节点自动是白色?

1.共识

首先咱们要达成一个共识:

关于性质3和性质4,假设非要违犯一个的话
咱们选用违犯性质3,而不是性质4
由于:
违犯性质3还可以经过变色和旋转的模式来处置
而违法性质4的话,其余一切门路都要从新修正

因此违法性质3的损失更小,调整更便捷
违法性质4…结果显而易见…

2.新节点是彩色的坏处

拔出之前:

拔出环节:

拔出之后:

3.新节点是白色的好处

拔出之前:

拔出环节:

拔出之后:

三.红黑树的拔出

1.拔出逻辑跟BST相反的那一局部

上方是跟BST普通二叉搜查树的拔出逻辑相反的那局部
惟一不太相反的是把根节点的色彩改成彩色了而已

bool Insertconst pairKV>)if _pRoot  nullptr_pRoot  new Nodedata//根节点是彩色_pRoot_color  BLACKreturn trueNode cur  _pRoot  parent  nullptrwhile cur//比我小,往左找if datafirst  cur_datafirstparent  curcur  cur_pLeft//比我大,往右找else if datafirst  cur_datafirstparent  curcur  cur_pRight//有重复元素,拔出失败elsereturn false//找到空位置,开局拔出cur  new Nodedata//衔接父亲和孩子if cur_datafirst  parent_datafirstparent_pLeft  curelseparent_pRight  curcur_pParent  parent//开局探讨节点色彩疑问return true

2.分类探讨拔出逻辑

引见了新拔出的节点必定是白色之后
咱们就可以分状况探讨了

1.新拔出节点的父亲是彩色

由于红黑树的性质3:一切白色节点的孩子不能是白色节点
这也就说明了红黑树不能存在延续的白色节点

2.新拔出节点的父亲是白色

1.详细分类的说明

上方咱们就对叔叔启动分类探讨

2.新拔出节点的叔叔存在是白色

1.说明:

这里以叔叔是祖父的右孩子为例展示
其实叔叔是祖父的左孩子的话是如出一辙的,就不再赘述了

2.动图展示

拔出前:

调整环节:

调整之后:

刚才一开局时展示的是:
cur是新增节点时的状况
然而两边环节借由祖父向上继续调整修正时,咱们就曾经能看出即使cur不是新增节点,调整模式和逻辑也是如出一辙的!!

3.总结:

3.新拔出节点的叔叔不存在或许存在是彩色

刚才的那种状况只有要变色即可
如今就须要旋转+变色了
跟AVL树的旋转相似,依然是分为4种状况
依然是画形象图来了解
画图外面规则:
p:代表parent,父亲
c:代表cur,孩子
g:grandParent,祖父
u:uncle,叔叔
a,b,c,d,e代表红黑树或许空节点
ar:ancestor:祖父的父亲

1.叔叔是祖父的右孩子

1.说明

1.uncle存在且为黑时:cur必定不是新增节点

2.为什么不能依照之前的模式只去修正色彩

2.旋转打算

1.cur是parent的左孩子(右旋)

修正之前:

修正环节:

这里是对g启动右旋,动图外面刚才写错了,道歉
修正之后:

修正之后没有违犯性质3

上方咱们对照一下修正之前和修正之后,看看能否违犯了性质4

没有违犯,完美的一次性修正

2.cur是parent的右孩子(左右双旋)

旋转之前:

旋转环节:

旋转之后:

修正之后没有违犯性质3

上方咱们对照一下修正之前和修正之后,看看能否违犯了性质4

完美修正

2.叔叔是祖父的左孩子

跟叔叔是祖父的右孩子就特意像了,间接给动图了

1.cur是parent的右孩子(左旋)

旋转之前:

旋转环节:

旋转之后:

2.cur是parent的左孩子(右左双旋)

旋转之前:

旋转环节:

旋转之后:

3.叔叔不存在

以右旋为例:
旋转之前:

旋转环节:

旋转之后:

以左右双旋为例:
旋转之前:

旋转环节:

旋转之后:

4.总结:

调整色彩的总结:

3.拔出代码

// 在红黑树中拔出值为data的节点，拔出成功前往true，否则前往false
// 留意：为了便捷起见，本次成功红黑树不存储重复性元素
bool Insertconst pairKV>)if _pRoot  nullptr_pRoot  new Nodedata//根节点是彩色_pRoot_color  BLACKreturn trueNode cur  _pRoot  parent  nullptrwhile cur//比我小,往左找if datafirst  cur_datafirstparent  curcur  cur_pLeft//比我大,往右找else if datafirst  cur_datafirstparent  curcur  cur_pRight//有重复元素,拔出失败elsereturn false//找到空位置,开局拔出cur  new Nodedata//衔接父亲和孩子if cur_datafirst  parent_datafirstparent_pLeft  curelseparent_pRight  curcur_pParent  parent//父亲是彩色,拔出成功if parent_color  BLACKreturn true//父亲是白色,须要调整//且此时爷爷必定是彩色//依据叔叔的色彩来调整while parent  parent_color  REDNode grandParent  parent_pParent//爸爸是爷爷的左孩子if parent  grandParent_pLeftNode uncle  grandParent_pRight//依据叔叔的色彩来调整//1.叔叔存在且为红if uncle  uncle_color  RED//修正爸爸,叔叔,爷爷的色彩uncle_color  parent_color  BLACKgrandParent_color  RED//此时视爷爷为新拔出的白色节点继续向上影响cur  grandParentparent  cur_pParent//2.叔叔不存在或许叔叔是黑else//1.我是爸爸的左孩子if parent_pLeft  cur//对爷爷启动一次性右旋RotateRgrandParent//把爷爷改成白色,爸爸改成彩色grandParent_color  REDparent_color  BLACK//此时爸爸是彩色,无需break,当然break也可以,因此爸爸是彩色,下次循环就不会进入了//2.我是爸爸的右孩子else<img alt="C" loading="lazy" src="https://pic3.zhimg.com/v2-9b0cdf3043fe36e278c6f0267a507d89_r.jpg"></img>//1.对爸爸启动左旋RotateLparent//2.对爷爷右旋RotateRgrandParent//3.孩子改成彩色,爷爷改成白色cur_color  BLACKgrandParent_color  RED//4.必定要break,假设不break的话,由于爸爸是白色,所以循环会继续,此时就乱套了break//爸爸是爷爷的右孩子elseNode uncle  grandParent_pLeft//1.叔叔存在且为红if uncle  uncle_color  REDuncle_color  parent_color  BLACKgrandParent_color  REDcur  grandParentparent  cur_pParent//2.叔叔不存在或许叔叔为黑else//1.我是爸爸的右孩子if parent_pRight  cur//对爷爷左旋RotateLgrandParent//爷爷改成白色,爸爸改成彩色grandParent_color  REDparent_color  BLACK//此时爸爸是彩色,无需break,当然break也可以,因此爸爸是彩色,下次循环就不会进入了//2.我是爸爸的左孩子else//1.对爸爸右旋RotateRparent//2.对爷爷左旋RotateLgrandParent//3.把孩子改成彩色,爷爷改成白色cur_color  BLACKgrandParent_color  RED//4.必定要break,假设不break的话,由于爸爸是白色,所以循环会继续,此时就乱套了break_pRoot_color  BLACKreturn true

四.红黑树的验证

templateclass Kclass V
class RBTreetypedef RBTreeNodeKV Node
public// 检测红黑树中能否存在关键字为key的节点，存在前往该节点的地址，否则前往nullptrNode Findconst K keyNode cur  _pRootwhile curif cur_datafirst  keycur  cur_pLeftelse if cur_datasecond  keycur  cur_pRightelsereturn curreturn nullptr// 检测红黑树能否为有效的红黑树，留意：其外部关键依托_IsValidRBTRee函数检测bool IsValidRBTRee//1.空树是红黑树if _pRoot  nullptrreturn true//2.根节点不能为白色if _pRoot_color  REDreturn false//3.为了验证性质: 红黑树的恣意一条门路上的彩色节点个数相反   找参考值size_t ReferenceCount  0Node cur  _pRootwhile curif cur_color  BLACKReferenceCountcur  cur_pLeftreturn _IsValidRBTRee_pRoot 0 ReferenceCountprivatebool _IsValidRBTReeNode pRoot size_t blackCount size_t ReferenceCountif pRoot  nullptrif blackCount  ReferenceCountcout  "存在彩色节点数量不相等的门路"  endlreturn falsereturn true//验证性质: 红黑树中不能存在延续的白色节点//假设一个节点是白色,该节点必定不是根节点,因此该节点必定有父亲//只有要保障白色节点的父亲不是白色节点即可if pRoot_color  REDif pRoot_pParent_color  REDcout  "存在延续的白色节点"  endlreturn falseelseblackCountreturn _IsValidRBTReepRoot_pLeft blackCount ReferenceCount  _IsValidRBTReepRoot_pRight blackCount ReferenceCountprivateNode _pRoot  nullptr

五.完整代码

1.RBTree.h

pragma once
enum ColorREDBLACKtemplateclass Kclass V
struct RBTreeNodeRBTreeNodeKV _pLeftRBTreeNodeKV _pRightRBTreeNodeKV _pParentColor _colorpairKV _data//新拔出的节点自动是白色RBTreeNodeconst pairKV>)_pLeftnullptr_pRightnullptr_pParentnullptr_colorRED_datadatatemplateclass Kclass V
class RBTreetypedef RBTreeNodeKV Node
public// 在红黑树中拔出值为data的节点，拔出成功前往true，否则前往false// 留意：为了便捷起见，本次成功红黑树不存储重复性元素bool Insertconst pairKV>)if _pRoot  nullptr_pRoot  new Nodedata//根节点是彩色_pRoot_color  BLACKreturn trueNode cur  _pRoot  parent  nullptrwhile cur//比我小,往左找if datafirst  cur_datafirstparent  curcur  cur_pLeft//比我大,往右找else if datafirst  cur_datafirstparent  curcur  cur_pRight//有重复元素,拔出失败elsereturn false//找到空位置,开局拔出cur  new Nodedata//衔接父亲和孩子if cur_datafirst  parent_datafirstparent_pLeft  curelseparent_pRight  curcur_pParent  parent//父亲是彩色,拔出成功if parent_color  BLACKreturn true//父亲是白色,须要调整//且此时爷爷必定是彩色//依据叔叔的色彩来调整while parent  parent_color  REDNode grandParent  parent_pParent//爸爸是爷爷的左孩子if parent  grandParent_pLeftNode uncle  grandParent_pRight//依据叔叔的色彩来调整//1.叔叔存在且为红if uncle  uncle_color  RED//修正爸爸,叔叔,爷爷的色彩uncle_color  parent_color  BLACKgrandParent_color  RED//此时视爷爷为新拔出的白色节点继续向上影响cur  grandParentparent  cur_pParent//2.叔叔不存在或许叔叔是黑else//1.我是爸爸的左孩子if parent_pLeft  cur//对爷爷启动一次性右旋RotateRgrandParent//把爷爷改成白色,爸爸改成彩色grandParent_color  REDparent_color  BLACK//此时爸爸是彩色,无需break,当然break也可以,因此爸爸是彩色,下次循环就不会进入了//2.我是爸爸的右孩子else//1.对爸爸启动左旋RotateLparent//2.对爷爷右旋RotateRgrandParent//3.孩子改成彩色,爷爷改成白色cur_color  BLACKgrandParent_color  RED//4.必定要break,假设不break的话,由于爸爸是白色,所以循环会继续,此时就乱套了break//爸爸是爷爷的右孩子elseNode uncle  grandParent_pLeft//1.叔叔存在且为红if uncle  uncle_color  REDuncle_color  parent_color  BLACKgrandParent_color  REDcur  grandParentparent  cur_pParent//2.叔叔不存在或许叔叔为黑else//1.我是爸爸的右孩子if parent_pRight  cur//对爷爷左旋RotateLgrandParent//爷爷改成白色,爸爸改成彩色grandParent_color  REDparent_color  BLACK//此时爸爸是彩色,无需break,当然break也可以,因此爸爸是彩色,下次循环就不会进入了//2.我是爸爸的左孩子else//1.对爸爸右旋RotateRparent//2.对爷爷左旋RotateLgrandParent//3.把孩子改成彩色,爷爷改成白色cur_color  BLACKgrandParent_color  RED//4.必定要break,假设不break的话,由于爸爸是白色,所以循环会继续,此时就乱套了break_pRoot_color  BLACKreturn true// 检测红黑树中能否存在关键字为key的节点，存在前往该节点的地址，否则前往nullptrNode Findconst K keyNode cur  _pRootwhile curif cur_datafirst  keycur  cur_pLeftelse if cur_datasecond  keycur  cur_pRightelsereturn curreturn nullptr// 检测红黑树能否为有效的红黑树，留意：其外部关键依托_IsValidRBTRee函数检测bool IsValidRBTRee//1.空树是红黑树if _pRoot  nullptrreturn true//2.根节点不能为白色if _pRoot_color  REDreturn false//3.为了验证性质: 红黑树的恣意一条门路上的彩色节点个数相反   找参考值size_t ReferenceCount  0Node cur  _pRootwhile curif cur_color  BLACKReferenceCountcur  cur_pLeftreturn _IsValidRBTRee_pRoot 0 ReferenceCountvoid InOrder_InOrder_pRootprivatebool _IsValidRBTReeNode pRoot size_t blackCount size_t ReferenceCountif pRoot  nullptrif blackCount  ReferenceCountcout  "存在彩色节点数量不相等的门路"  endlreturn falsereturn true//验证性质: 红黑树中不能存在延续的白色节点//假设一个节点是白色,该节点必定不是根节点,因此该节点必定有父亲//只有要保障白色节点的父亲不是白色节点即可if pRoot_color  REDif pRoot_pParent_color  REDcout  "存在延续的白色节点"  endlreturn falseelseblackCountreturn _IsValidRBTReepRoot_pLeft blackCount ReferenceCount  _IsValidRBTReepRoot_pRight blackCount ReferenceCount// 右单旋void RotateRNode pParentNode subL  pParent_pLeftNode subLR  subL_pRightNode grandParent  pParent_pParentsubL_pRight  pParentpParent_pParent  subLpParent_pLeft  subLRif subLRsubLR_pParent  pParentif grandParent  nullptr_pRoot  subL_pRoot_pParent  nullptrelseif pParent  grandParent_pLeftgrandParent_pLeft  subLelsegrandParent_pRight  subLsubL_pParent  grandParent// 左单旋void RotateLNode pParentNode subR  pParent_pRightNode subRL  subR_pLeftNode grandParent  pParent_pParentpParent_pParent  subRsubR_pLeft  pParentpParent_pRight  subRLif subRLsubRL_pParent  pParent//说明此时pParent是_pRootif grandParent  nullptr_pRoot  subR_pRoot_pParent  nullptr//说明此时pParent所在的树是一颗子树,须要跟父亲链接elseif pParent  grandParent_pLeftgrandParent_pLeft  subRelsegrandParent_pRight  subRsubR_pParent  grandParentvoid _InOrderNode rootif root  nullptr return_InOrderroot_pLeftcout  root_datafirst    root_datasecond  _InOrderroot_pRightprivateNode _pRoot  nullptr

2.test.cpp

include <iostream>
using namespace std
include <assert.h>
include "RBtree1.h"
include <vector>
void test1int a   16 3 7 11 9 26 18 14 15 //int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTreeint int tfor auto e  atInsertmake_paire etInOrdercout  endlcout  tIsValidRBTRee  endlvoid test2const int N  10000000vectorint vvreserveNsrandtime0for size_t i  0 i  N ivpush_backrand  isize_t begin2  clockRBTreeint int tfor auto e  vtInsertmake_paire esize_t end2  clockcout  tIsValidRBTRee  endlint maintest2return 0

验证终了