建设银行网站为什么打不开,推广文案撰写,高州网站开发公司,wordpress+绿色【c底层结构】AVL树红黑树 1.AVL树1.1 AVL树的概念1.2 AVL树结点的定义1.3 AVL树的插入1.4 AVL树的旋转1.5 AVL树的验证1.6 AVL树的性能 2. 红黑树2.1 红黑树的概念2.2 红黑树的性质2.3 红黑树节点的定义2.4 红黑树的插入操作2.5 红黑树的验证2.6 红黑树与AVL树的比较2.7 … 【c底层结构】AVL树红黑树 1.AVL树1.1 AVL树的概念1.2 AVL树结点的定义1.3 AVL树的插入1.4 AVL树的旋转1.5 AVL树的验证1.6 AVL树的性能 2. 红黑树2.1 红黑树的概念2.2 红黑树的性质2.3 红黑树节点的定义2.4 红黑树的插入操作2.5 红黑树的验证2.6 红黑树与AVL树的比较2.7 红黑树的应用2.8 红黑树模拟实现STL中的map与set 3 .map和set的模拟实现3.1 map的模拟实现3.2 set的模拟实现3.3 改造红黑树 1.AVL树
1.1 AVL树的概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adeksib-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1需要对树中的结点进行调整即可降低树的高度从而减少平均搜索长度。
它的左右子树都是AVL树左右子树高度之差平衡因子的绝对值不超过1-1/1/0) 如果一颗二叉树是高度平衡的它就是AVL、如果它有n个结点其高度可保持在O(log2N),搜索时间复杂度O(log2N)
1.2 AVL树结点的定义
templateclass K,class V
class AVLTreeNode
{AVLTreeNodeK, V* _left; //该节点的左孩子 AVLTreeNodeK, V* _right; //该节点的右孩子AVLTreeNodeK, V* _parent; //该节点的父结点pairK, V _kv; //该节点的左孩子int _bf;//balance factor //该节点的平衡因子AVLTreeNode(const pairK, V kv):_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _bf(0) {}
};1.3 AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么AVL树的插入 过程可以分为两步 按照二叉搜索树的方式插入新节点 调整节点的平衡因子
1、更新平衡因子 1、cur parent-_right parent-bf 2、cur parent-_left parent-bf– 2、如果更新完以后平衡因子没有出现问题|bf|1平衡结构没有受到影响不需要处理 3、如果更新完以后平衡出现问题平衡结构受到影响需要处理旋转
什么决定了是否要继续往上更新parent所在的子树高度是否变化变了继续更新不变就不再更新。 1、parent-bf 1 || parent-bf -1 -- parent所在的子树变了继续更新。0-1 ||0--1) 2、parent-bf2||parent-bf -2 --parent所在的子树不平衡。需要处理这棵子树旋转处理)。 3、parent-bf 0 parent所在的子树高度不变不用继续往上更新插入结束。(-1-0,1-0parent子树高度不变) 1.4 AVL树的旋转 旋转的原则保持搜索树的性质 旋转的目的左右均衡降低整棵树的高度 如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡 化。根据节点插入位置的不同AVL树的旋转分为四种
首先我们来分析两种简单的旋转单旋 我们可以将需要单旋的情况抽象为下图所示的抽象图 简单分析当h1h2;h3
新节点插入较高右子树的右侧—右右左单旋
void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;//链接parent和subRL 并更新三叉链parent-_right subRL;if(subRL!nullptr)subRL-_parent parent;Node* ppnode parent-_parent;//链接subR和parent并更新三叉链subR-_left parent;parent-_parent subR;//parent为根节点if (ppnode nullptr){_root subR;_root-_parent nullptr;}//parent不为根节点else{//与ppnode链接if (ppnode-_left parent){ppnode-_left subR}else{ppnode-_right subR;;}subR-_parent ppnode;}//更新平衡因子parent-_bf subR-_bf 0;}
新节点插入较高左子树的左侧–左左右单旋
代码
void RotateR(Node * parent){Node* subL parent-_left;Node* subLR subL-_right;Node* ppnode parent-_parent;subL-_right parent;parent-_parent subL;parent-_left subLR;if (subLR ! nullptr)subLR-_parent parent;if (ppnode nullptr){_root subL;_root-_parent nullptr;}else{if (ppnode__left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}parent-_bf subL-_bf 0;}接下来我们继续分析双旋的情况。 抽象图如下
具象图如图下 吧
新节点插入较高左子树的右侧—左右先左单旋再右单旋 void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 1){parent-_bf 0;subLR-_bf 0;subL-_bf -1;}else if (bf -1){parent-_bf 1;subLR-_bf 0;subL-_bf 0;}else if (bf 0){parent-_bf 0;subLR-_bf 0;subL-_bf 0;}else{assert(false);}}新节点插入较高右子树的左侧—右左先右单旋再左单旋 RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 1){parent-_bf -1;subRL-_bf 0;subR-_bf 0;}else if (bf -1){parent-_bf 0;subRL-_bf 0;subR-_bf 1;}else if (bf 0){parent-_bf 0;subRL-_bf 0;subR-_bf 0;}else{assert(false);}}1.5 AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步
验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子) 节点的平衡因子是否计算正确
int _Height(PNode pRoot);
bool _IsBalanceTree(PNode pRoot)
{// 空树也是AVL树if (nullptr pRoot) return true;// 计算pRoot节点的平衡因子即pRoot左右子树的高度差int leftHeight _Height(pRoot-_pLeft);int rightHeight _Height(pRoot-_pRight);int diff rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等或者// pRoot平衡因子的绝对值超过1则一定不是AVL树if (diff ! pRoot-_bf || (diff 1 || diff -1))return false;// pRoot的左和右如果都是AVL树则该树一定是AVL树return _IsBalanceTree(pRoot-_pLeft) _IsBalanceTree(pRoot-_pRight);
}1.6 AVL树的性能 AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证 查询时高效的时间复杂度即 。但是如果要对AVL树做一些结构修改的操作性能非常低下比如 插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。 因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树 但一个结构经常修改就不太适合。 全部代码 #pragma once
#includeassert.h
#includeiostream
#includeset
#includemap
#includestring
using namespace std;
templateclass K,class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf;//balance factorAVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};
template class K,class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//更新平衡因子while (parent){if (cur parent-_right){parent-_bf;}else{parent-_bf--;}if (parent-_bf 1 || parent-_bf -1){//继续更新parent parent-_parent;cur cur-_parent;}else if (parent-_bf 0){break;}else if(parent-_bf 2 || parent-_bf -2){//旋转处理 1、让子树平衡2、降低这棵子树的高度if (parent-_bf 2 cur-_bf 1){RotateL(parent);}else if (parent-_bf -2 cur-_bf -1){RotateR(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}else{assert(false);}break;}//在插入前平衡结构已经出现问题else{assert(false);}}return true;}void InOrder(){_InOrder(_root);cout endl;}bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}
private:void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}int _Height(Node* root){if (root NULL)return 0;int leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;}bool _IsBalance(Node* root){if (root NULL){return true;}int leftH _Height(root-_left);int rightH _Height(root-_right);if (rightH - leftH ! root-_bf){cout root-_kv.first 节点平衡因子异常 endl;return false;}return abs(leftH - rightH) 2 _IsBalance(root-_left) _IsBalance(root-_right);}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;//链接parent和subRL 并更新三叉链parent-_right subRL;if(subRL!nullptr)subRL-_parent parent;Node* ppnode parent-_parent;//链接subR和parent并更新三叉链subR-_left parent;parent-_parent subR;//parent为根节点if (ppnode nullptr){_root subR;_root-_parent nullptr;}//parent不为根节点else{//与ppnode链接if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;;}subR-_parent ppnode;}//更新平衡因子parent-_bf subR-_bf 0;}void RotateR(Node * parent){Node* subL parent-_left;Node* subLR subL-_right;Node* ppnode parent-_parent;subL-_right parent;parent-_parent subL;parent-_left subLR;if (subLR ! nullptr)subLR-_parent parent;if (ppnode nullptr){_root subL;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}parent-_bf subL-_bf 0;}void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 1){parent-_bf 0;subLR-_bf 0;subL-_bf -1;}else if (bf -1){parent-_bf 1;subLR-_bf 0;subL-_bf 0;}else if (bf 0){parent-_bf 0;subLR-_bf 0;subL-_bf 0;}else{assert(false);}}void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 1){parent-_bf -1;subRL-_bf 0;subR-_bf 0;}else if (bf -1){parent-_bf 0;subRL-_bf 0;subR-_bf 1;}else if (bf 0){parent-_bf 0;subRL-_bf 0;subR-_bf 0;}else{assert(false);}}private:Node* _root nullptr;
};
void Test_AVLTree1()
{int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree int, int t1;for (auto e : a){t1.Insert(make_pair(e,e));}t1.InOrder();
}
void Test_AVLTree2()
{srand(time(0));const size_t N 5000000;AVLTreeint, int t;for (size_t i 0; i N; i){size_t x rand() i;t.Insert(make_pair(x, x));//cout t.IsBalance() endl;}//t.Inorder();cout t.IsBalance() endl;cout t.Height() endl;
}2. 红黑树
2.1 红黑树的概念 红黑树是一种二叉搜索树但在每个节点上增加一个存储位表示节点的颜色可以是Red或Black通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径必其它路径长出两倍因而是接近平衡的。 2.2 红黑树的性质
每个节点不是红色就是黑色根节点是黑色的如果一个节点是红色的那么他的两个孩子结点是黑色的对于每个节点从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色结点每个叶子节点都是黑色的NIL结点
2.3 红黑树节点的定义
// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
templateclass ValueType
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Color _col;RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
我们在这里选择将默认的节点颜色给成红色是因为插入新节点时如果是黑色的话一定会违反上述红黑树性质的第四条其次这个节点的插入会影响到每一条路径如果是红的的话有可能会违反第三条同时如果造成了影响影响到的也只是局部。
2.4 红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步
按照二叉搜索树的规则插入新节点 bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//TODO 调整红黑树结构return true;}检测新节点插入以后红黑树的性质是否遭到破坏
因为新节点的默认颜色是红色因此如果其双亲结点的颜色是黑色没有违反红黑树任何性质则不需要调整单当插入节点的双亲节点颜色为红色时就违反了性质三不能有连续的红色节点此时就需要对红黑树分情况讨论。 首先我们先对特殊情况进行一个分析、对红黑树的节点调整建立初步印象。 接下来我们对更一般的情况进行分析
情况一cur为红 p为红g为黑u存在且为红解决方法parent 变黑 uncle变黑 grandfather变红 然后继续向上调整· 将上面的步骤翻译为代码就是
if (uncle uncle-_col RED)
{parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;
}情况二 cur为红p为红g为黑u不存在/u为黑单旋 说明u的情况有两种 1、如果u结点不存在则cur一定是新插入结点因为如果cur不是新插入节点则cur和p一定有一个节点的颜色是黑色就不满足性质4每条路经黑色节点个数相同。 2、如果u结点存在则其一定是黑色那么cur结点原来的颜色一定是黑色的现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改为红色 p为g的左孩子cur为p的左孩子则进行右单旋变色p变黑g变红 p为g的右孩子cur为p的右孩子则进行左单旋变色p变黑g变红 情况三 cur为红p为红g为黑u不存在/u为黑双旋)
p为g的左孩子cur为p的右孩子p做左单旋g右单旋变色p变黑g变红 p为g的右孩子cur为p的左孩子p做右单旋g左单旋变色p变黑g变红 在写代码的时候需要对up之间的关系进行分类因为这会影响到旋转的方向 将上面三种情况翻译为代码如下 while (parent ! nullptr parent-_col RED)
{Node* grandfather parent-_parent;if (grandfather-_left parent){Node* uncle grandfather-_right;//情况1uncle存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}//情况23uncle不存在/uncle存在且为黑旋转变色else {// g// p u// cif (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}// g// p u// celse{RotateL(parent);RotateR(grandfather);cur-_col BLACK;//parent-_col RED;grandfather-_col RED;}break;}}else//(grandfather-_right parent){// g// u p// cNode* uncle grandfather-_left;//情况1uncle存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}//情况23uncle不存在/uncle存在且为黑旋转变色else{// g// u p// cif (cur parent-_right){RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}
}
_root-_col BLACK;2.5 红黑树的验证
红黑树的检测分为两步
检测其是否满足二叉搜索树(中序遍历是否为有序序列)检测其是否满足红黑树的性质每条路径黑色节点数量相同
bool _Check(Node* root, int blackNum, int benchmark)
{if (root nullptr){if (benchmark ! blackNum){cout 某条路径黑色节点的数量不相等 endl;return false;}return true;}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return _Check(root-_left, blackNum, benchmark) _Check(root-_right, blackNum, benchmark);
}
bool IsBalance()
{if (_root _root-_col RED){cout 根节点颜色是红色 endl;return false;}int benchmark 0;//基准点(最左路经黑色节点的数量)Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}//连续红色结点return _Check(_root, 0, benchmark);
}全部代码
#pragma once
#includeassert.h
#includeiostream
#includeset
#includemap
#includestring
using namespace std;
enum Color
{RED,BLACK,
};
templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Color _col;RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};
templateclass K,class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:~RBTree(){_Destroy(_root);_root nullptr;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){cur cur -_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return nullptr;}bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;while (parent ! nullptr parent-_col RED){Node* grandfather parent-_parent;if (grandfather-_left parent){Node* uncle grandfather-_right;//情况1uncle存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}//情况23uncle不存在/uncle存在且为黑旋转变色else {// g// p u// cif (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}// g// p u// celse{RotateL(parent);RotateR(grandfather);cur-_col BLACK;//parent-_col RED;grandfather-_col RED;}break;}}else//(grandfather-_right parent){// g// u p// cNode* uncle grandfather-_left;//情况1uncle存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}//情况23uncle不存在/uncle存在且为黑旋转变色else{// g// u p// cif (cur parent-_right){RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}void InOrder(){_InOrder(_root);cout endl;}bool IsBalance(){if (_root _root-_col RED){cout 根节点颜色是红色 endl;return false;}int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}//连续红色结点return _Check(_root, 0, benchmark);}int Height(){return _Height(_root);}
private:void _Destroy (Node* root){if (root nullptr){return;}_Destroy(root-_left);_Destroy(root-_right);delete root;}int _Height(Node* root){if (root nullptr)return 0;int leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;}bool _Check(Node* root, int blackNum, int benchmark){if (root nullptr){if (benchmark ! blackNum){cout 某条路径黑色节点的数量不相等 endl;return false;}return true;}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return _Check(root-_left, blackNum, benchmark) _Check(root-_right, blackNum, benchmark);}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;//链接parent和subRL 并更新三叉链parent-_right subRL;if (subRL ! nullptr)subRL-_parent parent;Node* ppnode parent-_parent;//链接subR和parent并更新三叉链subR-_left parent;parent-_parent subR;//parent为根节点if (ppnode nullptr){_root subR;_root-_parent nullptr;}//parent不为根节点else{//与ppnode链接if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;Node* ppnode parent-_parent;subL-_right parent;parent-_parent subL;parent-_left subLR;if (subLR ! nullptr)subLR-_parent parent;if (ppnode nullptr){_root subL;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}}
private:Node* _root;
};
void Test_RBTree1()
{int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTree int, int t1;for (auto e : a){t1.Insert(make_pair(e, e));}t1.InOrder();
}
void Test_RBTree2()
{srand(time(0));const size_t N 5000000;RBTreeint, int t;for (size_t i 0; i N; i){size_t x rand() i;t.Insert(make_pair(x, x));cout t.IsBalance() endl;}//t.Inorder();
}2.6 红黑树与AVL树的比较
红黑树和AVL树都是搞笑的平衡二叉树增删查改的时间复杂度都是O( log2N)红黑树不追求绝对平衡其 只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构 中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。
2.7 红黑树的应用
C STL库 – maJava 库linux内核其他一些库
2.8 红黑树模拟实现STL中的map与set
迭代器的好处是可以方便遍历是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器需要考 虑以前问题 begin()与end() STL明确规定begin()与end()代表的是一段前闭后开的区间而对红黑树进行中序遍历后可以得到一 个有序的序列因此begin()可以放在红黑树中最小节点(即最左侧节点)的位置end()放在最大节点 (最右侧节点)的下一个位置关键是最大节点的下一个位置在哪块能否给成nullptr呢答案是行不通 的因为对end()位置的迭代器进行–操作必须要能找最后一个元素此处就不行因此最好的方式是 将end()放在头结点的位置
operator()与operator–()
/*
templateclass T, class Ref, class Ptr
typedef __RBTreeIteratorT, Ref, Ptr Self;
*/
Self operator(){if (_node-_right){// 1、右不为空下一个就是右子树的最左节点Node* subLeft _node-_right;while (subLeft-_left){subLeft subLeft-_left;}_node subLeft;}else{// 2、右为空沿着到根的路径找孩子是父亲左的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur parent;parent parent-_parent;}_node parent;}return *this;}Self operator--(){if (_node-_left){// 1、左不为空找左子树最右节点Node* subRight _node-_left;while (subRight-_right){subRight subRight-_right;}_node subRight;}else{// 2、左为空孩子是父亲的右的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_left){cur parent;parent parent-_parent;}_node parent;}return *this;}3 .map和set的模拟实现
首先map和set的底层结构就是红黑树因此在map和set中分别封装一棵红黑树然后将其接口包装下即可。为了减少代码的冗余我们通常会引入一个新的模版参数来区分是map还是set的调用。详情见下图
3.1 map的模拟实现
#pragma once#include RBTree.hnamespace bit
{templateclass K, class Vclass map{struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};public:typedef typename RBTreeK, pairconst K, V, MapKeyOfT::Iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}V operator[](const K key){pairiterator, bool ret _t.Insert(make_pair(key, V()));return ret.first-second;}pairiterator, bool insert(const pairconst K, V kv){return _t.Insert(kv);}private:RBTreeK, pairconst K, V, MapKeyOfT _t;};void test_map1(){mapstring, string dict;dict.insert(make_pair(sort, 排序));dict.insert(make_pair(string, ַ字符串));dict.insert(make_pair(count, 计数));dict.insert(make_pair(string, (字符串))); //插不进去mapstring, string::iterator it dict.begin();while (it ! dict.end()){cout it-first : it-second endl;/*it-first 1111;it-second 111;*/it;}cout endl;for (auto kv : dict){cout kv.first : kv.second endl;}cout endl;}void test_map2(){string arr[] { 你, 今, 天, 真, 好, 看, };mapstring, int countMap;for (auto e : arr){countMap[e];}for (auto kv : countMap){cout kv.first : kv.second endl;}}
}
3.2 set的模拟实现
#pragma once
#includeRBTree.h
namespace Maria
{template class Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename RBTreeK, K, SetKeyOfT::Iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pairiterator,bool Insert(const K key){return _t.Insert(key);}private:RBTree K,K,SetKeyOfT _t;};void test_set(){setint s;s.Insert(3);s.Insert(1);s.Insert(2);setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;}
}3.3 改造红黑树
#pragma once
#includeiostream
using namespace std;enum Colour
{RED,BLACK,
};templateclass T
struct RBTreeNode
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Colour _col;RBTreeNode(const T data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};templateclass T, class Ref, class Ptr
struct __RBTreeIterator
{typedef RBTreeNodeT Node;typedef __RBTreeIteratorT, Ref, Ptr Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}__RBTreeIterator(const __RBTreeIteratorT, T, T* it):_node(it._node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}Self operator--(){if (_node-_left){// 1、左不为空找左子树最右节点Node* subRight _node-_left;while (subRight-_right){subRight subRight-_right;}_node subRight;}else{// 2、左为空孩子是父亲的右的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_left){cur parent;parent parent-_parent;}_node parent;}return *this;}Self operator(){if (_node-_right){// 1、右不为空下一个就是右子树的最左节点Node* subLeft _node-_right;while (subLeft-_left){subLeft subLeft-_left;}_node subLeft;}else{//2、右为空、沿着到根的路径找孩子是父亲左的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur parent;parent parent-_parent;}_node parent;}return *this;}
};// 仿函数
templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:~RBTree(){_Destroy(_root);_root nullptr;}
public:typedef __RBTreeIteratorT, T, T* Iterator;typedef __RBTreeIteratorT, const T, const T* const_Iterator;Iterator begin(){Node* cur _root;while (cur cur-_left){cur cur-_left;}return Iterator(cur);}Iterator end(){return Iterator(nullptr);}Node* Find(const K key){Node* cur _root;KeyOfT kot;while (cur){if (kot(cur-_data) key){cur cur-_right;}else if (kot(cur-_data) key){cur cur-_left;}else{return cur;}}return nullptr;}pairIterator,bool Insert(const T data){if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(Iterator(_root),true);}KeyOfT kot;Node* parent nullptr;Node* cur _root;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(Iterator(cur),false );}}cur new Node(data);Node* newnode cur;if (kot(parent-_data) kot(data)){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;if (grandfather-_left parent){Node* uncle grandfather-_right;// 情况1u存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续往上调整cur grandfather;parent cur-_parent;}else // 情况23u不存在/u存在且为黑旋转变色{// g// p u// c if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;//parent-_col RED;grandfather-_col RED;}break;}}else // (grandfather-_right parent){// g// u p// cNode* uncle grandfather-_left;// 情况1u存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续往上调整cur grandfather;parent cur-_parent;}else // 情况23u不存在/u存在且为黑旋转变色{// g// u p// cif (cur parent-_right){RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return make_pair(Iterator(newnode), true);}bool IsBalance(){if (_root _root-_col RED){cout 根节点颜色是红色 endl;return false;}int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}// 连续红色节点return _Check(_root, 0, benchmark);}int Height(){return _Height(_root);}private:void _Destroy(Node* root){if (root nullptr){return;}_Destroy(root-_left);_Destroy(root-_right);delete root;}int _Height(Node* root){if (root NULL)return 0;int leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;}bool _Check(Node* root, int blackNum, int benchmark){if (root nullptr){if (benchmark ! blackNum){cout 某条路径黑色节点的数量不相等 endl;return false;}return true;}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return _Check(root-_left, blackNum, benchmark) _Check(root-_right, blackNum, benchmark);}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppnode parent-_parent;subR-_left parent;parent-_parent subR;if (ppnode nullptr){_root subR;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* ppnode parent-_parent;subL-_right parent;parent-_parent subL;if (parent _root){_root subL;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}}private:Node* _root nullptr;
};
