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//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
验证终了
还没有评论,来说两句吧...