网站生成手机站,商标网商标购买,wordpress手机访问排版乱,wordpress更换编辑器文章目录 一.红黑树的定义二.红黑树的插入1.红黑树节点的定义2.红黑树的插入操作3.总结#xff1a; 三.红黑树与AVL树的比较四.检验手写的红黑树五.源码 一.红黑树的定义 红黑树#xff0c;是一种二叉搜索树#xff0c;但在每个结点上增加一个存储位表示结点的颜色#xff… 文章目录 一.红黑树的定义二.红黑树的插入1.红黑树节点的定义2.红黑树的插入操作3.总结 三.红黑树与AVL树的比较四.检验手写的红黑树五.源码 一.红黑树的定义 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 红黑树的性质
每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的则它的两个孩子结点是黑色的对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
解读 性质三保证树中没有连续的红色节点 性质四每条路径上黑色节点的数目相同 满足以上性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍
其中其极限最短全黑。极限最长一黑一红……
可以发现最坏情况的时间复杂度和AVL树一样都是O(logN)但是红黑树这种近似平衡的结构减少了大量旋转综合性能优于AVL树。
二.红黑树的插入
1.红黑树节点的定义
enum Colour
{Red,Black
};templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col;RBTreeNode():_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv){}
};2.红黑树的插入操作
插入步骤 按照二叉搜索的树规则插入新节点 检测新节点插入后红黑树的性质是否造到破坏 因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论 约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点 情况一: cur为红p为红g为黑u存在且为红 解决方式将p,u改为黑g改为红然后把g当成cur继续向上调整 情况二: cur为红p为红g为黑u不存在/u存在且为黑 解决方式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做右单旋转
3.总结
插入新节点时父节点为红看叔叔的颜色。
叔叔存在且为红变色向上调整可能变为三种情况中的任意一种)叔叔不存在/存在且为黑直线。单旋变色叔叔不存在/存在且为黑折线两次单旋变色
三.红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N)
红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。
四.检验手写的红黑树
//检查有没有连续红节点
bool Check(Node* root,int blackNum,const int ref)
{if (root nullptr){if (blackNum ! ref){cout 路径上黑节点数量不一致 endl;return false;}return true;}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent-_col RED){cout 违反规则父子均为红 endl;return false;}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 ! nullptr){if (left-_col BLACK){ref;}left left-_left;}return Check(_root,0,ref);
}五.源码
namespace dianxia
{enum Colour{Red,Black};templateclass K,class Vstruct RBTreeNode{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col; //节点颜色RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv){}};templateclass K,class Vclass 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;}else{parent-_left cur;}cur-_parent parent;//检查是否满足红黑树的要求while (parent parent-_col Red){//p为红则gp一定存在且为黑Node* grandparent parent-_parent;assert(grandparent);assert(grandparent-_colBlack);if (parent grandparent-_left){Node* uncle grandparent-_right;//1.u存在且为红变色并继续向上更新if (uncle uncle-_col Red){parent-_col uncle-_col Black;grandparent-_col Red;cur grandparent;parent cur-_parent;}//2.u不存在或u为黑 变色加旋转else{if (cur parent-_left){// g// p u// c//右旋RotateR(grandparent);parent-_col Black;grandparent-_col Red;}else{// g// p u// c//先左旋再右旋RotateL(parent);RotateR(grandparent);cur-_col Black;grandparent-_col Red;}break;}}else //grandparent-_rightparent{Node* uncle grandparent-_left;//1.u存在且为红变色并继续向上更新if (uncle uncle-_col Red){parent-_col uncle-_col Black;grandparent-_col Red;cur grandparent;parent cur-_parent;}//2.u不存在或u为黑 变色加旋转else{if (cur parent-_right){// g// u p// c//左RotateL(grandparent);parent-_col Black;grandparent-_col Red;}else{// g// u p// c//先右旋再左旋RotateR(parent);RotateL(grandparent);cur-_col Black;grandparent-_col Red;}break;}}}_root-_col Black;return true;}~RBTree(){_Destroy(_root);_root nullptr;}void Inorder(){_InOrder(_root);}//检查红黑树1.检查以根节点为根的每条路径黑色节点的数目是否都相等// 2.检查某条路径上是否有连续的红色节点bool Isbalance(){if (_root _root-_col Red){cout 根节点是红色的 endl;return false;}int benchmark 0;Node* cur _root;while (cur){if (cur-_col Black)benchmark;cur cur-_left;}return _Check(_root, 0, benchmark);}int Height(){return _Height(_root);}private:void _Destroy(Node* root){if (root nullptr){return;}_Destroy(root-_left);_Destroy(root-_right);delete root;}int _Height(Node* root){if (root nullptr)return 0;int leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}bool _Check(Node* root, int blacknum, int benchmark){if (root nullptr){if (benchmark ! blacknum){cout 某条路径黑色节点的数量不相等 endl;return false;}return true;}if (root-_col Black)blacknum;if (root-_col Red root-_parent root-_parent-_col Red){cout 某条路径存在连续的红色节点 endl;return false;}return _Check(root-_left, blacknum, benchmark) _Check(root-_right, blacknum, benchmark);}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;_root-_parent nullptr;}else{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 (parent _root){_root subL;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}}private:Node* _root nullptr;};
}本文到此结束码文不易还请多多支持
