360建站公司,用网站做的简历,网上购物的好处,大良营销网站建设咨询目录
一、红黑树的概念
编辑二、红黑树的性质
三、红黑树节点的定义
四、红黑树结构
五、红黑树的插入操作
5.1. 按照二叉搜索的树规则插入新节点
5.2、检测新节点插入后#xff0c;红黑树的性质是否造到破坏 情况一: cur为红#xff0c;p为红#xff0c;g为黑红黑树的性质是否造到破坏 情况一: cur为红p为红g为黑u存在且为红
情况二: cur为红p为红g为黑u不存在/u为黑
情况三: cur为红p为红g为黑u不存在/u为黑
六、红黑树的验证
七、红黑树与AVL树的比较
八、key结构红黑树整体代码
九、keyvalue 结构红黑树整体代码 一、红黑树的概念 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 二、红黑树的性质 1. 每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的则它的两个孩子结点是黑色的 4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 三、红黑树节点的定义 红黑树的节点我们这里使用的是三叉链方便对后面内容的操作 首先我们定义了一个枚举常量来表示红黑树节点的颜色 其次定义节点一个红黑树的节点包含左孩子右孩子父节点数据颜色 接着我们定义构造函数对其节点数据进行初始化左右孩子和父节点置空插入的颜色默认为红色数据为传入的数据。 enum COLOR
{BLACK,RED
};
template class T
struct RBNode
{RBNodeT* _left;RBNodeT* _right;RBNodeT* _parent;T _value;COLOR _color;//颜色RBNode(const T valueT()):_left(nullptr), _right(nullptr), _parent(nullptr), _value(value), _color(RED){}
};
四、红黑树结构 为了后续封装map和set简单一些在红黑树的实现中增加一个头结点因为根节点必须为黑色为了与根节点进行区分将头结点给成黑色并且让头结点的 pParent 域指向红黑树的根节点pLeft域指向红黑树中最小的节点_pRight域指向红黑树中最大的节点如下 五、红黑树的插入操作
相比于AVL树插入比较简单效率比较高红黑树比AVL树的调整次数要少。
红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步 1. 按照二叉搜索的树规则插入新节点 2.检测新节点插入后红黑树的性质是否造到破坏有破坏进行调整 5.1. 按照二叉搜索的树规则插入新节点
bool Insert(const T value){// 1. 按照二叉搜索的树方式插入新节点//搜索树的插入if (_header-_parent nullptr){//空树创建根节点pNode root new Node(value);root-_color BLACK;root-_parent _header;_header-_parent root;_header-_left root;_header-_right root;return true;}//从根开始搜索pNode cur _header-_parent;pNode parent nullptr;//查找插入的位置while (cur){parent cur;//按照key值确定位置, key不能重复if (cur-_value value)return false;else if (cur-_value value)cur cur-_left;elsecur cur-_right;}//节点创建cur new Node(value);//节点插入if (parent-_value cur-_value)parent-_left cur;elseparent-_right cur;//节点连接cur-_parent parent;//while()// {// 2. 检测新节点插入后红黑树的性质是否造到破坏// 若满足直接退出否则对红黑树进行旋转着色处理//}// 根节点的颜色可能被修改将其改回黑色_header-_parent-_color BLACK;//更新 _header-_left, _header-_right_header-_left leftMost();_header-_right rightMost();return true;}
5.2、检测新节点插入后红黑树的性质是否造到破坏 因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论 约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点 情况一: cur为红p为红g为黑u存在且为红 注意::此时看到的树又可能是一颗完整的树也有可能是一颗子树 如果g是根节点调整完成后需要把根节点改为黑色 如果g是子树g一定有双亲父亲和叔叔如果g的双亲为红色则继续往上调整 解决方式将pu改为黑g改为红然后把g当作cur继续往上调整直至cur为根节点根为黑
情况二: cur为红p为红g为黑u不存在/u为黑 说明 U有俩种情况 1.如果U节点不存在则cur一定是新插入的节点因为如果cur不为新插入的节点则cur和p一定有一个节点的颜色为黑色就不满足性质4每条路径黑色节点相同 2.如果U节点存在则其一定是黑色的那么cue节点原来的颜色一定是黑色的现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改为红色。 解决方式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做右单旋转 则转换成了情况2
bool insert(const T value){//搜索树的插入if (_header-_parent nullptr){//空树创建根节点pNode root new Node(value);root-_color BLACK;root-_parent _header;_header-_parent root;_header-_left root;_header-_right root;return true;}//从根开始搜索pNode cur _header-_parent;pNode parent nullptr;//查找插入的位置while (cur){parent cur;//按照key值确定位置, key不能重复if (cur-_value value)return false;else if (cur-_value value)cur cur-_left;elsecur cur-_right;}//节点创建cur new Node(value);//节点插入if (parent-_value cur-_value)parent-_left cur;elseparent-_right cur;//节点连接cur-_parent parent;//调整和更新颜色连续红色需要调整while (cur ! _header-_parent cur-_parent-_color RED)//当前不是根并且你的父亲是红色{//cur:当前节点parent:父亲节点 gfather祖父节点uncle:叔叔节点parent cur-_parent;pNode gfather parent-_parent;if (gfather-_left parent){pNode uncle gfather-_right;//uncle 存在且为红if (uncle uncle-_color RED){//修改颜色parent-_color uncle-_color BLACK;gfather-_color RED;//继续向上更新cur gfather;}else{//如果存在双旋的场景可以先进行一次单旋使它变成单旋的场景if (cur parent-_right){RotateL(parent);swap(cur, parent);}//右旋RotateR(gfather);//修改颜色parent-_color BLACK;gfather-_color RED;//停止调整break;}}//gfather-_right parentelse{pNode uncle gfather-_left;if (uncle uncle-_color RED){//修改颜色uncle-_color parent-_color BLACK;gfather-_color RED;cur gfather;}else{//判断是否有双旋的场景if (cur parent-_left){//以parent右旋RotateR(parent);//交换指针swap(cur, parent);}//以gfather 左旋RotateL(gfather);//修改颜色parent-_color BLACK;gfather-_color RED;//停止调整break;}}}//根的颜色始终是黑的 根_header-_parent_header-_parent-_color BLACK;//更新 _header-_left, _header-_right_header-_left leftMost();_header-_right rightMost();return true;}
六、红黑树的验证
红黑树的检测分为两步 1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列) 2. 检测其是否满足红黑树的性质 bool isRBTree(){pNode root _header-_parent;if (root nullptr)return true;if (root-_color RED){cout 根节点必须是黑色的!!! endl;return false;}//根节点是黑色//需要判断每条路径上黑色个数相同//可以先任意遍历一条路径 比如走最右路径。查找black数量pNode cur root;int blackCount 0;while (cur){if (cur-_color BLACK)blackCount;cur cur-_right;}int k 0;return _isRBTree(root, k, blackCount);}bool _isRBTree(pNode root, int curBlackCount, int totalBlackCout)//curBlackCount:走到当前节点黑色个数{//每条路径上黑色个数相同//没有连续红色结点//一条路径走完if (root nullptr){if (curBlackCount ! totalBlackCout){cout 每条路径-黑色结点个数不同 endl;return false;}return true;}if (root-_color BLACK)curBlackCount;//没有红色连续pNode parent root-_parent;if (parent-_color RED root-_color RED){cout 有连续的红色结点 endl;return false;}return _isRBTree(root-_left, curBlackCount, totalBlackCout) _isRBTree(root-_right, curBlackCount, totalBlackCout);}
七、红黑树与AVL树的比较 红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O( )红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。
八、key结构红黑树整体代码
#define _CRT_SECURE_NO_WARNINGS 1
#includetime.h
#includeutility
#includeiostream
using namespace std;
enum COLOR
{BLACK,RED
};
template class T
struct RBNode
{RBNodeT* _left;RBNodeT* _right;RBNodeT* _parent;T _value;COLOR _color;//颜色RBNode(const T valueT()):_left(nullptr), _right(nullptr), _parent(nullptr), _value(value), _color(RED){}
};template class T
class RBTree
{
public:typedef RBNodeT Node;typedef Node* pNode;RBTree(){//构建空的红黑树 空树--》带头的红黑树头不是根_header new Node;_header-_left _header;_header-_right _header;}/*红黑树插入1.相对于AVL树插入比较简单且效率高红黑树比AVL树调整次数要少2.二叉树进行插入3.判断有没有连续的红色结点如果有a:只需要修改颜色 uncle为红色b:修改颜色旋转u不存在、存在且为黑单旋cur,parent在gfather的同一边双旋cur,parent不在gfather的同一边首先经过一次单璇交换指针转化为上面单璇场景没有不需要做任何操作插入结束。*/bool insert(const T value){//搜索树的插入if (_header-_parent nullptr){//空树创建根节点pNode root new Node(value);root-_color BLACK;root-_parent _header;_header-_parent root;_header-_left root;_header-_right root;return true;}//从根开始搜索pNode cur _header-_parent;pNode parent nullptr;//查找插入的位置while (cur){parent cur;//按照key值确定位置, key不能重复if (cur-_value value)return false;else if (cur-_value value)cur cur-_left;elsecur cur-_right;}//节点创建cur new Node(value);//节点插入if (parent-_value cur-_value)parent-_left cur;elseparent-_right cur;//节点连接cur-_parent parent;//调整和更新颜色连续红色需要调整while (cur ! _header-_parent cur-_parent-_color RED)//当前不是根并且你的父亲是红色{//cur:当前节点parent:父亲节点 gfather祖父节点uncle:叔叔节点parent cur-_parent;pNode gfather parent-_parent;if (gfather-_left parent){pNode uncle gfather-_right;//uncle 存在且为红if (uncle uncle-_color RED){//修改颜色parent-_color uncle-_color BLACK;gfather-_color RED;//继续向上更新cur gfather;}else{//如果存在双旋的场景可以先进行一次单旋使它变成单旋的场景if (cur parent-_right){RotateL(parent);swap(cur, parent);}//右旋RotateR(gfather);//修改颜色parent-_color BLACK;gfather-_color RED;//停止调整break;}}//gfather-_right parentelse{pNode uncle gfather-_left;if (uncle uncle-_color RED){//修改颜色uncle-_color parent-_color BLACK;gfather-_color RED;cur gfather;}else{//判断是否有双旋的场景if (cur parent-_left){//以parent右旋RotateR(parent);//交换指针swap(cur, parent);}//以gfather 左旋RotateL(gfather);//修改颜色parent-_color BLACK;gfather-_color RED;//停止调整break;}}}//根的颜色始终是黑的 根_header-_parent_header-_parent-_color BLACK;//更新 _header-_left, _header-_right_header-_left leftMost();_header-_right rightMost();return true;}pNode leftMost(){pNode cur _header-_parent;while (cur cur-_left ! nullptr){cur cur-_left;}return cur;}pNode rightMost(){pNode cur _header-_parent;while (cur cur-_right ! nullptr){cur cur-_right;}return cur;}void RotateR(pNode parent){pNode subL parent-_left;pNode subLR subL-_right;// 1subL-_right parent;// 2parent-_left subLR;// 3if (subLR)subLR-_parent parent;// 4, 5if (parent ! _header-_parent){// subL --- parent-parentpNode gParent parent-_parent;if (gParent-_left parent)gParent-_left subL;elsegParent-_right subL;subL-_parent gParent;}else{//更新根节点_header-_parent subL;//subL-_parent nullptr;subL-_parent _header;}// 6parent-_parent subL;}void RotateL(pNode parent){pNode subR parent-_right;pNode subRL subR-_left;subR-_left parent;parent-_right subRL;if (subRL)subRL-_parent parent;if (parent ! _header-_parent) {pNode gParent parent-_parent;if (gParent-_left parent)gParent-_left subR;elsegParent-_right subR;subR-_parent gParent;}else{_header-_parent subR;//根的父节点不是nullptr//subR-_parent nullptr;subR-_parent _header;}parent-_parent subR;}void inOrder(){_inOrder(_header-_parent);}void _inOrder(pNode root){if (root) {_inOrder(root-_left);cout root-_valueendl;_inOrder(root-_right);}}bool isRBTree(){pNode root _header-_parent;if (root nullptr)return true;if (root-_color RED){cout 根节点必须是黑色的!!! endl;return false;}//根节点是黑色//需要判断每条路径上黑色个数相同//可以先任意遍历一条路径 比如走最右路径。查找black数量pNode cur root;int blackCount 0;while (cur){if (cur-_color BLACK)blackCount;cur cur-_right;}int k 0;return _isRBTree(root, k, blackCount);}bool _isRBTree(pNode root, int curBlackCount, int totalBlackCout)//curBlackCount:走到当前节点黑色个数{//每条路径上黑色个数相同//没有连续红色结点//一条路径走完if (root nullptr){if (curBlackCount ! totalBlackCout){cout 每条路径-黑色结点个数不同 endl;return false;}return true;}if (root-_color BLACK)curBlackCount;//没有红色连续pNode parent root-_parent;if (parent-_color RED root-_color RED){cout 有连续的红色结点 endl;return false;}return _isRBTree(root-_left, curBlackCount, totalBlackCout) _isRBTree(root-_right, curBlackCount, totalBlackCout);}private:pNode _header;
};
九、keyvalue 结构红黑树整体代码
#pragma once
#includeiostream
using namespace std;//定义颜色
enum Color
{RED,BLACK,
};// 定义节点
templateclass K, class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Color _col;RBTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}else{Node* cur _root;Node* parent nullptr;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);cur-_col RED;if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}while (parent parent-_col RED){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;// 情况一 uncle存在且为红if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else{// 情况二if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}// 情况三else{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else{Node* uncle grandfather-_left;if (uncle uncle-_col RED){uncle-_col parent-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else{// g// p// cif (cur parent-_left){RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}// g// p// celse{RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}}void RotateL(Node* parent){Node* SubR parent-_right;Node* SubRL SubR-_left;parent-_right SubRL;if (SubRL)SubRL-_parent parent;Node* ppNode parent-_parent;SubR-_left parent;parent-_parent SubR;if (ppNode nullptr){_root SubR;SubR-_parent nullptr;}else{if (parent ppNode-_left){ppNode-_left SubR;SubR-_parent ppNode;}else{ppNode-_right SubR;SubR-_parent ppNode;}}}void RotateR(Node* parent){Node* SubL parent-_left;Node* SubLR SubL-_right;parent-_left SubLR;if (SubLR)SubLR-_parent parent;Node* ppNode parent-_parent;SubL-_right parent;parent-_parent SubL;if (ppNode nullptr){_root SubL;SubL-_parent nullptr;}else{if (parent ppNode-_left){ppNode-_left SubL;}else{ppNode-_right SubL;}SubL-_parent ppNode;}}void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}bool check(Node* root, int blackNum, int ref){if (root nullptr){if (blackNum ! ref){cout 违反规则:本条路径的黑色节点的数量跟最左路径不相等 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout 违反规则出现连续红色节点 endl;return false;}if (root-_col BLACK)blackNum;return check(root-_left, blackNum, ref) check(root-_right, blackNum, ref);}bool IsBalance(){if (_root nullptr)return true;if (_root-_col ! BLACK)return false;int ref 0;// 统计黑节点的个数Node* left _root;while (left){if (left-_col BLACK)ref;left left-_left;}return check(_root, 0, ref);}
private:Node* _root nullptr;
};
