商城网站开发的完整流程,php网站开发 招聘,公司网页网站建设 ppt模板下载,移动端英文简称目录 一. 红黑树的概念及结构
二. 红黑树节点的定义
三. 红黑树节点的插入
3.1 初步查找插入节点的位置并插入节点
3.2 红黑树结构的调整
3.3 红黑树节点插入完整版代码
四. 红黑树的结构检查
4.1 检查是否为搜索树
4.2 检查节点颜色是否满足要求
附录#xff1a;红黑…目录 一. 红黑树的概念及结构
二. 红黑树节点的定义
三. 红黑树节点的插入
3.1 初步查找插入节点的位置并插入节点
3.2 红黑树结构的调整
3.3 红黑树节点插入完整版代码
四. 红黑树的结构检查
4.1 检查是否为搜索树
4.2 检查节点颜色是否满足要求
附录红黑树完整版代码 一. 红黑树的概念及结构
在我之前的博客C数据结构手撕AVL树_【Shine】光芒的博客-CSDN博客中对AVL树的结构及插入节点操作进行了分析AVL树要求以每个节点为根节点的子树的左右子树高度差不超过1以此来保证搜索树查找数据的时间复杂度为O(logN)。
但是AVL树对高度差的要求过于严格会导致在插入节点的过程中频繁进行旋转造成数据插入效率低下。为了权衡插入数据与查找数据的效率一种新的数据结构 -- 红黑树 被提出。相比于AVL树红黑树对高度差的要求适当进行了放松红黑树要求最长路径的节点数目不超过最短路径的两倍。
红黑树的每个节点为红色或黑色通过一定的规则控制节点颜色来达到最长路径节点数目不超过最短路径节点数目两倍的要求这也是红黑树名称的由来。 图1.1 红黑树的结构图 一颗结构正确的红黑树要么为空树要么满足一下几个条件
每个节点为红色或者黑色。根节点为黑色。如果一个节点为红色那么它的两个根节点一定为黑色即红黑树中没有连续的红色节点但是可以有连续的黑色节点。对于每个节点从该节点到其后代叶子结点的路径上黑色节点的数目相同即每条路径的黑色节点数目相同。叶子节点都为黑色节点。注意这里的叶子节点是指NULL节点 为什么满足上面几条规则就能保证最长路径不超过最短路径两倍 极限最短一条路径上全为黑色。极限最长一黑一红间隔排布。
规则4要求每条路径上黑色节点数目相同那么极限最短路径和极限最长路径肯定具有相同数目的黑色节点假设每条路径上黑色节点数目为N那么极限最短路径有N个节点极限最长路径有2N个节点这样就满足了红黑树的路径长度的要求。
二. 红黑树节点的定义
红黑树的节点应当被定义为一个三叉链具有三个红黑树节点指针分别为指向左孩子节点的指针_left、指向右孩子节点的指针_right指向父亲节点的指针_parent。这里存储父亲节点指针的目的是为了在插入数据后检查红黑树结构是否正确以及进行变色及旋转操作。
同时还应当定义Color枚举常量使用_col来表示节点颜色并存储一键值对kv来表示节点数据。
代码2.1红黑树节点
//枚举常量 -- 红色、黑色
enum Color
{RED,BLACK
};//定义红黑树节点
templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;std::pairK, V _kv; //每个节点存储的键值对Color _col; //节点颜色RBTreeNode(const std::pairK, V kv) //节点构造函数: _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){ }
};
三. 红黑树节点的插入
3.1 初步查找插入节点的位置并插入节点
红黑树节点插入位置的查找与普通搜索二叉树和AVL树均一致流程为
如果当前位置为nullptr那么该位置为插入节点的位置。如果当前节点值大于要插入的值到该节点的左子树去查找。如果当前节点值小于要插入的值到该节点的右子树去查找。如果当前节点值等于要插入的值则插入失败。二叉搜索树一般不允许存在相同的节点。
当查找到插入位置后判断是插入到了其父亲节点的左孩子位置还是右孩子位置将新节点与其父亲节点进行连接。
注意新插入的节点应初步设置为红色。因为红黑树要求每条路径上黑色节点数目相同而如果给定新插入的节点为黑色那么根节点的另一颗没有插入数据的子树中也要想办法增加黑色节点数目或旋转来满足结构要求这样后期调整红黑树结构就会变得复杂。而初步设定节点为红色只是有可能存在连续红色节点只需调整新节点所在子树节点的颜色或进行简单旋转即可。
3.2 红黑树结构的调整
红黑树结构调整主要涉及到四个节点通过观察下面四个节点的颜色进行分类讨论采取不同的方法调整红黑树结构
cur节点 -- 新插入的节点。p节点 -- 父亲节点p cur-_parent。g节点 -- 祖父节点g p-_parent。u节点 -- 叔叔节点与p具有共同父亲节点的节点。u-_parent p-_parent g。 图3.1 红黑树结构调整所涉及到的节点示意图 如果p节点为黑色节点则红黑树已经满足结构要求不需要再进行调整如果p节点为红色那么则会存在连续的红色节点要进行调整。对于如何调整分为两大种情况及数种细分情况进行讨论
cur为红p为红g为黑u存在且为红。cur为红p为红g为黑u不存在或u存在且为黑。
由此可以看出u的颜色是如何调整的关键所在。 情况一cur为红p为红g为黑u存在且为红。 将p节点和u节点变为黑色将g节点变为红色然后将cur节点更新为g节点将p节点更新为更新为g-_parent节点继续向上调整。 图3.2 cur为红p为红g为黑u存在且为红时红黑树调整示意图 情况二cur为红p为红g为黑u不存在或u存在且为红。 情况2.1节点cur为p的左子节点p为g的左子节点 -- 右单旋 变色
先对g节点进行右单旋操作然后将p节点变为黑色g节点变为红色。 图3.3 右单旋 变色 示意图 情况2.2节点cur为p的右子节点p为g的右子节点 -- 左单旋 变色
先对g节点进行左单旋操作然后将p节点变为黑色g节点变为红色。 图3.4 左单旋 变色 示意图 情况2.3节点cur为p的右子节点p为g的左子节点 -- 左右双旋 变色
先对p节点进行左单旋然后对g节点进行右单旋最后将cur节点变为黑色将g节点变为红色。 图3.5 左右双旋 变色 示意图 情况2.4节点cur为p的左子节点节点p为g的右子节点 -- 右左双旋 变色
先对p节点进行右单旋然后对g节点进行左单旋最后将cur节点变为黑色将g节点变为红色。 图3.6 右左双旋 变色 示意图 3.3 红黑树节点插入完整版代码 bool insert(const std::pairK, V kv){//插入第一个节点if (_root nullptr){_root new Node(kv);_root-_col BLACK; //根节点为黑色return true;}//寻找节点插入的位置Node* parent nullptr; Node* cur _root;while (cur){//如果cur节点的key值大于插入键值对的key向左子树查找if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if(cur-_kv.first kv.first) //如果cur节点的key值小于插入键值对的key向左子树查找{parent cur;cur cur-_right;}else //相等表明节点已存在插入失败{return false;}}//判断新节点是parent的左节点还是右节点链接//默认新插入的节点为红色cur new Node(kv);cur-_col RED;cur-_parent parent;if (parent-_kv.first kv.first){parent-_left cur;}else{parent-_right cur;}//如果parent节点不为空且为红色那么红黑树的结构在插入节点后被破坏需要调整while (parent parent-_col RED){Node* grandParent parent-_parent; //祖父节点assert(grandParent);assert(grandParent-_col BLACK); //断言检查如果祖父节点为空或为黑色那么红黑树结构在节点插入之前就存在问题if (parent grandParent-_left) //插入在祖父节点的左子树{Node* uncle grandParent-_right;//情况一cur为红parent为红grandFather为黑uncle为红if (uncle uncle-_col RED){//将parent节点和uncle节点变为黑grandFather节点变为红然后继续向上调整parent-_col BLACK;uncle-_col BLACK;grandParent-_col RED;cur grandParent;parent cur-_parent;} else //情况二、三cur为红parent为红grandFather为黑uncle不存在或为黑{if (parent-_left cur){//情况二 -- 进行右单旋 变色(parent变黑,grandFather变红)// g// p u//cRotateR(grandParent);parent-_col BLACK;grandParent-_col RED;}else{//情况三 -- 进行左右双旋 变色cur节点变为黑grandFater节点变为红// g// p u// u RotateLR(grandParent);cur-_col BLACK;grandParent-_col RED;}break;}}else //parent grandParent-_right{Node* uncle grandParent-_left; //叔叔节点//情况一cur为红parent为红grandFather为黑uncle为红if (uncle uncle-_col RED){//将parent节点和uncle节点变为黑grandFather节点变为红然后继续向上调整parent-_col BLACK;uncle-_col BLACK;grandParent-_col RED;cur grandParent;parent cur-_parent;}else{//情况二、三cur为红parent为红grandFather为黑uncle不存在或为黑if (parent-_right cur){//情况二 -- 进行右单旋 变色(parent变黑,grandFather变红)// g// u p// cRotateL(grandParent);parent-_col BLACK;grandParent-_col RED;}else{//情况三 -- 进行右左双旋 变色cur节点变为黑grandFater节点变为红// g// u p// cRotateRL(grandParent);cur-_col BLACK;grandParent-_col RED;}break;}}}_root-_col BLACK; //根节点为黑色return true;}void RotateR(Node* parent) //右单旋函数{Node* pNode parent-_parent; Node* pL parent-_left; //左子节点Node* pLR pL-_right; //左子节点的右子节点//将pLR节点托管给parent节点的左子节点parent-_left pLR;if (pLR ! nullptr){pLR-_parent parent;}//将父亲节点托管给pL节点的右子节点pL-_right parent; parent-_parent pL;//此时这颗进行旋转的子树的根节点变为了pLpL要与pNode节点连接if (parent _root){_root pL;pL-_parent nullptr;}else{pL-_parent pNode;if (pNode-_left parent){pNode-_left pL;}else{pNode-_right pL;}}}void RotateL(Node* parent) //左单旋函数{Node* pNode parent-_parent;Node* pR parent-_right; //右子节点Node* pRL pR-_left; //右子节点的左子节点//将pLR节点托管给parent节点的右子节点parent-_right pRL;if (pRL ! nullptr){pRL-_parent parent;}//将parent节点托管给pR的左子节点pR-_left parent;parent-_parent pR;if (_root parent){_root pR;_root-_parent nullptr;}else{pR-_parent pNode;if (pNode-_left parent){pNode-_left pR;}else{pNode-_right pR;}}}void RotateLR(Node* parent) //左右双旋函数{RotateL(parent-_left);RotateR(parent);}void RotateRL(Node* parent) //右左双旋函数{RotateR(parent-_right);RotateL(parent);}
四. 红黑树的结构检查
4.1 检查是否为搜索树
采用中序遍历得到一串递增的数据即可证明为搜索树。
代码4.1中序遍历 //中序遍历函数void InOrder(){_InOrder(_root);std::cout std::endl;}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);std::cout root-_kv.first ;_InOrder(root-_right);}
4.2 检查节点颜色是否满足要求
需要进行以下两个方面的检查
检查每条路径上的黑色节点数量是否相同。检查是否不存在连续的红色节点。
检查每条路径上的黑色节点数目时可以选取其中一条路径作为基准一般为最左侧路径或最右侧路径通过函数遍历每条路径获取每条路径上的黑色节点数目与基准路径的黑色节点数目进行比较如果不相同则不满足红黑树结构要求。 图4.1 基准路径的选择 红黑树要求红色节点的左右孩子节点必须为黑色但是对孩子节点颜色进行检查较为繁琐因此当遇到红色节点时检查其父亲节点是否为空或者为黑色即可如果红色节点的父亲节点依旧为红色则表明树中存在连续的红色节点不满足红黑树结构要求。
代码4.2节点颜色检查 //红黑树检验函数bool IsRBTree(){//空树是合法的红黑树if (_root nullptr){return true;}//检查根节点颜色if (_root-_col RED){std::cout 根节点颜色不是黑色 std::endl;}int baseBlackNum 0; //基准黑色节点个数//以最左侧路径为基准计算黑色节点个数每条路径黑色节点数目都应该相同Node* cur _root;while (cur){if (cur-_col BLACK){baseBlackNum;}cur cur-_left;}bool blackNumTrue PrevCheck(_root, 0, baseBlackNum); //检查每条路径黑色节点数目是否相同bool colorTrue CheckColor(_root); //检查是否存在连续红色节点return blackNumTrue colorTrue;}bool CheckColor(Node* root){if (root nullptr){return true;}//如果本节点为红色且父亲节点也为红色证明存在连续红色节点结构错误if (root-_col RED root-_parent root-_parent-_col RED){std::cout 存在连续的红色节点 std::endl;return false;}return CheckColor(root-_left) CheckColor(root-_right);}bool PrevCheck(Node* root, int blackNum, int baseBlackNum){if (root nullptr){if (blackNum ! baseBlackNum){std::cout 每条路径上黑色节点的数目不同 std::endl;return false;}else{return true;}}if (root-_col BLACK){blackNum;}return PrevCheck(root-_left, blackNum, baseBlackNum) PrevCheck(root-_right, blackNum, baseBlackNum);}
附录红黑树完整版代码
//枚举常量 -- 红色、黑色
enum Color
{RED,BLACK
};//定义红黑树节点
templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;std::pairK, V _kv; //每个节点存储的键值对Color _col; //节点颜色RBTreeNode(const std::pairK, V kv) //节点构造函数: _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){ }
};//红黑树类模板
templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node; //类型重定义红黑树节点public:bool insert(const std::pairK, V kv){//插入第一个节点if (_root nullptr){_root new Node(kv);_root-_col BLACK; //根节点为黑色return true;}//寻找节点插入的位置Node* parent nullptr; Node* cur _root;while (cur){//如果cur节点的key值大于插入键值对的key向左子树查找if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if(cur-_kv.first kv.first) //如果cur节点的key值小于插入键值对的key向左子树查找{parent cur;cur cur-_right;}else //相等表明节点已存在插入失败{return false;}}//判断新节点是parent的左节点还是右节点链接//默认新插入的节点为红色cur new Node(kv);cur-_col RED;cur-_parent parent;if (parent-_kv.first kv.first){parent-_left cur;}else{parent-_right cur;}//如果parent节点不为空且为红色那么红黑树的结构在插入节点后被破坏需要调整while (parent parent-_col RED){Node* grandParent parent-_parent; //祖父节点assert(grandParent);assert(grandParent-_col BLACK); //断言检查如果祖父节点为空或为黑色那么红黑树结构在节点插入之前就存在问题if (parent grandParent-_left) //插入在祖父节点的左子树{Node* uncle grandParent-_right;//情况一cur为红parent为红grandFather为黑uncle为红if (uncle uncle-_col RED){//将parent节点和uncle节点变为黑grandFather节点变为红然后继续向上调整parent-_col BLACK;uncle-_col BLACK;grandParent-_col RED;cur grandParent;parent cur-_parent;} else //情况二、三cur为红parent为红grandFather为黑uncle不存在或为黑{if (parent-_left cur){//情况二 -- 进行右单旋 变色(parent变黑,grandFather变红)// g// p u//cRotateR(grandParent);parent-_col BLACK;grandParent-_col RED;}else{//情况三 -- 进行左右双旋 变色cur节点变为黑grandFater节点变为红// g// p u// u RotateLR(grandParent);cur-_col BLACK;grandParent-_col RED;}break;}}else //parent grandParent-_right{Node* uncle grandParent-_left; //叔叔节点//情况一cur为红parent为红grandFather为黑uncle为红if (uncle uncle-_col RED){//将parent节点和uncle节点变为黑grandFather节点变为红然后继续向上调整parent-_col BLACK;uncle-_col BLACK;grandParent-_col RED;cur grandParent;parent cur-_parent;}else{//情况二、三cur为红parent为红grandFather为黑uncle不存在或为黑if (parent-_right cur){//情况二 -- 进行右单旋 变色(parent变黑,grandFather变红)// g// u p// cRotateL(grandParent);parent-_col BLACK;grandParent-_col RED;}else{//情况三 -- 进行右左双旋 变色cur节点变为黑grandFater节点变为红// g// u p// cRotateRL(grandParent);cur-_col BLACK;grandParent-_col RED;}break;}}}_root-_col BLACK; //根节点为黑色return true;}//中序遍历函数void InOrder(){_InOrder(_root);std::cout std::endl;}//红黑树检验函数bool IsRBTree(){//空树是合法的红黑树if (_root nullptr){return true;}//检查根节点颜色if (_root-_col RED){std::cout 根节点颜色不是黑色 std::endl;}int baseBlackNum 0; //基准黑色节点个数//以最左侧路径为基准计算黑色节点个数每条路径黑色节点数目都应该相同Node* cur _root;while (cur){if (cur-_col BLACK){baseBlackNum;}cur cur-_left;}bool blackNumTrue PrevCheck(_root, 0, baseBlackNum); //检查每条路径黑色节点数目是否相同bool colorTrue CheckColor(_root); //检查是否存在连续红色节点return blackNumTrue colorTrue;}private:bool CheckColor(Node* root){if (root nullptr){return true;}//如果本节点为红色且父亲节点也为红色证明存在连续红色节点结构错误if (root-_col RED root-_parent root-_parent-_col RED){std::cout 存在连续的红色节点 std::endl;return false;}return CheckColor(root-_left) CheckColor(root-_right);}bool PrevCheck(Node* root, int blackNum, int baseBlackNum){if (root nullptr){if (blackNum ! baseBlackNum){std::cout 每条路径上黑色节点的数目不同 std::endl;return false;}else{return true;}}if (root-_col BLACK){blackNum;}return PrevCheck(root-_left, blackNum, baseBlackNum) PrevCheck(root-_right, blackNum, baseBlackNum);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);std::cout root-_kv.first ;_InOrder(root-_right);}void RotateR(Node* parent) //右单旋函数{Node* pNode parent-_parent; Node* pL parent-_left; //左子节点Node* pLR pL-_right; //左子节点的右子节点//将pLR节点托管给parent节点的左子节点parent-_left pLR;if (pLR ! nullptr){pLR-_parent parent;}//将父亲节点托管给pL节点的右子节点pL-_right parent; parent-_parent pL;//此时这颗进行旋转的子树的根节点变为了pLpL要与pNode节点连接if (parent _root){_root pL;pL-_parent nullptr;}else{pL-_parent pNode;if (pNode-_left parent){pNode-_left pL;}else{pNode-_right pL;}}}void RotateL(Node* parent) //左单旋函数{Node* pNode parent-_parent;Node* pR parent-_right; //右子节点Node* pRL pR-_left; //右子节点的左子节点//将pLR节点托管给parent节点的右子节点parent-_right pRL;if (pRL ! nullptr){pRL-_parent parent;}//将parent节点托管给pR的左子节点pR-_left parent;parent-_parent pR;if (_root parent){_root pR;_root-_parent nullptr;}else{pR-_parent pNode;if (pNode-_left parent){pNode-_left pR;}else{pNode-_right pR;}}}void RotateLR(Node* parent) //左右双旋函数{RotateL(parent-_left);RotateR(parent);}void RotateRL(Node* parent) //右左双旋函数{RotateR(parent-_right);RotateL(parent);}private:Node* _root nullptr;
};
