网站中的二级菜单怎么做23,怎么用vue写wordpress主题,黄冈商城网站建设,网站建设汇报稿红黑树 1.前言2.红黑树简述2.1概念2.2性质 3.红黑树的插入3.1关于新插入节点的颜色3.2节点的定义3.3插入新节点3.4判断插入后是否需要调整3.5插入后维持红黑树结构#xff08;重点#xff09;3.5.1cur、p、u为红#xff0c;g为黑3.5.2cur、p为红#xff0c;g为黑#xff0… 红黑树 1.前言2.红黑树简述2.1概念2.2性质 3.红黑树的插入3.1关于新插入节点的颜色3.2节点的定义3.3插入新节点3.4判断插入后是否需要调整3.5插入后维持红黑树结构重点3.5.1cur、p、u为红g为黑3.5.2cur、p为红g为黑u为空/u存在为黑 4.一些简单的测试接口5.完整代码 1.前言
本文旨在理解红黑树基本概念以及变色旋转规则以理解Cmap和set的底层原理不会讲红黑树的删除操作。对于基本的旋转操作(单旋和双旋)本文不会展开讲详细讲解在这里AVL树旋转讲解。 2.红黑树简述
2.1概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保最长路径不超过最短路径两倍因而是接近平衡的。 2.2性质
每个节点不是红色就是黑色。根部节点是黑色的。(为了减少旋转次数后面讲旋转大家就明白了对于一个红节点它的孩子只能是黑色。(即一条路径上不能出现连续的红色节点)每条路径都必须包含相同数量的黑色节点。
通过上面规则的限制红黑树最长路径一定不会超过最短路径两倍也就维持了高度的相对平衡。 结合3、4来看下面的两条路径 最长黑、红、黑、红、黑、红………… 最短黑、黑、黑………… 3.红黑树的插入
3.1关于新插入节点的颜色
对于新插入节点我们设置为红色原因是红黑树每条路径都必须包含相同数量的黑色节点性质4新插入红节点不一定破坏红黑树的结构新插入黑色节点一定不符合性质4而且很难调整。 3.2节点的定义
//用枚举来定义颜色
enum Color
{RED,BLACK
};//这里直接实现key_value模型
templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent; //涉及到旋转多加父亲指针来简化操作pairK, V _kv; //存储键值对Color _col; //颜色RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_col(RED) //新节点颜色为红色{}
};3.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 (kv.first cur-_kv.first) //待插入节点在右子树{parent cur;cur cur-_right;}else if (kv.first cur-_kv.first) //待插入节点在左子树{parent cur;cur cur-_left;}else //相同{return false;}}cur new Node(kv);if (kv.first parent-_kv.first) //新节点在父亲右子树{parent-_right cur;}else //新节点在父亲左子树{parent-_left cur;}cur-_parent parent; //记得更新父亲指针/// 变色旋转维持红黑树结构暂时省略 //_root-_col BLACK; //可能改变根部颜色保持根部为黑色return true;
}3.4判断插入后是否需要调整
其实红黑树插入后只需要看当前节点和父亲的颜色即可其中新节点一定为红。
父亲为黑符合规则不需要调整。父亲为红此时出现红红的连续节点需要进行调整。 3.5插入后维持红黑树结构重点
为了方便叙述我们做如下定义
cur表示当前节点p表示cur父亲节点u表示叔叔节点g表示祖父(p和u的父亲)节点
3.5.1cur、p、u为红g为黑 代码
while (parent parent-_col RED) //父亲为红就调整调整到根部要结束
{Node* granderfather parent-_parent; //祖父//需要对叔叔进行操作需要判断叔叔是祖父的左还是右if (parent granderfather-_left) //父亲是祖父的左子树{Node* uncle granderfather-_right;if (uncle uncle-_col RED) //叔叔不为空并且叔叔为红变色即可{uncle-_col parent-_col BLACK;granderfather-_col RED; //当前子树可能为部分继续向上调整cur granderfather;parent cur-_parent;}else //叔叔为空或为黑色{ //先省略}}else //父亲是祖父的右子树{Node* uncle granderfather-_left;if (uncle uncle-_col RED) //叔叔不空并且为红{parent-_col uncle-_col BLACK;granderfather-_col RED; //当前可能为部分子树需要继续上调cur granderfather;parent cur-_parent;}else //叔叔为空或为黑色{// 先省略}}
}3.5.2cur、p为红g为黑u为空/u存在为黑
下面是一会要用到的旋转接口
void RotateL(Node* parent) //左单旋,rotate-旋转
{Node* SubR parent-_right;Node* SubRL SubR-_left; //这个有可能为空Node* ppnode parent-_parent; //原来父亲的父亲parent-_right SubRL;if (SubRL) SubRL-_parent parent;SubR-_left parent;parent-_parent SubR;if (ppnode nullptr) //旋转的是整颗树{_root SubR;SubR-_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; //这个有可能为空Node* ppnode parent-_parent;parent-_left SubLR;if (SubLR) SubLR-_parent parent;SubL-_right parent;parent-_parent SubL;if (ppnode nullptr) //旋转的是整颗树{_root SubL;SubL-_parent nullptr;}else //旋转部分{if (ppnode-_left parent) //是左子树{ppnode-_left SubL;}else //右子树{ppnode-_right SubL;}SubL-_parent ppnode;}
}涉及旋转情况比较复杂分开讨论
1p为g的左孩子cur为p的左孩子 2p为g的左孩子cur为p的右孩子 3p为g的右孩子cur为p的右孩子 4p为g的右孩子cur为p的左孩子 整合一下1、2、3、4得到下面的调整代码
//到这里插入新节点的工作完成下面进行结构调整
while (parent parent-_col RED) //父亲为红就调整调整到根部要结束
{Node* granderfather parent-_parent; //祖父if (parent granderfather-_left) //父亲是祖父的左子树p为g的左孩子{Node* uncle granderfather-_right;if (uncle uncle-_col RED) //叔叔不为空并且叔叔为红变色即可{uncle-_col parent-_col BLACK;granderfather-_col RED; //当前子树可能为部分继续向上调整cur granderfather;parent cur-_parent;}else //叔叔为空或为黑色{ // g// p u// cif (cur parent-_left) //当前为父亲的左子树cur为p的左孩子{RotateR(granderfather);granderfather-_col RED;parent-_col BLACK;}else //当前为父亲的右子树cur为p的右孩子{// g// p u// c//左右双旋RotateL(parent);RotateR(granderfather);granderfather-_col RED;cur-_col BLACK;}break; //这两种情况调整完可以结束}}else //父亲是祖父的右子树p为g的右孩子{Node* uncle granderfather-_left;if (uncle uncle-_col RED) //叔叔不空并且为红{parent-_col uncle-_col BLACK;granderfather-_col RED; //当前可能为部分子树需要继续上调cur granderfather;parent cur-_parent;}else //叔叔为空或为黑色{if (cur parent-_right) //当前为父亲的右cur为p的右孩子{// g// u p// c//左旋RotateL(granderfather);parent-_col BLACK;granderfather-_col RED;}else //当前为父亲的左cur为p的左孩子{// g// u p// c//右左双旋RotateR(parent);RotateL(granderfather);cur-_col BLACK;granderfather-_col RED; }break; //这两种情况调整完可以结束}}
}
_root-_col BLACK; //保持根部为黑色4.一些简单的测试接口
void InOrder() //中序遍历验证是否为二叉搜索树
{_InOrder(_root);cout endl;
}void _InOrder(Node* root)
{if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);
}// 根节点-当前节点这条路径的黑色节点的数量
bool Check(Node* root, int blacknum, const int refVal)
{if (root nullptr) //到根部看看当前路径黑色节点和标准值是否一致{//cout balcknum endl;if (blacknum ! refVal){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, refVal) Check(root-_right, blacknum, refVal);
}bool IsBalance()
{if (_root nullptr)return true;if (_root-_col RED)return false;//参考值即先算出一条路径的黑色节点数int refVal 0;Node* cur _root;while (cur){if (cur-_col BLACK){refVal;}cur cur-_left;}int blacknum 0;return Check(_root, blacknum, refVal);
}5.完整代码
#pragma once
#include iostream
#include utility
using namespace std;//用枚举来定义颜色
enum Color
{RED,BLACK
};//这里直接实现key_value模型
templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent; //涉及到旋转多加父亲指针来简化操作pairK, V _kv; //存储键值对Color _col; //颜色RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_col(RED) //新节点颜色为红色{}
};templateclass K, class V
class RBTree
{
public:typedef RBTreeNodeK, V Node;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 (kv.first cur-_kv.first) //待插入节点在右子树{parent cur;cur cur-_right;}else if (kv.first cur-_kv.first) //待插入节点在左子树{parent cur;cur cur-_left;}else //相同{return false;}}cur new Node(kv);if (kv.first parent-_kv.first) //在右子树{parent-_right cur;}else{parent-_left cur;}cur-_parent parent;while (parent parent-_col RED) //父亲为红就调整调整到根部要结束{Node* granderfather parent-_parent; //祖父if (parent granderfather-_left) //父亲是祖父的左子树{Node* uncle granderfather-_right;if (uncle uncle-_col RED) //叔叔不为空并且叔叔为红变色即可{uncle-_col parent-_col BLACK;granderfather-_col RED; //当前子树可能为部分继续向上调整cur granderfather;parent cur-_parent;}else //叔叔为空或为黑色{ // g// p u// cif (cur parent-_left) //当前为父亲的左子树{RotateR(granderfather);granderfather-_col RED;parent-_col BLACK;}else //当前为父亲的右子树{// g// p u// c//左右双旋RotateL(parent);RotateR(granderfather);granderfather-_col RED;cur-_col BLACK;}break;}}else //父亲是祖父的右子树{Node* uncle granderfather-_left;if (uncle uncle-_col RED) //叔叔不空并且为红{parent-_col uncle-_col BLACK;granderfather-_col RED; //当前可能为部分子树需要继续上调cur granderfather;parent cur-_parent;}else //叔叔为空或为黑色{if (cur parent-_right) //当前为父亲的右{// g// u p// c//左旋RotateL(granderfather);parent-_col BLACK;granderfather-_col RED;}else //当前为父亲的左{// g// u p// c//右左双旋RotateR(parent);RotateL(granderfather);cur-_col BLACK;granderfather-_col RED; }break;}}}_root-_col BLACK; //保持根部为黑色return true;}/// //
/// /
/// 测试代码void InOrder() //中序遍历验证是否为二叉搜索树{_InOrder(_root);cout endl;}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}// 根节点-当前节点这条路径的黑色节点的数量bool Check(Node* root, int blacknum, const int refVal) {if (root nullptr) //到根部看看当前路径黑色节点和标准值是否一致{//cout balcknum endl;if (blacknum ! refVal){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, refVal) Check(root-_right, blacknum, refVal);}bool IsBalance(){if (_root nullptr)return true;if (_root-_col RED)return false;//参考值即先算出一条路径的黑色节点数int refVal 0;Node* cur _root;while (cur){if (cur-_col BLACK){refVal;}cur cur-_left;}int blacknum 0;return Check(_root, blacknum, refVal);}int Height(){return _Height(_root);}int _Height(Node* root) //求高度的{if (root nullptr)return 0;int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}Node* Find(K key){return _Find(key, _root);}Node* _Find(K key, Node* root){if (root nullptr)return nullptr;if (key root-_kv.first) //在右子树{return _Find(key, root-_right);}else if (key root-_kv.first) //在左子树{return _Find(key, root-_left);}else //找到了{return root;}}private:Node* _root nullptr;void RotateL(Node* parent) //左单旋,rotate-旋转{Node* SubR parent-_right;Node* SubRL SubR-_left; //这个有可能为空Node* ppnode parent-_parent; //原来父亲的父亲parent-_right SubRL;if (SubRL) SubRL-_parent parent;SubR-_left parent;parent-_parent SubR;if (ppnode nullptr) //旋转的是整颗树{_root SubR;SubR-_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; //这个有可能为空Node* ppnode parent-_parent;parent-_left SubLR;if (SubLR) SubLR-_parent parent;SubL-_right parent;parent-_parent SubL;if (ppnode nullptr) //旋转的是整颗树{_root SubL;SubL-_parent nullptr;}else //旋转部分{if (ppnode-_left parent) //是左子树{ppnode-_left SubL;}else //右子树{ppnode-_right SubL;}SubL-_parent ppnode;}}
};
