C++ STL-- 关联式容器之一 -- set
AVL树是一个平衡二叉搜索树，当向二叉搜索树中插入新节点后，如果能保证每个节点的左右子树高度之差的绝对值不超过1（需要对树中的节点进行调整），即可降低树的高度，从而减少平均搜索的长度；②为什么要用AVL树：因为二叉搜索树虽然可以降低查找效率，但如果数据有序或接近有序的时候将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下：例如：当数据是 1 2 3 4 5 6 ....13 14 时：二叉
·
Hello！！大家早上中午晚上好！！今天我们来复习一下STL的关联式容器！！！
一、什么是set?
1.1 set 就是一个key模型的二叉搜索树，严格来说是红黑树；
1.2 什么是红黑树？
红黑树其实是AVL树的基础上做了一点改动，了解红黑树之前我们先来了解AVL树：
1.3 什么是AVL树?
①AVL树的概念：
AVL树是一个平衡二叉搜索树，当向二叉搜索树中插入新节点后，如果能保证每个节点的左右子树高度之差的绝对值不超过1（需要对树中的节点进行调整），即可降低树的高度，从而减少平均搜索的长度；
②为什么要用AVL树：
因为二叉搜索树虽然可以降低查找效率，但如果数据有序或接近有序的时候将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下：
例如：
当数据是 1 2 3 4 5 6 ....13 14 时：
二叉搜索树是这个样子：
这样的搜索树高度很高，搜索次数会增加，效率大大下降！
③怎么使用？怎么实现AVL树？
二、AVL树的平衡方法
2.1 AVL树必须满足以下条件：
①每一棵左右子树必须是AVL树；
②左右子树的高度差（平衡因子）的绝对值不超过1，即平衡因子只能是1、0、-1；
左右子树高度差=右子树的高度-左子树的高度：
画个图：
例如：节点3的左子树高度为2,节点3的右子树的高度为1,节点3的平衡因子为1-2=-1；
节点5的左子树的高度为3，右子树高度为3，节点5的平衡因子为3-3=0；
节点7的左子树的高度为1，右子树的高度为2，节点7的平衡因子为2-1=1；
2.2 AVL树实现的核心步骤
①当新增节点在parent的左边，parent的平衡因子--；
②当新增节点咋parent的右边，parent的平衡因子++；
③更新后parent的平衡因子==0，说明parent所在的子树的高度不变，不会影响祖先，不用再沿着到root的路径往上更新，结束插入；
④更新后parent的平衡因子==1或==-1，说明parent所在的子树的高度发生变化，会影响祖先，要沿着到root的路径往上更新；
⑤更新后parent的平衡因子==2或-2，说明parent所在的子树高度发生变化且已经不平衡！需要对parent所在的子树进行旋转，让他平衡；
⑥如果更新到根结点，结束插入；
（简而言之：当插入节点后还是平衡二叉树不需要改动，当插入节点后不平衡了就旋转让他平衡！）
2.3 AVL树实现的核心步骤如何旋转？
当parent的平衡因子为2并且cur的平衡因子为1时左单旋：
当parent的平衡因子为-2并且cur的平衡因子为-1时右单旋：
当parent的平衡因子为2且cur的平衡因子为-1时右左双旋：
当parent的平衡因子为-2且cur的平衡因子为1时左右双旋：
三、AVL树模拟实现
3.1 明白了平衡方法那我们来实现一下吧
首先明确每个节点必须包含的成员：
①左右子树的指针；
②指向父节点的指针；（因为旋转的过程必须要知道父节点是谁，如果没有父亲节点的指针cur遍历下去会很麻烦）
③平衡因子；（用来记录左右子树高度差，判断是否需要旋转）
④节点存放的数据；（这里我直接用std::pair类型当数据，即Key，Val结构的数据）
代码：
#pragma once
template<class K,class V>
struct AVLtreeNode
{
pair<K, V> _data;//节点存放的数据
AVLtreeNode* _left;//左孩
AVLtreeNode* _right;//右孩
AVLtreeNode* _parent;//节点的父亲
int _bf;//平衡因子
//节点的构造函数
AVLtreeNode(const pair<K,V>& data )
:_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0)
{
}
};测试：
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
#include "AVLTREE.h"
int main()
{
AVLtreeNode<int, string> s1(make_pair(5, "hello"));
cout << s1._data.first <<" "<<s1._data.second << endl;
return 0;
}
接着下一步，AVL树的插入；
3.2 AVL树的方法实现
首先明确AVL树的的成员：
①只需要一个成员变量指向root节点的指针，通过这个指针可以访问到整棵树，并对这棵树进行增删查改！
②insert插入成员函数不可或缺；
③左旋右旋左右旋右左旋的方法实现可以单独写，需要的时候调用即可；
代码：
template<class K,class V>
class AVLTree
{
public:
typedef AVLtreeNode<K, V> Node;
bool insert(const pair<K,V>& kv)//用bool返回值判断是否成功插入（当key值相等时插入失败）
{
//如果是一棵空树，插入的节点就是根节点
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
//寻找插入位置，首先要保证它是一棵二叉搜索树
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_data.first > kv.first)
{
parent = cur;//往下走之前记录一下parent
cur = cur->_left;
}
else if (cur->_data.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
return false;
}
//走到这一步说明找到插入位置
cur = new Node(kv);//创建新节点
if (parent->_data.first > cur->_data.first)//判断新节点在父节点的左边还是右边并连接
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//链接后向上更新平衡因子
while (parent)
{
//判断插入节点位置，在左parent平衡因子--，在右平衡因子++
if (parent->_left == cur)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
//检查parent的平衡因子是否需要旋转或向上更新
if (parent->_bf == 0)
{
break;//不需要更新
}
else if (parent->_bf == 1 || parent->_bf == -1)//需要向上更新
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)//需要旋转
{
if (parent->_bf == 2 && cur->_bf == 1)//右单旋
{
RotateR(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)//左单旋
{
RotateL(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)//右左双旋
{
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)//左右双旋
{
RotateLR(parent);
}
}
}
return true;
}
void inOrder()
{
inOrder(_root);
}
void preOrder(Node* root)
{
if (root == nullptr)
return;
inOrder(root->_left);
cout << root->_data.first << " :" << root->_data.second << endl;
inOrder(root->_right);
}
private:
void RotateL(Node* parent) // 1
{ // 1
Node* cur = parent->_right; // 1
Node* curleft = cur->_left;
parent->_right = curleft;
if (curleft)
{
curleft->_parent = parent;
}
Node* ppnode = parent->_parent;
cur->_left = parent;
if (parent==_root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
ppnode->_right = cur;
cur->_parent = ppnode;//记得要链上
}
parent->_bf = cur->_bf = 0;
}
void RotateR(Node*parent)
{
Node* cur = parent->_left; // 1
Node* curright = cur->_right; // 1
parent->_left = curright; // 1
if (curright)
{
curright->_parent = parent;
}
Node* ppnode = parent->_parent;
cur->_right = parent;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
ppnode->_right = cur;
cur->_parent = ppnode;//记得要链上
}
parent->_bf = cur->_bf = 0;
}
void RotateLR(Node* parent)//左右旋 // 1
{ // 1
Node* cur = parent->_left; // 1
Node* curright = cur->_right;
int bf = curright->_bf;//记录旋转前的bf，待会需要更改
RotateL(parent->_left);
RotateR(parent);//复用
//更新bf
if (bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curright->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
cur->_bf = -1;
curright->_bf = 0;
}
else if(bf==-1)
{
parent->_bf = 1;
cur->_bf = 0;
curright->_bf = 0;
}
}
void RotateRL(Node* parent)//右左旋 // 1
{ // 1
Node* cur = parent->_right; // 1
Node* curleft = cur->_left;
int bf = curleft->_bf;//记录旋转前的bf，待会需要更改
RotateR(parent->_right);//复用
RotateL(parent);
//更新bf
if (bf == 0)//这里画图理解就行
{
parent->_bf = 0;
cur->_bf = 0;
curleft->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
cur->_bf = 0;
curleft->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
cur->_bf = 1;
curleft->_bf = 0;
}
}
Node* _root=nullptr;
};顺便实现一下求树的高度：
int treeHight()
{
return treeHight(_root);
}
int treeHight(Node* root)
{
if (root == nullptr)
{
return 0;
}
int treeLeft = treeHight(root->_left);
int treeRight = treeHight(root->_right);
return treeLeft > treeRight ? treeLeft + 1 : treeRight + 1;
}测试：
void test1()
{
AVLTree<int, string> s1;
s1.insert(make_pair<int,string>(3, "hello"));
s1.insert(make_pair<int, string>(6, "hi"));
s1.insert(make_pair<int, string>(2, "thank"));
s1.insert(make_pair<int, string>(8, "nice"));
s1.insert(make_pair<int, string>(5, "well"));
s1.inOrder();//注： preOrder是自己实现的前序遍历打印
cout <<"treeHight = "<< s1.treeHight() << endl;
}
四、红黑树
既然AVL树已经实现了，我们回到标题1.2的问题：什么是红黑树？
下面我们来看一看什么是红黑树吧！
4.1红黑树的概念
红黑树是一种二叉搜索树，但在每一个节点上增加一个存储位表示该节点的颜色，可以是Red或Black。通过任何一条根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的！（最长路径不超过最短路径的2倍）
4.2 红黑树的规则
①每个节点是不是黑色就是红色；
②根节点是黑色；
③如果一个节点是红色，它的两个孩子节点必须是黑色（任何一个路径没有连续的红色节点，可以是连续的黑色节点）；
④ 每条路径上黑色节点的数量相等；
⑤每个叶子结点都是黑色的（此叶子结点指的是NULL空节点，红黑树中只有NULL节点被看做是叶子节点！！）
画图理解：
4.3 红黑色的旋转和变色方法
当我们插入一个节点后，存在连续的两个红色节点，就要对红黑树进行调整：
场景一：当parent为红且uncle为红
场景二：当parent为红且uncle不存在或为黑
当parent为红且uncle不存在：
当parent在granfarther右边且cur在parent右边时进行右单旋（前提条件一样）；
场景三：左右双旋
右左双旋同理！
场景四：当parent为黑色的时候，什么事也不用做
以上是大概的变色与旋转方案，那么接下来模拟实现以下吧！
五、红黑树的实现
5.1 明确实现红黑树所需要定义的类或结构体
①首先描述一个节点，用struct结构体，里面的成员必须包含：
1、能表示节点颜色的color（最好用枚举）；
2、节点里必须要有指向左右子树的节点指针；
3、节点里必须要有一个指向父节点的指针；
4、节点必须要有一个可以存放数据的的变量（至于什么可自定义，这里我直接用pair<>方便后续set的包装）
②其次描述红黑树，可以定义一个类，成员变量只需要一个指向根节点的指针；
其余便是类方法的实现，可以实现对这棵树进行增删查改、判断是否是红黑树、是否平衡、跟获取树的高度；
5.2 开始实现
枚举类型color标记节点的颜色：
//定义一个表示颜色的枚举
enum color
{
RED,
BLACK
};节点的定义：
//定义节点
template<class K,class V>
struct RBTreeNode
{
pair<K, V> _kv;//数据
color _col;//标记颜色
RBTreeNode<K, V>* _left;//指向左子树
RBTreeNode<K, V>* _right;//指向右子树
RBTreeNode<K, V>* _parent;//指向父节点
RBTreeNode(const pair<K,V>& kv)//节点的构造函数
:_kv(kv),_col(RED),_left(nullptr),_right(nullptr),_parent(nullptr)//节点默认设置为红色
{
}
};RBTree的定义：
//定义红黑树
template<class K,class V>
class RBTree
{
public:
typedef RBTreeNode<K, V> Node;
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
//如果为空树，插入的结点成为根节点
_root = new Node(kv);
_root->_col = BLACK;//根节点必须黑色
return true;//插入成功
}
//走到这里说明不为空树，开始找插入位置（保证它是一棵二叉搜索树）
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;//cur往下走之前记录一下
cur = cur->_left;
}
else if(cur->_kv.first<kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
//走到这里说明相等，插入失败
return false;
}
}
//走到这里说明找到插入位置，创建新节点并链接
cur = new Node(kv);
cur->_parent = parent;
//需要判断一下在parent的左还是右
if (parent->_kv.first > cur->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
//开始判断parent跟uncle的颜色来决定需不需要调整
while (parent && parent->_col == RED)//parent 不为空且parent的颜色为红说明一定存在两个连着的红色节点
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left)
{
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED)//如果uncle存在且颜色为红
{
parent->_col = BLACK; //父跟uncle变黑,grandparentB变红并继续往上调整
uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else//父为空或者黑，需要旋转+变色
{
if (cur == parent->_left)
{
RotateR(grandparent); // 1
grandparent->_col = RED; // 1
parent->_col = BLACK; // 1
}
else
{
RotateL(parent); // 1
RotateR(grandparent); // 1
grandparent->_col = RED; // 1
cur->_col = BLACK;
}
break;//旋转后就平衡了不需要继续往上走
}
}
else //parent==grandparent->right
{
Node* uncle = parent->_left;
if (uncle && uncle->_col == RED)
{
//变色向上调整
parent->_col = BLACK;
uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else//uncle为黑或不存在，需要旋转
{
if (cur == parent->_right) // 1
{ // 1
RotateL(grandparent); // 1
grandparent->_col = RED;
parent->_col = BLACK;
}
else
{
RotateR(parent);
RotateL(grandparent);
grandparent->_col = RED; // 1
cur->_col = BLACK; // 1
} // 1
break;
}
}
}
_root->_col = BLACK;
return true;
}
//这里旋转方法直接ctrl c v前面AVL树实现的就行
void RotateL(Node* parent) // 1
{ // 1
Node* cur = parent->_right; // 1
Node* curleft = cur->_left;
parent->_right = curleft;
if (curleft)
{
curleft->_parent = parent;
}
Node* ppnode = parent->_parent;
cur->_left = parent;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
ppnode->_right = cur;
cur->_parent = ppnode;//记得要链上
}
}
void RotateR(Node* parent)
{
Node* cur = parent->_left; // 1
Node* curright = cur->_right; // 1
parent->_left = curright; // 1
if (curright)
{
curright->_parent = parent;
}
Node* ppnode = parent->_parent;
cur->_right = parent;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
ppnode->_right = cur;
cur->_parent = ppnode;//记得要链上
}
}
//中序遍历，用来打印树的节点信息
void inOrder()
{
inOrder(_root);
}
void inOrder(Node* root)
{
if (root == nullptr)
return;
inOrder(root->_left);
cout << root->_kv.first << " : " << root->_kv.second << endl;
inOrder(root->_right);
}
private:
Node* _root=nullptr;
};5.3 测试：
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include "RBTree4_10.h"
int main()
{
RBTree<int, string> rbt1;
rbt1.insert(make_pair(4, "hello"));
rbt1.insert(make_pair(2, "hi"));
rbt1.insert(make_pair(7, "well"));
rbt1.insert(make_pair(1, "welcome"));
rbt1.inOrder();
return 0;
}
ok再实现一下下求树的高度和判断是否平衡、是否红黑树的接口：
int Hight()//求树高度
{
Hight(_root);
}
int Hight(Node* root)
{
if (root == nullptr)
return 0;
int lefthight = Hight(root->_left);
int righthight = Hight(root->_right);
return lefthight > righthight ? lefthight + 1 : righthight + 1;
}实现判断是否红黑树的思路：
①递归红黑树如果出现两个连续的红节点return false；
②先算出红黑树的黑节点的基准值，再边递归红黑树，如果是黑节点++，最后遇到null跟基准值比较，只要有一个路径的黑色节点个数不相等返回false；
代码：
bool isBalance()
{
return isBalance(_root);
}
bool isBalance(Node* root)
{
if (root == nullptr)
return true;
if (root->_col != BLACK)
return false;//如果根节点不为黑
//走到这里说明不是空且根节点为黑色
int fiducial = 0;//求出某一条路径的黑色节点数作为基准值
Node* cur = root;
while (cur)
{
if (cur->_col == BLACK)
++fiducial;
cur = cur->_left;
}
return checkColour(root, 0, fiducial);
}
bool checkColour(Node* root, int blacknum, int _fiducial)
{
if (root == nullptr)//当root==nullptr说明递归走到NULL节点，这时可以用blacknum跟基准值比较
{
if (blacknum != _fiducial)
{
return false;
}
else
return true;
}
if (root->_col == BLACK)//如果遇到黑色节点++blacknum
++blacknum;
if (root->_col == RED && root->_parent && root->_parent->_col == RED)
return false;
return checkColour(root->_left, blacknum, _fiducial) && checkColour(root->_right, blacknum, _fiducial);//递归左子树、右子树
}测试：
int main()
{
RBTree<int, string> rbt1;
rbt1.insert(make_pair(4, "hello"));
rbt1.insert(make_pair(2, "hi"));
rbt1.insert(make_pair(7, "well"));
rbt1.insert(make_pair(1, "welcome"));
rbt1.inOrder();
cout <<"当前是否红黑树：" << rbt1.isBalance() << endl;
cout <<"当前树的高度： " << rbt1.Hight() << endl;
return 0;
}
ok！！到这里红黑树的实现基本完成，那么我们来用红黑树封装一下set吧！！！
六、set的封装
6.1 首先set 要实现以下功能
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
#include <set>
int main()
{
set<int> s1;
s1.insert(1);
s1.insert(23);
s1.insert(4);
s1.insert(6);
s1.insert(77);
s1.insert(2);
set<int>::iterator it1 = s1.begin();
while (it1 != s1.end())
{
cout << *it1 << " ";
//*it1 += 1;报错
++it1;
}
cout << endl;
for (auto e : s1)
{
cout << e << " ";
}
cout << endl;
return 0;
}
1、插入的过程就是对一棵红黑树进行插入；
2、支持for语法糖说明包装有迭代器，且迭代器++是从小到大依次遍历；
3、*it1报错说明这是一个const的迭代器只能读不能写！
6.2、实现
把RBTree迭代器完善、类型完善，然后再在RBTree外面套一层壳，这层壳就是set，set类方法的调用，实际上是RBTree类方法的调用：
Set：
#pragma once
#include "RBTree4_13.h"
namespace ldc
{
template<class K>
class Set
{
struct setKeyofT //为什么要写keyofT 因为map （map的数据是pair<int,string>时要用keyofT获取第一个参数即key值的类型来做比较）
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, setKeyofT>::const_iterator iterator;
typedef typename RBTree<K, K, setKeyofT>::const_iterator const_iterator;
const_iterator begin()const
{
return _tree.begin();
}
const_iterator end()const
{
return _tree.end();
}
pair<iterator,bool> insert(const K&key)
{
pair<typename RBTree<K,K,setKeyofT>::iterator, bool> ret = _tree.insert(key);
return pair<iterator,bool>(ret.first,ret.second);
}
private:
RBTree<K, K, setKeyofT> _tree;//为什么多传一个K模版参数？ 因为map （当map的插入数据类型是pair<int,string>时第二个参数就可以直接获取类型，用第一个参数做键值key的类型）
};
}完善后的RBTree：
#pragma once
#include <assert.h>
//定义一个表示颜色的枚举
enum color
{
RED,
BLACK
};
//定义节点
template<class T> //这里改成T，T可以是int string 、 pair<int,string>...只要传什么就给它实例化出什么类型来
struct RBTreeNode
{
T _data;//数据
color _col;//标记颜色
RBTreeNode<T>* _left;//指向左子树
RBTreeNode<T>* _right;//指向右子树
RBTreeNode<T>* _parent;//指向父节点
RBTreeNode(const T& data)//节点的构造函数
:_data(data),_col(RED),_left(nullptr),_right(nullptr),_parent(nullptr)//节点默认设置为红色
{
}
};
//包装迭代器
template <class T,class Ptr,class Ref>
class RBTreeIterator
{
typedef RBTreeIterator<T, Ptr, Ref> Self;
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, T*, T&> iterator;
public:
RBTreeIterator( Node*node)
{
_node = node;
}
RBTreeIterator(const iterator& it)
{
_node = it._node;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self &operator--()
{
//红黑树迭代器--实现方法：1、当左子树不为空时，找左子树最右节点 2、当左子树为空时，找cur是parent右边的parent就是下一个访问的节点
Node* cur = _node;
if (cur->_left)
{
Node* rightmost = cur->_left;
while (rightmost->_right)
{
rightmost = rightmost->_right;
}
_node = rightmost;
}
else
{
//左为空
Node* parent = cur->_parent;
while (parent)
{
if (parent->_right == cur)
{
break;
}
else
{
cur = cur->_parent;
parent = parent->_parent;
}
}
_node = parent;
}
return *this;
}
Self &operator++()
{
//红黑树迭代器++实现方法：1、当右子树不为空时，找右子树最左节点 2、当右子树为空时，找cur是parent左边的parent就是下一个访问的节点
Node* cur = _node;
if (cur->_right)
{//右不为空
Node* leftmost = cur->_right;
while (leftmost->_left)
{
leftmost = leftmost->_left;
}
_node = leftmost;
}
else
{//右为空
Node* parent = cur->_parent;
while (parent)
{
if (parent->_left == cur)
{
break;
}
else//parent->right==cur
{
cur = cur->_parent;
parent = parent->_parent;
}
}
_node = parent;
}
return *this;
}
bool operator==(const Self&it)
{
return _node == it._node;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
Node* _node;
};
//定义红黑树
//set -> RBTree<K,K,setKeyofT> _t;
// map -> RBTree<K,pair<K,V>,mapKeyofT> _t;
template<class K,class T,class KeyofT>
class RBTree
{
public:
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, T*, T&> iterator;
typedef RBTreeIterator<T, const T*, const T&> const_iterator;
iterator begin()
{
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin()const
{
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
const_iterator end()const
{
return const_iterator(nullptr);
}
Node* Find(const K& key)
{
KeyofT kot;
Node* cur = _root;
while (cur)
{
if (kot(cur->_data) > kot(key))
{
cur = cur->_left;
}
else if (kot(cur->_data) < kot(key))
{
cur = cur->_right;
}
else
return cur;
}
return nullptr;
}
pair<iterator,bool> insert(const T& data)//这里为什么要用pair<iterator,bool>作返回值？ 因为map
{
if (_root == nullptr)
{
//如果为空树，插入的结点成为根节点
_root = new Node(data);
_root->_col = BLACK;//根节点必须黑色
return pair<iterator,bool>(_root,true);//插入成功
}
//走到这里说明不为空树，开始找插入位置（保证它是一棵二叉搜索树）
Node* cur = _root;
Node* parent = nullptr;
KeyofT KOT;// 这里为什么要用KOT ? 因为map
while (cur)
{
if (KOT(cur->_data) > KOT(data))
{
parent = cur;//cur往下走之前记录一下
cur = cur->_left;
}
else if(KOT(cur->_data)<KOT(data))
{
parent = cur;
cur = cur->_right;
}
else
{
//走到这里说明相等，插入失败
return pair<iterator,bool>(cur,false);
}
}
//走到这里说明找到插入位置，创建新节点并链接
cur = new Node(data);
cur->_parent = parent;
Node* newnode = cur;//保存一下新节点位置
//需要判断一下在parent的左还是右
if (KOT(parent->_data) > KOT(cur->_data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
//开始判断parent跟uncle的颜色来决定需不需要调整
while (parent && parent->_col == RED)//parent 不为空且parent的颜色为红说明一定存在两个连着的红色节点
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left)
{
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED)//如果uncle存在且颜色为红
{
parent->_col = BLACK; //父跟uncle变黑,grandparentB变红并继续往上调整
uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else//父为空或者黑，需要旋转+变色
{
if (cur == parent->_left)
{
RotateR(grandparent); // 1
grandparent->_col = RED; // 1
parent->_col = BLACK; // 1
}
else
{
RotateL(parent); // 1
RotateR(grandparent); // 1
grandparent->_col = RED; // 1
cur->_col = BLACK;
}
break;//旋转后就平衡了不需要继续往上走
}
}
else //parent==grandparent->right
{
Node* uncle = parent->_left;
if (uncle && uncle->_col == RED)
{
//变色向上调整
parent->_col = BLACK;
uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else//uncle为黑或不存在，需要旋转
{
if (cur == parent->_right) // 1
{ // 1
RotateL(grandparent); // 1
grandparent->_col = RED;
parent->_col = BLACK;
}
else
{
RotateR(parent);
RotateL(grandparent);
grandparent->_col = RED; // 1
cur->_col = BLACK; // 1
} // 1
break;
}
}
}
_root->_col = BLACK;
return pair<iterator,bool>(newnode,true);
}
void RotateL(Node* parent) // 1
{ // 1
Node* cur = parent->_right; // 1
Node* curleft = cur->_left;
parent->_right = curleft;
if (curleft)
{
curleft->_parent = parent;
}
Node* ppnode = parent->_parent;
cur->_left = parent;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
ppnode->_right = cur;
cur->_parent = ppnode;//记得要链上
}
}
void RotateR(Node* parent)
{
Node* cur = parent->_left; // 1
Node* curright = cur->_right; // 1
parent->_left = curright; // 1
if (curright)
{
curright->_parent = parent;
}
Node* ppnode = parent->_parent;
cur->_right = parent;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
ppnode->_right = cur;
cur->_parent = ppnode;//记得要链上
}
}
void inOrder()
{
inOrder(_root);
}
void inOrder(Node* root)
{
if (root == nullptr)
return;
inOrder(root->_left);
cout << root->_kv.first << " : " << root->_kv.second << endl;
inOrder(root->_right);
}
int Hight()//求树高度
{
return Hight(_root);
}
int Hight(Node* root)
{
if (root == nullptr)
return 0;
int lefthight = Hight(root->_left);
int righthight = Hight(root->_right);
return lefthight > righthight ? lefthight + 1 : righthight + 1;
}
bool isBalance()
{
return isBalance(_root);
}
bool isBalance(Node* root)
{
if (root == nullptr)
return true;
if (root->_col != BLACK)
return false;//如果根节点不为黑
//走到这里说明不是空且根节点为黑色
int fiducial = 0;//求出某一条路径的黑色节点数作为基准值
Node* cur = root;
while (cur)
{
if (cur->_col == BLACK)
++fiducial;
cur = cur->_left;
}
return checkColour(root, 0, fiducial);
}
bool checkColour(Node* root, int blacknum, int _fiducial)
{
if (root == nullptr)
{
if (blacknum != _fiducial)
{
return false;
}
else
return true;
}
if (root->_col == BLACK)
++blacknum;
if (root->_col == RED && root->_parent && root->_parent->_col == RED)
return false;
return checkColour(root->_left, blacknum, _fiducial) && checkColour(root->_right, blacknum, _fiducial);
}
private:
Node* _root=nullptr;
};测试：
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
#include <set>
#include "MYset04_12.h"
int main()
{
ldc:: Set<int> s1;
s1.insert(5);
s1.insert(3);
s1.insert(55);
s1.insert(22);
s1.insert(7);
s1.insert(1);
ldc::Set<int>::iterator it1 = s1.begin();
while (it1 != s1.end())
{
cout << *it1 << " ";
//*it1 += 1;报错
++it1;
}
cout << endl;
for (auto e : s1)
{
cout << e << " ";
}
cout << endl;
return 0;
}
成功！！
七、总结
7.1、这里的难点有：
①为什么要定义一个keyofT？因为后续map的实现通过keyofT来获取当map插入的数据类型pair的第一个参数；
②为什么insert的返回值类型要用pair<iterator,bool>? 因为后续map通过insert的返回值来实现operator[]运算符重载函数；
③为什么RBTree要定义三个模版参数？因为后续map类型的使用更清晰，可以做到第一个参数当key（键值）的类型，第二个参数当pair<K,V>的类型，第三个参数用来获取pair<K,V>中的K类型；
④可以理解为set所有的一切为什么都是因为map；
今天就分享到这里！！如果对你有帮助记得点赞收藏+关注哦！！！谢谢！！
咱下期见！！（map的实现）
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
29
0- 0
已为社区贡献1条内容
所有评论(0)