logo免费设计网站,电商网站功能介绍,广州网站设计与制作公司,伯维网站建设目录
1、什么是红黑树#xff1f;
2、红黑树的相关操作与实现
1、节点定义
2、查找操作
3、插入操作
1、cur为红#xff0c;p为红#xff0c;g为黑#xff0c;cur存在且为红
2、cur为红#xff0c;p为红#xff0c;g为黑#xff0c;u不存在/u存在且为黑
4、判断…目录
1、什么是红黑树
2、红黑树的相关操作与实现
1、节点定义
2、查找操作
3、插入操作
1、cur为红p为红g为黑cur存在且为红
2、cur为红p为红g为黑u不存在/u存在且为黑
4、判断是否为红黑树
3、完整实现代码 1、什么是红黑树 前面的文章我们讲解了AVL树AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度。但是AVL树为了保持平衡要旋转来操作在删除时有可能要一直旋转到根部效率就会比较低下如果数据的个数为静态的(即不会改变)可以考虑AVL树如果一个结构经常修改那么红黑树是个不错的选择。 红黑树Red-Black Tree是一种自平衡的二叉搜索树它在普通的二叉搜索树的基础上增加了一些额外的规则来确保树的高度差别不会太大从而保持了较为稳定的性能。在每个结点上增加一个存储位表示结点的颜色可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。
红黑树的性质 1、每个节点不是黑色就是红色。 2、根节点是黑色的。 3、如果一个节点是红色的那么它的两个孩子是黑色的也就是说不可以有两个连续的红色节点。 4、对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点 5、每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点 个数的两倍 因为不会有两个连续的红色节点而每条路径上面的黑色节点数目都相同所以所有节点的长度只会在 N为每条路径黑色节点的个数而红色节点最多也为N所以所有路径的长度只会在N~2N内。 2、红黑树的相关操作与实现
红黑树与AVL树都是二叉搜索树在插入操作时也使用了左旋与右旋这些在AVL树的文章中也做过讲解可以参考这篇文章数据结构AVL树
1、节点定义
enum Color
{RED,BLACK
};
templateclass valuetype
struct RBTreeNode
{RBTreeNode(const valuetype data valuetype(), Color color RED):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _color(color){}RBTreeNodevaluetype* _left;RBTreeNodevaluetype* _right;RBTreeNodevaluetype* _parent;valuetype _data;Color _color;};
使用枚举类型来表示颜色节点结构与AVL树类似
2、查找操作
红黑树的查找操作与二叉搜索树一致
a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。
b、最多查找高度次走到到空还没找到这个值不存在。
3、插入操作
红黑树是在二叉搜索树的基础上附加了平衡条件来保持特性其最长路径中节点个数不会超过最短路径节点个数的两倍所以它的旋转次数相对AVL树会少一些而深度相比AVL树也不会很大对于计算机来说查找20次和查找40次是差别不大的。
在寻找插入位置方面与AVL树一致只不过在调整保持特性有所不同。
接下来cur表示当前节点p表示该节点的父节点g表示该节点的爷爷节点也就是父节点的父节点u表示叔叔节点也就是父节点的兄弟节点。
1、cur为红p为红g为黑cur存在且为红
p是g的左孩子还是右孩子操作都是一样的 这种情况如图所示将g节点变红p节点和u节点变黑来保证性质4不变。
如果g的父节点为红就违反了性质3需要继续向上调整。
2、cur为红p为红g为黑u不存在/u存在且为黑
1、如果u不存在那么cur一定是新增节点由性质4可以得到。 如果p是g的左孩子cur为左孩子则进行右单旋。
相反如果p是g的右孩子cur为右孩子则进行左单旋。
2、如果u存在且为黑那么cur一定是由1、cur为红p为红g为黑cur存在且为红这种情况调整上来的也是根据性质4就可以推出来每条路径上的黑色节点数目是相同的。
接下来只需要判断需要进行左单旋还是右单旋即可
p是g的左孩子cur是p的左孩子
p是g的右孩子cur是p的右孩子 为保证性质4调整p为黑g为红。
p是g的右孩子cur是p的左孩子 对p做右单旋后仔细观察发现转变为了情况2对g进行左单旋即可。
为保证性质4调整cur为黑g为红。
p是g的左孩子cur是p的右孩子 对p做左单旋后仔细观察发现转变为了情况1对g进行右单旋即可。
为保证性质4调整cur为黑g为红。
根据上述逻辑写出插入操作代码如下
bool Insert(const valuetype data){if (_root nullptr){_root new Node(data, BLACK);//根的双亲为头结点return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_data data){parent cur;cur cur-_right;}else if(cur-_datadata){parent cur;cur cur-_left;}else{return false;}}cur new Node(data, RED);if (cur-_data parent-_data){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;while (parent parent-_color RED){Node* grandparent parent-_parent;if (parent grandparent-_left){Node* uncle grandparent-_right;if (uncle uncle-_color RED){grandparent-_color RED;parent-_color BLACK;uncle-_color BLACK;cur grandparent;parent cur-_parent;}else{if (cur parent-_left){RotateR(grandparent);parent-_color BLACK;grandparent-_color RED;}else{RotateL(parent);RotateR(grandparent);cur-_color BLACK;grandparent-_color RED;}break;}}else{Node* uncle grandparent-_left;if (uncle uncle-_color RED){grandparent-_color RED;parent-_color BLACK;uncle-_color BLACK;cur grandparent;parent cur-_parent;}else{if (cur parent-_right){RotateL(grandparent);parent-_color BLACK;grandparent-_color RED;}else{RotateR(parent);RotateL(grandparent);cur-_color BLACK;grandparent-_color RED;}break;}}}_root-_color BLACK;return true;}
4、判断是否为红黑树
我们主要验证性质3和性质4
bool Check(Node* root, int blacknum, const int refval){if (root nullptr){if (blacknum ! refval){cout 有黑色节点数目不同的路径;return false;}return true;}if (root-_color RED root-_parent-_color RED){cout 存在连续的红色节点;return false;}if (root-_color BLACK){blacknum;}return Check(root-_left, blacknum, refval) Check(root-_right, blacknum, refval);}
每次一条路径走完时我们需要把它和一个标准值来比较验证性质4.
我们走完一条路径得到标准值refval来调用Check递归函数检查。
//判断是否为红黑树bool IsRBTree(){if (_root nullptr)return true;if (_root-_color RED)return false;Node* cur _root;int refval 0;while (cur){if (cur-_color BLACK)refval;cur cur-_left;}return Check(_root, 0, refval); //调用检查函数black为0}
3、完整实现代码
#pragma onceenum Color
{RED,BLACK
};
templateclass valuetype
struct RBTreeNode
{RBTreeNode(const valuetype data valuetype(), Color color RED):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _color(color){}RBTreeNodevaluetype* _left;RBTreeNodevaluetype* _right;RBTreeNodevaluetype* _parent;valuetype _data;Color _color;};templateclass valuetype
class RBTree
{
public:typedef RBTreeNodevaluetype Node;bool Insert(const valuetype data){if (_root nullptr){_root new Node(data, BLACK);//根的双亲为头结点return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_data data){parent cur;cur cur-_right;}else if(cur-_datadata){parent cur;cur cur-_left;}else{return false;}}cur new Node(data, RED);if (cur-_data parent-_data){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;while (parent parent-_color RED){Node* grandparent parent-_parent;if (parent grandparent-_left){Node* uncle grandparent-_right;if (uncle uncle-_color RED){grandparent-_color RED;parent-_color BLACK;uncle-_color BLACK;cur grandparent;parent cur-_parent;}else{if (cur parent-_left){RotateR(grandparent);parent-_color BLACK;grandparent-_color RED;}else{RotateL(parent);RotateR(grandparent);cur-_color BLACK;grandparent-_color RED;}break;}}else{Node* uncle grandparent-_left;if (uncle uncle-_color RED){grandparent-_color RED;parent-_color BLACK;uncle-_color BLACK;cur grandparent;parent cur-_parent;}else{if (cur parent-_right){RotateL(grandparent);parent-_color BLACK;grandparent-_color RED;}else{RotateR(parent);RotateL(grandparent);cur-_color BLACK;grandparent-_color RED;}break;}}}_root-_color BLACK;return true;}void RotateL(Node* parent){Node* sub parent-_right;Node* subl sub-_left;parent-_right subl;sub-_left parent;Node* ppnode parent-_parent;parent-_parent sub;if (subl){subl-_parent parent;}if (parent _root){_root sub;sub-_parent nullptr;}else{if (parent ppnode-_left){ppnode-_left sub;}else{ppnode-_right sub;}sub-_parent ppnode;}}void RotateR(Node* parent){Node* subl parent-_left;Node* subr subl-_right;parent-_left subr;if (subr){subr-_parent parent;}subl-_right parent;Node* ppnode parent-_parent;parent-_parent subl;if (parent _root){_root subl;subl-_parent nullptr;}else{if (parent ppnode-_left){ppnode-_left subl;}else{ppnode-_right subl;}subl-_parent ppnode;}}bool Check(Node* root, int blacknum, const int refval){if (root nullptr){if (blacknum ! refval){cout 有黑色节点数目不同的路径;return false;}return true;}if (root-_color RED root-_parent-_color RED){cout 存在连续的红色节点;return false;}if (root-_color BLACK){blacknum;}return Check(root-_left, blacknum, refval) Check(root-_right, blacknum, refval);}//判断是否为红黑树bool IsRBTree(){if (_root nullptr)return true;if (_root-_color RED)return false;Node* cur _root;int refval 0;while (cur){if (cur-_color BLACK)refval;cur cur-_left;}return Check(_root, 0, refval); //调用检查函数black为0}void _inorder(Node* root){if (root nullptr){return;}_inorder(root-_left);cout root-_data ;_inorder(root-_right);}void inorder(){_inorder(_root);}
private:Node* _rootnullptr;
};以上就是对于红黑树的简单讲解红黑树从根到叶子的最长路径不超过最短路径的两倍长。这确保了树的高度始终保持在对数级别使得查找、插入和删除等操作的时间复杂度始终保持较低水平O(log n)。通过引入颜色标记和自平衡规则提供了一种高效的二叉搜索树实现适用于需要频繁插入、删除和查找操作的场景。
