做优秀企业网站,朋友圈广告投放价格表,网站切换图片做背景怎么写,网站建设字体文章目录 写在前面1. 红黑树的概念及性质1. 1 红黑树的概念1. 2 红黑树的性质 2. 红黑树节点的定义3. 红黑树的插入3.1 按照二叉搜索的树规则插入新节点3.2 检测新节点插入后#xff0c;红黑树的性质是否造到破坏 4.红黑树的删除5.红黑树的验证6.源码 写在前面
在上篇文章中红黑树的性质是否造到破坏 4.红黑树的删除5.红黑树的验证6.源码 写在前面
在上篇文章中我们实现了AVL树AVL树是一种高度平衡的二叉搜索树。通过确保任何节点的左右子树的高度差不超过1AVL树能够维持严格的平衡状态。然而严格平衡的代价是某些插入和删除操作可能需要多次旋转。
本篇文章将实现红黑树它是一种近似平衡的二叉搜索树。红黑树通过维持某些性质来保持树的平衡。通过这些性质红黑树确保从根到叶子的所有路径中最长路径不超过最短路径的两倍从而实现近似平衡。这种近似平衡比AVL树的严格平衡稍松一些使得它在某些插入和删除操作中的效率更高因为它需要的旋转次数较少。
在接下来的内容中我们将详细介绍红黑树的实现过程以及它是如何通过旋转和重新着色来维护红黑树的平衡性。
1. 红黑树的概念及性质
1. 1 红黑树的概念
红黑树是一种二叉搜索树其每个节点存储一个额外的颜色位用于确保树的平衡性。在红黑树中节点的颜色可以是红色或黑色。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。
1. 2 红黑树的性质
红黑树通过以下性质来保持树的平衡 每个节点是红色或黑色。 根节点是黑色。 每个叶子节点NIL节点是黑色。 psNIL节点不是传统意义上的叶子节点而是指空节点是用来方便我们来数路径的。 如果一个节点是红色则它的两个子节点都是黑色不能出现连续的红色节点。 从根节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。
为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍 分析如下
2. 红黑树节点的定义
TreeNode成员的几点解释
枚举类型 Color 用于表示红黑树节点的颜色。红黑树节点只能是红色或黑色。TreeNode 是一个模板结构体用于存储红黑树节点的信息。 _left 指向左孩子节点_right 指向右孩子节点_parent 指向父节点。 _kv 存储节点的键值对类型为 pairK, V其中 K 是键的类型V 是值的类型。 _col 存储节点的颜色类型为 Color。 构造函数初始化节点的左孩子、右孩子和父节点为空指针键值对通过参数传递进来并将节点颜色初始化为红色新插入的节点默认是红色。
enum Color
{RED,BLACK
};
templateclass K, class V
struct TreeNode
{TreeNode* _left; // 左孩子节点TreeNode* _right;// 右孩子节点TreeNode* _parent;// 父节点pairK, V _kv;// 存储键值对Color _col; // 节点颜色// 构造函数TreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)// 新插入的节点初始为红色{}
};3. 红黑树的插入
红黑树就是在二叉搜索树的基础上增加了节点的颜色来控制平衡因此红黑树也可以看成是二叉搜索树。那么红黑树的插入过程可以分为两步
按照二叉搜索树的方式插入新节点。检测新节点插入后红黑树的性质是否造到破坏。
具体操作步骤如下
3.1 按照二叉搜索的树规则插入新节点
具体操作过程参考之前写的文章这里就不在赘述详情参考之前写的这篇文章搜索二叉树这里直接给出插入新节点的具体代码。
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;cur-_parent parent;}else{cur-_parent parent;parent-_left cur;}
}3.2 检测新节点插入后红黑树的性质是否造到破坏
这里涉及的旋转操作参考之前写的文章AVL树C里面详细介绍了旋转操作这里就不在赘述。 因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整 注意下面图片中的树有可能是一颗完整的树也有可能是一颗局部的子树。
但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论 ps:cur为当前节点p为父节点g为祖父节点u为叔叔节点。
情况一: cur为红p为红g为黑u存在且为红。 ps:cur可能是新插入的节点也有可能是在下面插入节点不断往上调整使得cur的颜色变红。
解决方式将p,u改为黑g改为红然后把g当成cur继续向上调整。
ps:如果g是根节点调整完成后需要将g改为黑色; 如果g是子树g一定有双亲且g的双亲如果是红色需要继续向上调整。
情况二: cur为红p为红g为黑u不存在/u存在且为黑 解决方式 cur是p的左孩子以g为旋转点右单旋g变红p变黑调整结束无需向上调整 cur是p的右孩子先以p为旋转点左单旋再以g为旋转点右单旋g变红p变黑调整结束无需向上调整。
1. 如果u节点不存在则cur一定是新插入节点因为如果cur不是新插入节点则cur和p一定有一个节点的颜色是黑色就不满足性质4:每条路径黑色节点个数相同。 2. 如果u节点存在则其一定是黑色的那么cur节点原来的颜色一定是黑色的现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。 p有可能是g的右孩子这种情况下旋转操作与上面的情况相反变色操作还是一样的这里就不在赘述了。 如下图 检测新节点插入后红黑树的性质是否造到破坏的具体代码如下
//插入以后判断是否满足红黑树的规则
//不满足则调整
while (parent parent-_col RED)
{Node* grandfather parent-_parent;//p是g的左孩子if (parent grandfather-_left){Node* uncle grandfather-_right;//u存在且为红if (uncle uncle-_col RED){//变色向上调整parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent grandfather-_parent;}else{//不存在或者存在且为黑//旋转变色//cur 是p的左 以g为旋转点右单旋if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{//cur 是p的右 先以p为旋转点左单旋再以g为旋转点右单旋RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else//p是g的右孩子{Node* uncle grandfather-_left;//u存在且为红if (uncle uncle-_col RED){//变色向上调整parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent grandfather-_parent;}else{//不存在或者存在且为黑//旋转变色//cur 是p的右 以g为旋转点左单旋if (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{//cur 是p的左 先以p为旋转点右单旋再以g为旋转点左单旋RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}
}
_root-_col BLACK;4.红黑树的删除
红黑树的删除和AVL树一样不做深入研究实现红黑树的插入已经足够帮助我们来了解其是如何控制平衡的关于红黑树的删除有兴趣的可参考《算法导论》或者《STL源码剖析》。
5.红黑树的验证
红黑树是在二叉搜索树的基础上加入了平衡性的限制因此要验证红黑树可以分两步
检测其是否满足二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树。 代码如下
void _InOrder(Node* root)
{if (root nullptr) return;_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);
}
void InOrder()
{_InOrder(_root);cout endl;
}检测其是否满足红黑树的性质 不能出现连续的红色节点每条路径上的黑色节点数量相同。
bool _IsRbTree(Node* root, int blacknum, int num)
{if (root nullptr){//判断当前路径和最左路径上的黑色节点数量是否相同if (blacknum ! num)return false;return true;}//当前节点为黑色当前路径上的黑色节点数量加1if (root-_col BLACK) num;Node* parent root-_parent;//判断是否出现连续的红色节点if (root-_col RED parent-_col RED){cout 出现连续的红色节点;return false;}//递归去判断其左右子树是否满足性质return _IsRbTree(root-_left, blacknum, num) _IsRbTree(root-_right, blacknum, num);
}
bool IsRbTree()
{//空树是红黑树if (_root nullptr) return true;if (_root-_col RED) return false;//检查根节点的颜色//统计最左路径黑色节点的数量以其为参考值去判断每条路径上的黑色节点数量是否相同int blacknum 0;Node* cur _root;while (cur){if (cur-_col BLACK){blacknum;}cur cur-_left;}return _IsRbTree(_root, blacknum, 0);
}验证用例 常规场景1 {16, 3, 7, 11, 9, 26, 18, 14, 15}。 特殊场景2{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}。 场景三随机生成N个数字插入验证这里给出代码有兴趣的可以自己去测试一下。
int main()
{const int N 1000;srand((unsigned int)time(nullptr));RBTreeint, int rbTree;for (int i 0; i N; i){int num rand() i;rbTree.insert(make_pair(num, num));}//rbTree.InOrder();cout rbTree.IsRbTree();return 0;
}6.源码
#include iostream
using namespace std;
enum Color
{RED,BLACK
};
templateclass K, class V
struct TreeNode
{TreeNode* _left;TreeNode* _right;TreeNode* _parent;pairK, V _kv;Color _col;TreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};templateclass K, class V
class RBTree
{typedef TreeNodeK, 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 (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;cur-_parent parent;}else{cur-_parent parent;parent-_left cur;}//插入以后判断是否满足红黑树的规则//不满足则调整while (parent parent-_col RED){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent grandfather-_parent;}else{if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateL(parent);RotateR(grandfather);cur-_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 grandfather-_parent;}else{if (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}void InOrder(){_InOrder(_root);cout endl;}bool IsRbTree(){if (_root nullptr) return true;if (_root-_col RED) return false;int blacknum 0;Node* cur _root;while (cur){if (cur-_col BLACK){blacknum;}cur cur-_left;}return _IsRbTree(_root, blacknum, 0);}
private:bool _IsRbTree(Node* root, int blacknum, int num){if (root nullptr){if (blacknum ! num)return false;return true;}if (root-_col BLACK) num;Node* parent root-_parent;if (root-_col RED parent-_col RED){cout 出现连续的红色节点;return false;}return _IsRbTree(root-_left, blacknum, num) _IsRbTree(root-_right, blacknum, num);}void _InOrder(Node* root){if (root nullptr) return;_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;//旋转sub的右子树做parent的左子树//parent做subL的右子树parent-_right subRL;if (subRL){subRL-_parent parent;}Node* pParent parent-_parent;subR-_left parent;parent-_parent subR;//parent为根节点需要将根节点更新为subR if (parent _root){_root subR;subR-_parent nullptr;}else{//更新subR的父节点指针if (subR-_kv.first pParent-_kv.first){pParent-_right subR;}else{pParent-_left subR;}subR-_parent pParent;}}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR){subLR-_parent parent;}Node* pParent parent-_parent;subL-_right parent;parent-_parent subL;if (_root parent){_root subL;subL-_parent nullptr;}else{if (subL-_kv.first pParent-_kv.first){pParent-_right subL;}else{pParent-_left subL;}subL-_parent pParent;}}
private:Node* _root nullptr;
};#include RBTree.h
int main()
{RBTreeint, int rbTree;int nums[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : nums){rbTree.insert(make_pair(e, e));}rbTree.InOrder();cout rbTree.IsRbTree() endl;return 0;
}至此本片文章就结束了若本篇内容对您有所帮助请三连点赞关注收藏支持下。
创作不易白嫖不好各位的支持和认可就是我创作的最大动力我们下篇文章见
如果本篇博客有任何错误请批评指教不胜感激
