河南做网站那家最好,网络搭建drc,兰州装修公司官网,我怎么自己创建微信公众号每一个不曾起舞的日子都是对生命的辜负 红黑树实现:RBTree 前言一.红黑树的概念及性质1.1 红黑树的概念1.2 红黑树的性质二.红黑树的结构2.1 红黑树节点的定义2.2 红黑树类的封装三.红黑树的插入情况1#xff1a;只变色情况2#xff1a;变色单旋情况3#xff1a;双旋插入的代… 每一个不曾起舞的日子都是对生命的辜负 红黑树实现:RBTree 前言一.红黑树的概念及性质1.1 红黑树的概念1.2 红黑树的性质二.红黑树的结构2.1 红黑树节点的定义2.2 红黑树类的封装三.红黑树的插入情况1只变色情况2变色单旋情况3双旋插入的代码实现四.红黑树的验证五.红黑树实现代码完整RBTree.hTest.cpp六.红黑树与AVL树的比较前言 在上一节中我们学到了AVL树的结构及其相关性质对于平衡树来说AVL无疑是最完美的结构但实际上AVL树由于完美的结构因此也要花费一定的代价由于AVL树的结构很敏感查找虽然最快但插入节点后一旦偏离AVL结构就会进行旋转而旋转就会花费一定的性能。因此我们提到的map和set的底层为了防止这种性能上的缺失即便AVL是非常完美的结构也不采用AVL。而是采用我们这节所要描述的红黑树。 一.红黑树的概念及性质
1.1 红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 可见红黑树的这种结构虽然在不满足条件时会发生旋转但敏感程度相比AVl树大大降低。 1.2 红黑树的性质
每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的则它的两个孩子结点是黑色的对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点每个叶子结点都是黑色的此处的叶子结点指的是空结点
需要注意的是对于性质3意思就是没有连续的红色结点。 思考 为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍 就上面的这颗红黑树来说有11条路径需算到空我们只观察黑色结点发现是接近满二叉树的。对于红黑树的最短路径最短的极限情况就是一条路径全是黑色的结点因为其他路径也会有相同数目的黑节点加上一定数量的红色结点而最长路径就是一黑一红相间的路径。可见最长的结点个数是最短结点个数的二倍。 这样就是红黑树的结构且存在最长和最短的情况最短为最长的二分之一。 由于红黑树确保没有一条路径会比其他路径长出俩倍因此可以看成近似平衡对于这种不确定的结构自然就有最好的情况和最坏的情况。 最好情况左右平衡 全黑或者每条路径都是一黑一红相间的路径接近满二叉树。那么此时设全黑的路径长度为h结点数量为N则2^h - 1 _ N_代表红色结点由于一条路径红色结点数量一定小于等于黑色所以可以忽略计算此时h logN。 最坏情况左右极其不平衡 左子树全黑且右子树一黑一红。那么此时最长路径为2*logN。 总结 可以看出在对数的加持下即便是最坏情况对于计算机来说相差也不是很大。虽不如AVL的极度平衡但红黑树明显在插入节点时显得张弛有力。对于AVL来说说是过刚易折也不为过往往像红黑树那样增加一定的柔韧性才是最后的选择。 二.红黑树的结构
2.1 红黑树节点的定义
相比较AVL树红黑树的结点仍是三叉链这个结构为后续不满足结构的条件旋转做准备。此外和AVL树结点不同的是红黑树不再有平衡因子这一变量而是多了一个定义颜色的变量颜色变量通过枚举实现。下面看看结点定义的代码
enum Color//颜色采用枚举但STL库采用的是特殊的bool值后续会看
{RED,//0BLACK,//1
};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)//默认哪种颜色都可以因为后续会改{}};2.2 红黑树类的封装
enum Color//颜色采用枚举但STL库采用的是特殊的bool值后续会看
{RED,//0BLACK,//1
};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){}
private:Node* _root nullptr;
};三.红黑树的插入
与AVL树一样在插入中需要考虑的因素众多但相比AVL红黑树在插入时的情况少很多因为其结构没有AVL树的高度平衡。 在红黑树的性质中第三第四条尤为重要。即
如果一个节点是红色的则它的两个孩子结点是黑色的对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点
如果我们新插入的结点的颜色为黑的话插入之后一定会打破上述第二个结构导致每条路径的黑结点数量不同如果新插入的节点的颜色为红色的话也有可能不满足情况如果插入节点的父节点为黑的话还好但如果父节点为红也就不满足这个条件了。因此插入节点的颜色尤为重要经过上述考虑插入节点的颜色为红无疑是最好的选择因为有可能满足条件有可能不满足条件但插入黑色一定不满足。如果插入红色的也不满足那就后期处理就好了。
插入节点的颜色必须为红 检测新节点插入后红黑树的性质是否造到破坏 因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论 约定: cur为当前插入节点p为父节点g为祖父节点u为叔叔节点 对于新节点的插入与父节点和父节点的兄弟节点也有关下面就看看各种情况 情况1只变色
cur为红p为红g为黑u存在且为红 通过上面图的步骤我们大致知道了思路如果红色结点连续为了满足红黑树的不能有连续红色结点的性质我们需要将其双亲也就是父亲结点变成黑色如果这棵树是子树那么为了保证黑色结点数量不变我们需要将g变红如果g的双亲仍是红色那么就一直往上更新迭代。对于上图实际上同样是个抽象图因为a,b,c,d,e可以使任意的红黑树子树情况也会随着这几个抽象树节点的增加而变化的非常多因此我们只需要牢记这种抽象图即可。
cur和p均为红违反了性质三此处能否将p直接改为黑 解决方式将p,u改为黑g改为红然后把g当成cur继续向上调整。 可以看出红色结点的增加是因为插入节点黑色节点的增加是为了保证红黑树结构的性质从红色结点变化而来的。 情况2变色单旋
cur为红p为红g为黑u不存在/u存在且为黑 如果不存在叔叔结点u那么是这样的结构
此时新增的cur节点为红那我们必须想办法将p变黑此时就可以考虑将g为轴进行旋转的方式
这样就可以使其满足红黑树的结构了u结点存在且为黑和此同理。
接下来看看步骤
p为g的左孩子cur为p的左孩子则g进行右单旋转相反 p为g的右孩子cur为p的右孩子则g进行左单旋转 p、g变色–p变黑g变红
情况3双旋
cur为红p为红g为黑u不存在/u存在且为黑 看似与情况二一样实际上区别是cur插入的左右不同。情况2为左情况3为右。 和上篇中的AVL一样对于这种弯的结构只进行一次旋转是不可能成功的因此需要进行两部旋转上图只旋转了一次变成了情况2因此需要再旋转一次就能满足红黑树结构的性质。
步骤
p为g的左孩子cur为p的右孩子则针对p做左单旋转相反p为g的右孩子cur为p的左孩子则针对p做右单旋转。 则转换成了情况2。转换成情况2之后再根据情况2的步骤继续旋转p为g的左孩子cur为p的左孩子则g进行右单旋转相反p为g的右孩子cur为p的右孩子则g进行左单旋转 p、g变色–p变黑g变红 注意经过左旋变色位置不变但对应位置的结点变了因此在代码编写时需注意这个问题。 插入的代码实现 注Insert单拿出来观察其利用的旋转函数与AVL一样只不过去掉了平衡因子。 bool Insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);_root-_col BLACK;//根节点为黑色return true;}Node* parent nullptr;Node* cur _root;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;//看叔叔颜色//情况1uncle存在且为红if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//情况2或3不用考虑叔叔的问题即叔叔为空还是为黑{if (cur parent-_left)//情况2{// g// p// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else//情况3{// g// p// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else//与上述代码的左右反过来了而已步骤一样但左右相反。{Node* uncle grandfather-_left;//情况1if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//情况2和3{// g// p// cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}}}}_root-_col BLACK;return true;
}此外有插入就有删除删除是插入的反向思维。删除太难了不用学。真想了解看这个但是没有代码红黑树 - Never - 博客园 (cnblogs.com) 四.红黑树的验证
红黑树的检测分为两步
检测其是否满足二叉搜索树(中序遍历是否为有序序列)检测其是否满足红黑树的性质
函数代码
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);
}
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;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, ref) Check(root-_right, blackNum, ref);
}五.红黑树实现代码完整
随机插入构建红黑树 以升序插入构建红黑树 以降序插入构建红黑树
RBTree.h
#pragma onceenum Color//颜色采用枚举但STL库采用的是特殊的bool值后续会看
{RED,//0BLACK//1
};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;}Node* parent nullptr;Node* cur _root;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;//看叔叔颜色//情况1uncle存在且为红if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//情况2或3不用考虑叔叔的问题即叔叔为空还是为黑{if (cur parent-_left)//情况2{// g// p// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else//情况3{// g// p// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else//与上述代码的左右反过来了而已步骤一样但左右相反。{Node* uncle grandfather-_left;//情况1if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//情况2和3{// g// p// cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}}}}_root-_col BLACK;return true;}//旋转代码和AVL一样只是去掉了平衡因子void RotateL(Node* parent)//左单旋{//1.记录subR, subRLNode* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)//subRL不为空则需要连接到parent{subRL-_parent parent;}Node* ppNode parent-_parent;//记录保存subR-_left parent;parent-_parent subR;if (ppNode nullptr)//说明根节点变化{_root subR;_root-_parent nullptr;}else//如果是局部子树{//判断ppNode之前是左连接还是右连接if (ppNode-_left parent){ppNode-_left subR;}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;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}void Inorder(){_Inorder(_root);}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: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;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, ref) Check(root-_right, blackNum, ref);}void _Inorder(Node* root){if (root nullptr){return;}_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);}Node* _root nullptr;
};void TestRBTree1()
{int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTreeint, int t;for (auto e : a){t.Insert(make_pair(e, e));}t.Inorder();}Test.cpp
#includeiostream
#includestring
#includemap
#includeassert.h
using namespace std;
#includeRBTree.h
int main()
{TestRBTree1();return 0;
}六.红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(log2Nlog_2 Nlog2N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。
