织梦做的网站打开不是,饮品店网站模板,计算机软件开发难学吗,dyndns如何申请免费域名个人主页#xff1a;仍有未知等待探索-CSDN博客 专题分栏#xff1a;C 目录 一、概念
性质
二、操作
插入
情况一#xff1a;cur为红、p为红、g为黑#xff0c;如果u存在且为红
步骤#xff1a;
情况二#xff1a;cur为红、p为红、g为黑#xff0c;如果u不存在或… 个人主页仍有未知等待探索-CSDN博客 专题分栏C 目录 一、概念
性质
二、操作
插入
情况一cur为红、p为红、g为黑如果u存在且为红
步骤
情况二cur为红、p为红、g为黑如果u不存在或者u存在且为黑
情况a步骤
情况b步骤
情况三cur为红、p为红、g为黑如果u不存在或者u存在且为黑
步骤 三、总代码 一、概念
红黑树是一颗特殊的二叉搜索树。红黑树虽然不要求是平衡的但是该树的最长路径不超过最短路径的二倍。
红黑树避免了过多的旋转问题。 性质 1、每个节点的颜色不是红色就是黑色。 2、根节点的颜色是黑色。 3、如果一个节点的颜色是红色则该节点的左右孩子节点都是黑色。 4、对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点。 5、每个叶子节点这里的叶子节点指的是null节点的颜色都是黑色的。 二、操作
插入
插入一个新节点之后会遇到几种情况需要我们自己对红黑树进行调整来保证其性质的正确。 新插入节点的颜色为红色。如果为黑色的话性质4可能会不满足相较于性质3来说调整起来会比较麻烦。 情况一cur为红、p为红、g为黑如果u存在且为红 步骤 将 p、u 变成黑色g 变成红色。如果 g 为整个树的根节点则将 g 变成黑色。如果 g 不是根节点且双亲结点为红色的话继续向上进行变换。如果 g 不是根节点且双亲结点为黑色的话则结束。 情况二cur为红、p为红、g为黑如果u不存在或者u存在且为黑 对于这个情况二还有两种不同的情况。注p 节点一定是 cur 节点的双亲结点。 情况acur 为 p 的左孩子p 为 g 的左孩子。 情况bcur 为 p 的右孩子、p 为 g 的右孩子。 情况a步骤 将 p 变成黑色g 变成红色。以 g 为旋转点进行右单旋。 情况b步骤 将 p 变成黑色g 变成红色。然后以 g 为旋转点进行左单旋。 另外一种情况u 不存在就需要自己去琢磨咯。 情况三cur为红、p为红、g为黑如果u不存在或者u存在且为黑 情况三是情况二的补充。对于情况二我们只讲了上述的两种情况。剩余的情况则在这里进行解释。 情况acur 为 p 的左孩子p 为 g 的右孩子。 情况bcur 为 p 的右孩子、p 为 g 的左孩子。 对于上述情况想必大概也能猜测出来这种情况要对红黑树进行双旋处理了。这里仅对情况a 且 u 存在进行画图分析。 步骤 先以 p 为旋转点进行右单旋然后再以 g 为旋转点进行左单旋。然后将 cur 变成黑色g 变成红色。 三、总代码
#include iostream
#include assert.h
#include vector
using namespace std;enum color
{Red,Black
};
template class K, class V
struct RBTreeNode
{typedef pairK, V PKV;RBTreeNode(const PKV e PKV()):_left(nullptr),_right(nullptr),_parent(nullptr),_col(Red),_val(e){}struct RBTreeNodeK, V* _left;struct RBTreeNodeK, V* _right;struct RBTreeNodeK, V* _parent;int _col;PKV _val;
};templateclass K, class V
class RBTree
{
public:typedef RBTreeNodeK, V node;typedef pairK, V PKV;RBTree():_root(nullptr){}void insert(const PKV e){// 根据二叉搜索树插入的方式进行插入node* cur _root;node* parent cur;while (cur){parent cur;if (cur-_val.first e.first){cur cur-_left;}else{cur cur-_right;}}cur new node(e);if (parent nullptr){_root cur;}else{if (parent-_val.first cur-_val.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;}// 更新对于不同的情况进行不同的调整// parent 为黑、不存在结束node* p parent;while (p p-_col Red){node* g p-_parent;if (g-_left p){node* u g-_right;// 叔叔存在且为红if (u u-_col Red){p-_col u-_col Black;g-_col Red;// 继续往上处理cur g;p cur-_parent;}// 叔叔不存在且为黑else {// g// p u// cif (cur p-_left){// 右单旋RotateR(g);// 变色g-_col Red;p-_col Black;}// g// p u// celse {// 左右双旋RotateL(p);RotateR(g);// 变色cur-_col Black;g-_col Red;}// 叔叔不存在或者存在且为黑调整完就不需要继续进行调整了break;}}else{node* u g-_left;if (u u-_col Red){p-_col u-_col Black;g-_col Red;// 继续往上处理cur g;p cur-_parent;}else {// g// u p// cif (cur p-_right){// 左单旋RotateL(g);// 变色g-_col Red;p-_col Black;}// g// u p// celse {// 左右双旋RotateR(p);RotateL(g);// 变色cur-_col Black;g-_col Red;}// 叔叔不存在或者存在且为黑调整完就不需要继续进行调整了break;}}}_root-_col Black;}void inorder(){_inorder(_root);}
private:void _inorder(node* root){if (root nullptr) return;_inorder(root-_left);cout root-_val.first ;_inorder(root-_right);}void RotateR(node* parent){node* subl parent-_left;node* sublr subl-_right;node* grandfather parent-_parent;parent-_left sublr;if (sublr){sublr-_parent parent;}subl-_right parent;parent-_parent subl;subl -_parent grandfather;if (_root parent){if (grandfather-_left parent){grandfather-_left subl;}else{grandfather-_right subl;}}else{_root subl;}}void RotateL(node* parent){node* subr parent-_right;node* subrl subr-_left;node* grandfather parent-_parent;parent-_right subrl;if (subrl){subrl-_parent parent;}subr-_left parent;parent-_parent subr;subr -_parent grandfather;if (_root ! parent){if (grandfather-_left parent){grandfather-_left subr;}else{grandfather-_right subr;}}else{_root subr;}}protected:node* _root;
};
