杭州网站建设工作室,建立百度网站,wordpress前端会员中心开发教程,河北建设工程信息网首页#x1f307;个人主页#xff1a;平凡的小苏 #x1f4da;学习格言#xff1a;命运给你一个低的起点#xff0c;是想看你精彩的翻盘#xff0c;而不是让你自甘堕落#xff0c;脚下的路虽然难走#xff0c;但我还能走#xff0c;比起向阳而生#xff0c;我更想尝试逆风… 个人主页平凡的小苏 学习格言命运给你一个低的起点是想看你精彩的翻盘而不是让你自甘堕落脚下的路虽然难走但我还能走比起向阳而生我更想尝试逆风翻盘。 C专栏C内功修炼基地 家人们更新不易你们的点赞和⭐关注⭐真的对我真重要各位路 过的友友麻烦多多点赞关注。 欢迎你们的私信提问感谢你们的转发 关注我关注我关注我你们将会看到更多的优质内容 一、红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 二、红黑树的性质 每个结点不是红色就是黑色 根节点是黑色的 如果一个节点是红色的则它的两个孩子结点是黑色的 对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 最优情况全黑或每条路径都是一黑一红的满二叉树高度logN 最差情况每颗子树左子树全黑右子树一黑一红。高度2*logN。 可以发现最坏情况的时间复杂度和AVL树一样都是O(logN)但是红黑树这种近似平衡的结构减少了大量旋转综合性能优于AVL树。 注第三点的意思就是没有连续的红色节点进行连接 三、红黑树的定义
enum Color
{RED,BLACK
};
templateclass K, class V
struct RedBlackTreeNode
{pairK, V _kv;RedBlackTreeNodeK, V* _left;//该节点的左孩子RedBlackTreeNodeK, V* _right;//该节点的右孩子RedBlackTreeNodeK, V* _parent;//该节点是父亲节点Color _col;//颜色RedBlackTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr),_col(RED){}
};思考在节点的定义中为什么要将节点的默认颜色给为红色的而不是黑色 因为给成红色就会和红黑树的性质3冲突而给成黑色就会和红黑树的性质4冲突那么对于冲突性质3比性质4更优因为冲突性质4不管插入哪个位置都会引起颜色的变换或者旋转。而冲突性质3有可能会引起改变也可能不改变 四、红黑树的插入主要看叔叔的颜色
1.情况一uncle存在且节点颜色为红
这种情况cur、parent、grandfather都是确定颜色的唯独uncle的颜色是不确定的。 2.情况二uncle不存在或者uncle存在且节点为黑直线
uncle不存在示例图
uncle存在且为黑的情况示例图 3.情况三uncle不存在/存在并且为黑折线
uncle的情况分两种。
uncle不存在则cur为插入节点两次单旋即可。 uncle存在且为黑示例图 4.总结
插入新节点时父节点为红看叔叔的颜色。
1、叔叔存在且为红变色向上调整可能变为三种情况中的任意一种
2、叔叔不存在/存在且为黑直线。单旋变色
3、叔叔不存在/存在且为黑折线两次单旋变色
五、红黑树的插入代码
bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}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);if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;// ... 控制平衡while (parent parent-_col RED)//parent不为空并且为红进循环{Node* grandfather parent-_parent;if (grandfather-_left parent){if (parent-_left cur){Node* uncle grandfather-_right;if (uncle uncle-_col RED)//叔叔节点为红{parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else //叔叔节点为空或者为黑的情况{RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;break;}}else{Node* uncle grandfather-_right;if (uncle uncle-_col RED)//叔叔存在并且叔叔节点为红{parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else //叔叔节点为空或者为黑的情况{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;break;}}}else{if (parent-_right cur){Node* uncle grandfather-_left;if (uncle uncle-_col RED)//叔叔节点为红{parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else //叔叔节点为空或者为黑的情况{RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;break;}}else{Node* uncle grandfather-_left;if (uncle uncle-_col RED)//叔叔节点为红{parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else //叔叔节点为空或者为黑的情况{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;break;}}}}_root-_col BLACK;//处理根一直为黑的情况return true;}六、红黑树代码是否正确的代码检测
bool checkColour(Node* root, int blacknum, int beachmark){if (root nullptr){if (blacknum ! beachmark)//和基准值比较如果不相等则红黑树代码出错{return false;}return true;}if (root-_col BLACK)//记录黑色节点数量{blacknum;}if (root-_col RED root-_parent root-_parent-_col RED){cout root-_kv.first 出现连续红色节点 endl;return false;}return checkColour(root-_left, blacknum, beachmark) checkColour(root-_right, blacknum, beachmark);}bool _IsBalance(Node* root){if (root nullptr){return true;}if (root-_col ! BLACK)//根节点不为黑不符合红黑树的性质{return false;}//基准值int beanchmark 0;Node* cur root;while (cur)//求一条路径的黑色节点的数量作为基准值{if (cur-_col BLACK){beanchmark;}cur cur-_left;}return checkColour(root, 0, beanchmark);}详看代码注释 七、红黑树的整体代码
#include iostream
#include cassert
using namespace std;templateclass K, class V
class RedBlackTree
{typedef RedBlackTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}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);if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;// ... 控制平衡while (parent parent-_col RED)//parent不为空并且为红进循环{Node* grandfather parent-_parent;if (grandfather-_left parent){if (parent-_left cur){Node* uncle grandfather-_right;if (uncle uncle-_col RED)//叔叔节点为红{parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else //叔叔节点为空或者为黑的情况{RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;break;}}else{Node* uncle grandfather-_right;if (uncle uncle-_col RED)//叔叔存在并且叔叔节点为红{parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else //叔叔节点为空或者为黑的情况{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;break;}}}else{if (parent-_right cur){Node* uncle grandfather-_left;if (uncle uncle-_col RED)//叔叔节点为红{parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else //叔叔节点为空或者为黑的情况{RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;break;}}else{Node* uncle grandfather-_left;if (uncle uncle-_col RED)//叔叔节点为红{parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else //叔叔节点为空或者为黑的情况{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;break;}}}}_root-_col BLACK;//处理根一直为黑的情况return true;}bool IsBalance(){return _IsBalance(_root);}
private:bool checkColour(Node* root, int blacknum, int beachmark){if (root nullptr){if (blacknum ! beachmark){return false;}return true;}if (root-_col BLACK){blacknum;}if (root-_col RED root-_parent root-_parent-_col RED){cout root-_kv.first 出现连续红色节点 endl;return false;}return checkColour(root-_left, blacknum, beachmark) checkColour(root-_right, blacknum, beachmark);}bool _IsBalance(Node* root){if (root nullptr){return true;}if (root-_col ! BLACK){return false;}//基准值int beanchmark 0;Node* cur root;while (cur){if (cur-_col BLACK){beanchmark;}cur cur-_left;}return checkColour(root, 0, beanchmark);}void RotateR(Node* parent){Node* cur parent-_left;Node* curRight cur-_right;parent-_left curRight;cur-_right parent;Node* ppNode parent-_parent;if (curRight){curRight-_parent parent;}parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left cur;}else{ppNode-_right cur;}cur-_parent ppNode;}}void RotateL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;if (curleft)//判断是否为空空的话就不用接上父亲节点{curleft-_parent parent;}cur-_left parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}
private:Node* _root nullptr;
};
