如何宣传网站,网站建设方面,怎么在网站上做按钮,网站开发系统绿色版#x1f31f; 快来参与讨论#x1f4ac;#xff0c;点赞#x1f44d;、收藏⭐、分享#x1f4e4;#xff0c;共创活力社区。#x1f31f; 在 C 标准模板库#xff08;STL#xff09;的大家庭里#xff0c;map和set可是超级重要的关联容器成员呢#x1f60e;#x… 快来参与讨论点赞、收藏⭐、分享共创活力社区。 在 C 标准模板库STL的大家庭里map和set可是超级重要的关联容器成员呢它们凭借红黑树这一强大的数据结构实现了查找、插入和删除等操作的高效运行。 现在就让我们一步步深入探索如何亲手基于红黑树打造自定义的map和set容器吧 目录
深入剖析基于红黑树实现自定义 map 和 set 容器
一、红黑树基础结构与操作
1. 红黑树节点结构
2. 红黑树类基本框架
3. 左旋操作
4. 右旋操作
5. 插入修复
6. 插入操作
7. 查找操作
8. 红黑树析构函数 ️
二、自定义 map 和 set 实现 ️
1. 自定义 set 实现
1SetKeyOfT 仿函数
2. 自定义 map 实现 ️
1MapKeyOfT 仿函数
三、测试代码 一、红黑树基础结构与操作
1. 红黑树节点结构 红黑树的节点结构包含节点颜色、父节点指针、左右子节点指针以及存储的数据。 实现思路定义一个结构体来表示红黑树的节点包含节点颜色、父节点指针、左右子节点指针和存储的数据。为方便后续操作节点默认颜色设为红色新插入节点通常为红色有助于维持红黑树性质。代码实现
// 定义红黑树节点颜色
enum Colour {RED,BLACK
};// 红黑树节点结构体
templateclass T
class RBTreeNode {
public:RBTreeNode(const T data) : _data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Colour _col;T _data;
};2. 红黑树类基本框架 实现思路定义红黑树类包含根节点指针。提供插入、查找等基本操作函数声明用于数据的插入、检索同时定义左旋、右旋等内部操作函数声明用于调整树结构维持红黑树性质。代码实现
templateclass K, class T, class KeyOfT
class RBTree {
public:typedef RBTreeNodeT Node;typedef _TreeIteratorT, T, T* iterator;typedef _TreeIteratorT, const T, const T* const_iterator;iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;pairNode*, bool insert(const T data);private:Node* _root nullptr;void RotateL(Node* parent);void RotateR(Node* parent);void RotateRL(Node* parent);void RotateLR(Node* parent);
};3. 左旋操作 实现步骤 保存关键节点指针 保存 parent 的右子节点 subR 和 subR 的左子节点 subRL。 调整 parent 的右子节点 将 parent 的右子节点更新为 subRL。如果 subRL 不为空将 subRL 的父节点指针指向 parent。 调整 subR 的左子节点 将 subR 的左子节点更新为 parent。保存 parent 的父节点 parentParent。将 parent 的父节点指针指向 subR。 更新根节点或父节点的子节点指针 如果 parent 是根节点即 parentParent 为空将 subR 设为新的根节点并将 subR 的父节点指针置为空。否则根据 parent 是 parentParent 的左子节点还是右子节点更新 parentParent 的相应子节点指针为 subR并将 subR 的父节点指针指向 parentParent。
代码实现
templateclass K, class T, class KeyOfT
void RBTreeK, T, KeyOfT::RotateL(Node* parent) { Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL) {subRL-_parent parent;}subR-_left parent;Node* parentParent parent-_parent;parent-_parent subR;if (parentParent nullptr) {_root subR;subR-_parent nullptr;}else {if (parentParent-_left parent) {parentParent-_left subR;}else {parentParent-_right subR;}subR-_parent parentParent;}
}4. 右旋操作 实现思路右旋操作以 parent 为中心交换其与左子节点 subL 位置调整 subLR 指针更新根或父节点指向维持平衡代码实现
templateclass K, class T, class KeyOfT
void RBTreeK, T, KeyOfT::RotateR(Node* parent) { Node* subL parent-_left;Node* subLR subL-_right;parent-_left subL-_right;if (subLR) {subLR-_parent parent;}subL-_right parent;Node* parentParent parent-_parent;parent-_parent subL;if (parentParent nullptr) {_root subL;subL-_parent nullptr;}else {if (parentParent-_left parent) {parentParent-_left subL;}else {parentParent-_right subL;}subL-_parent parentParent;}
}5. 插入修复 实现思路插入新节点后红黑树的性质可能会被破坏需要进行修复操作。修复操作主要根据新节点的父节点和叔节点的颜色进行分类处理通过旋转和颜色调整来恢复红黑树的性质。代码实现
pairNode*,bool insert(const T data)
{if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(_root, true);}Node* cur _root;Node* parent nullptr;KeyOfT kot;while (cur){parent cur;if (kot(cur-_data) kot(data)){cur cur-_right;}else if (kot(cur-_data) kot(data)){cur cur-_left;}else{return make_pair(cur, false);}}//新增结点给红色cur new Node(data);Node* newNode cur;cur-_parent parent;if (kot(parent-_data) kot(cur-_data)){parent-_right cur;}else{parent-_left cur;}while (parent parent-_col RED){//找叔叔Node* grandfather parent-_parent;Node* uncle nullptr;if (parent grandfather-_left){uncle grandfather-_right;}else{uncle grandfather-_left;}if (uncle uncle-_col RED)//满足规则一父亲和叔叔变黑爷爷变红{parent-_col uncle-_col BLACK;grandfather-_col RED;//继续向上更新cur grandfather;parent grandfather-_parent;}else //叔叔 不存在 或 存在且为黑{if (parent grandfather-_left cur parent-_left)//右单旋{RotateR(grandfather);//变色parent-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_right cur parent-_right)//左单旋{RotateL(grandfather);//变色parent-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_left cur parent-_right)//折射双旋{RotateLR(grandfather);//变色cur-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_right cur parent-_left)//折射双旋{RotateRL(grandfather);//变色cur-_col BLACK;grandfather-_col RED;}}}_root-_col BLACK;return make_pair(newNode, true);
} 6. 插入操作 实现思路首先找到合适的插入位置创建新节点并插入到树中然后调用插入修复函数来恢复红黑树的性质。代码实现
templateclass K, class T, class KeyOfT
pairtypename RBTreeK, T, KeyOfT::Node*, bool RBTreeK, T, KeyOfT::insert(const T data) {if (_root nullptr) {_root new Node(data);_root-_col BLACK;return make_pair(_root, true);}Node* cur _root;Node* parent nullptr;KeyOfT kot;while (cur) {parent cur;if (kot(cur-_data) kot(data)) {cur cur-_right;}else if (kot(cur-_data) kot(data)) {cur cur-_left;}else {return make_pair(cur, false);}}// 插入新节点并设置颜色cur new Node(data);Node* newNode cur;cur-_parent parent;if (kot(parent-_data) kot(cur-_data)) {parent-_right cur;}else {parent-_left cur;}while (parent parent-_col RED) {// 情况分类Node* grandfather parent-_parent;Node* uncle nullptr;if (parent grandfather-_left) {uncle grandfather-_right;}else {uncle grandfather-_left;}if (uncle uncle-_col RED) { // 叔叔节点存在且为红色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上调整cur grandfather;parent grandfather-_parent;}else { // 叔叔节点不存在或为黑色if (parent grandfather-_left cur parent-_left) { // 左左情况RotateR(grandfather);// 调整颜色parent-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_right cur parent-_right) { // 右右情况RotateL(grandfather);// 调整颜色parent-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_left cur parent-_right) { // 左右情况RotateLR(grandfather);// 调整颜色cur-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_right cur parent-_left) { // 右左情况RotateRL(grandfather);// 调整颜色cur-_col BLACK;grandfather-_col RED;}}}_root-_col BLACK;return make_pair(newNode, true);
}7. 查找操作 实现思路从根节点开始根据键的大小比较递归地在左子树或右子树中查找目标节点。代码实现
templateclass K, class T, class KeyOfT
RBTreeNodeT* RBTreeK, T, KeyOfT::Find(const K key) {RBTreeNodeT* current _root;KeyOfT kot;while (current) {if (key kot(current-_data)) {current current-_left;}else if (key kot(current-_data)) {current current-_right;}else {return current;}}return nullptr;
}8. 红黑树析构函数 ️ 实现思路采用后序遍历的方式递归删除树中的所有节点释放内存。代码实现
templateclass K, class T, class KeyOfT
RBTreeK, T, KeyOfT::~RBTree() {auto destroyTree [](RBTreeNodeT* node) {if (node ! nullptr) {destroyTree(node-left);destroyTree(node-right);delete node;}};destroyTree(_root);
}二、自定义 map 和 set 实现 ️
1. 自定义 set 实现
1SetKeyOfT 仿函数 实现思路由于set中存储的元素就是键因此仿函数直接返回元素本身。代码实现
namespace zdf {templateclass Kclass set {public:struct SetKeyOfT {const K operator()(const K key) {return key;}};// 定义迭代器类型typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator;typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator;iterator begin() const {return _t.begin();}iterator end() const {return _t.end();}pairiterator, bool insert(const K key) {return _t.insert(key);}private:RBTreeK, K, SetKeyOfT _t;};
}2. 自定义 map 实现 ️
1MapKeyOfT 仿函数 实现思路map中存储的是键值对仿函数从键值对中提取键。代码实现
namespace zdf {templateclass K, class Vclass map {struct MapKeyOfT {const K operator()(const std::pairK, V kv) {return kv.first;}};public:typedef typename RBTreeK, std::pairconst K, V, MapKeyOfT::iterator iterator;typedef typename RBTreeK, std::pairconst K, V, MapKeyOfT::const_iterator const_iterator;iterator begin() {return _t.begin();}iterator end() {return _t.end();}V operator[](const K key) {std::pairiterator, bool ret insert(std::make_pair(key, V()));return ret.first-second;}pairiterator, bool insert(const std::pairK, V kv) {return _t.insert(kv);}private:RBTreeK, std::pairconst K, V, MapKeyOfT _t;};
}三、测试代码
#include iostreamint main() {// 测试setzdf::setint s;s.insert(3);s.insert(1);s.insert(2);// 测试mapzdf::mapint, std::string m;m.insert({ 1, one });m.insert({ 2, two });m[3] three;std::cout Map value at key 3: m[3] std::endl;return 0;
}通过以上步骤我们基于红黑树实现了自定义的map和set容器每个函数的实现思路和代码都进行了详细讲解。这些实现展示了红黑树在关联容器中的重要应用以及如何通过封装和扩展红黑树来实现高效的数据存储和操作。
欢迎关注我 【A charmer】
