中学生网站制作,装饰公司网页设计,建网方案策划书,电信网站备案查询文章目录 红黑树概念性质#xff08;条件限制#xff09;节点的定义红黑树的结构红黑树的插入cur为红#xff0c;p为红#xff0c;g为黑#xff0c;u存在且为红cur为红#xff0c;p为红#xff0c;g为黑#xff0c;u不存在或u为黑#xff0c;插入到p对应的一边cur为红… 文章目录 红黑树概念性质条件限制节点的定义红黑树的结构红黑树的插入cur为红p为红g为黑u存在且为红cur为红p为红g为黑u不存在或u为黑插入到p对应的一边cur为红p为红g为黑u不存在或u存在且为黑插入到与p相反的一边示例代码 红黑树的验证红黑树与AVL树的比较 完整代码 红黑树
概念
和AVL树一样红黑树也是一种二叉搜索树是解决二叉搜索树不平衡的另一种方案他在每个节点上增加一个存储位用于表示节点的颜色是Red或者Black
红黑树的核心思想是通过一些着色的条件限制达到一种最长路径不超过最短路径的两倍的状态
所以说红黑树并不是严格平衡的树而是一种近似平衡
例如 性质条件限制
红黑树一共有五条性质由此来保证最长路径不超过最短路径的两倍
每个节点都有颜色不是黑色就是红色根节点是黑色的如果一共节点是红色那么他的子节点一定是黑色不会出现两个红色节点连接的情况对于每个节点以这个节点到所有后代的任意路径上均包含相同数目的黑色节点每个叶子节点空节点是黑色的为了满足第四条性质某些情况下如果没有第五条第四条会失效
节点的定义
// 颜色
enum Color {RED,BLACK
};templateclass T
struct RBTreeNode {RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Color _col;RBTreeNode(const T data) :_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}
};我们定义颜色时使用枚举类型可以方便且明了的看到颜色
除此之外我们默认插入节点是红色的因为一旦插入节点是黑色就会违反第四条规则如果要满足的话就要走到每一条路径上插入对应的黑色节点代价巨大
当插入节点是红色时有可能会违反第三条规则但是我们可以通过变色旋转等操作在局部进行改变这样就能使之仍然满足条件
红黑树的结构
为了后续利用红黑树封装map和set我们对红黑树增加一个头节点为了和根节点进行区分我们将头节点赋为黑色并且让头节点的parent指向根节点left指向红黑树的最小节点right指向最大节点如图 红黑树的插入
红黑树插入时也是按照二叉搜索树的规则进行插入并在此基础上加上平衡条件因此插入也就分为两步
按照二叉搜索树的规则插入新节点插入节点后检测规则是否被破坏
因为插入红节点时只有可能破坏第三条规则因此我们只需要判断父节点是否为红色即可
然后我们分情况讨论
为了方便叙述我们约定cur为插入节点p为父节点g为祖父节点u为叔叔节点
cur为红p为红g为黑u存在且为红
画出来是这样的 这时我们需要将g改为红色p和u改为黑色即可这样既能保证红色不连续黑色数量一致如图 但是如果g是是子树那么g一定有父节点当g的父节点也是红色时也就同样需要向上调整了
cur为红p为红g为黑u不存在或u为黑插入到p对应的一边
画出来是这样的 u的情况有两种
u节点不存在说明cur一定是新插入的节点因为要保证左右两个路径的黑色节点的数量相同u节点存在说明cur节点是由下至上调整的红色原因也是左右路径的黑色节点要相同
对于这两种情况的调整方法是相同的如果p是g的左节点cur为p的左节点则右单旋如果p是g的右节点cur为p的右节点则左单旋
同时p要变成黑色g要变成红色
变成如下状态 那么因为最上面的根节点颜色没有变化也就不需要继续向上调整了
cur为红p为红g为黑u不存在或u存在且为黑插入到与p相反的一边
如图 这种情况需要针对p进行单旋如果p为g的左节点cur为p的右节点则对p左单旋反之则为右单旋此时就会变成第二种情况再继续处理即可
第一次处理的结果如下 示例代码
templateclass K, class T, class KeyOfT
class RBTree {typedef RBTreeNodeT Node;
public:pairNode*, bool Insert(const T data) {// 插入根节点直接返回if (_root nullptr) {_root new Node(data);_root-_col BLACK;return make_pair(_root, true);}Node* parent nullptr;Node* cur _root;KeyOfT kot;// 平衡二叉树找到插入位置while (cur) {if (kot(cur-_data) kot(data)) {parent cur;cur cur-_right;} else if (kot(cur-_data) kot(data)) {parent cur;cur cur-_left;} else {return make_pair(cur, false);}}// 新建节点cur new Node(data);Node* newnode cur;cur-_col RED;// 连接父节点if (kot(parent-_data) kot(data)) {parent-_right cur;cur-_parent parent;} else {parent-_left cur;cur-_parent parent;}// 如果父节点存在且父节点为红色则需要调整while (parent parent-_col RED) {Node* grandfather parent-_parent;if (parent grandfather-_left) {// g// p u// c // 判断u是否存在和他的颜色Node* uncle grandfather-_right;// 如果存在且为红色if (uncle uncle-_col RED) {// 变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 向上调整cur grandfather;parent cur-_parent;} else {// 如果不存在或u为黑色需要判断同侧还是异侧// 如果是同侧if (cur parent-_left) {// g// p// cRotateR(grandfather); // 右旋// 调整颜色parent-_col BLACK;grandfather-_col RED;} else {// g// p// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}} else { // p g-rNode* uncle grandfather-_left;// g// u p// c// 判断u是否存在和他的颜色// 如果存在且为红色if (uncle uncle-_col RED) {// 变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 向上调整cur grandfather;parent cur-_parent;} else {if (cur parent-_right) {RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;} else {// g// u p // c//RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return make_pair(newnode, true);}void RotateL(Node* parent) {Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subR-_left parent;Node* parentParent parent-_parent;parent-_parent subR;if (subRL)subRL-_parent parent;else {if (parentParent-_left parent) {parentParent-_left subR;} else {parentParent-_right subR;}subR-_parent parentParent;}}void RotateR(Node* parent) {Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* parentParent parent-_parent;subL-_right parent;parent-_parent subL;if (_root parent) {_root subL;subL-_parent nullptr;} else {if (parentParent-_left parent) {parentParent-_left subL;} else {parentParent-_right subL;}subL-_parent parentParent;}}
private:Node* _root nullptr;
};红黑树的验证
红黑树要验证需要验证两个部分
检测是否中序遍历是有序序列检测是否满足红黑树的性质
这里我们就不讲红黑树的删除了完成红黑树的验证之后就算作已经完成了任务接下来会使用红黑树模拟实现map和set
红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树但是红黑树不追求绝对的平衡降低了插入和旋转的次数因此性能比AVL更优而且红黑树比AVL树的实现更加简单所以实际中运用红黑树更多
完整代码
#pragma once
#includeutility
#includeiostream
using namespace std;
// 颜色
enum Color {RED,BLACK
};templateclass T
struct RBTreeNode {RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Color _col;RBTreeNode(const T data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED) {}
};templateclass K, class T, class KeyOfT
class RBTree {typedef RBTreeNodeT Node;
public:pairNode*, bool Insert(const T data) {if (_root nullptr) {_root new Node(data);_root-_col BLACK;return make_pair(_root, true);}Node* parent nullptr;Node* cur _root;KeyOfT kot;// 平衡二叉树找到插入位置while (cur) {if (kot(cur-_data) kot(data)) {parent cur;cur cur-_right;} else if (kot(cur-_data) kot(data)) {parent cur;cur cur-_left;} else {return make_pair(cur, false);}}// 新建节点cur new Node(data);Node* newnode cur;cur-_col RED;// 连接父节点if (kot(parent-_data) kot(data)) {parent-_right cur;cur-_parent parent;} else {parent-_left cur;cur-_parent parent;}// 如果父节点存在且父节点为红色则需要调整while (parent parent-_col RED) {Node* grandfather parent-_parent;if (parent grandfather-_left) {// g// p u// c // 判断u是否存在和他的颜色Node* uncle grandfather-_right;// 如果存在且为红色if (uncle uncle-_col RED) {// 变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 向上调整cur grandfather;parent cur-_parent;} else {// 如果不存在或u为黑色需要判断同侧还是异侧// 如果是同侧if (cur parent-_left) {// g// p// cRotateR(grandfather); // 右旋// 调整颜色parent-_col BLACK;grandfather-_col RED;} else {// g// p// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}} else { // p g-rNode* uncle grandfather-_left;// g// u p// c// 判断u是否存在和他的颜色// 如果存在且为红色if (uncle uncle-_col RED) {// 变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 向上调整cur grandfather;parent cur-_parent;} else {if (cur parent-_right) {RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;} else {// g// u p // c//RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return make_pair(newnode, true);}void RotateL(Node* parent) {Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subR-_left parent;Node* parentParent parent-_parent;parent-_parent subR;if (subRL)subRL-_parent parent;else {if (parentParent-_left parent) {parentParent-_left subR;} else {parentParent-_right subR;}subR-_parent parentParent;}}void RotateR(Node* parent) {Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* parentParent parent-_parent;subL-_right parent;parent-_parent subL;if (_root parent) {_root subL;subL-_parent nullptr;} else {if (parentParent-_left parent) {parentParent-_left subL;} else {parentParent-_right subL;}subL-_parent parentParent;}}void InOrder() {_InOrder(_root);cout endl;}void _InOrder(Node* root) {if (root nullptr)return;_InOrder(root-_left);cout root-_data ;_InOrder(root-_right);}bool Check(Node* root, int blacknum, const int refVal) {if (root nullptr) {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 leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH;}size_t Size() {return _Size(_root);}size_t _Size(Node* root) {if (root nullptr)return 0;return _Size(root-_left) _Size(root-_right) 1;}Node* Find(const K key) {Node* cur _root;while (cur) {if (cur-_data key) {cur cur-_right;}else if (cur-_data key) {cur cur-_left;}else {return cur;}}return nullptr;}private:Node* _root nullptr;
};
