手撕AVL树、红黑树，红黑树封装map、set
原创
image-20230409165512114
AVL树
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，咱们中国的邻居俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
这样的树被称为AVL树。具有性质：
- 它的左右子树都是AVL树；左右子树高度差（平衡因子）的绝对值不超过1**（即三种可能：-1，0，1）；
- 如果一棵二叉搜索树的高度平衡的，它就是AVL树，若它有n个节点，其高度可保持在O(log_2 N)，搜索时间复杂度也是O(log_2 N);
AVL树的实现
AVL树的节点
template<class K, class V>
class AVLTreeNode
{
public:
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;//balance fator--平衡因子
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{}
};AVL树的平衡因子
平衡因子即左右子树的高度差，左子树高度加1，根的平衡因子减减，右子树高度加1，根的平衡因子加加。（左增--左减++，右增++，右减--）
是否继续往上更新平衡因子：
- parent-> _bf==0说明之前parent-> _bf==1或者-1，说明之前parent左右子树一边高一边低，现在低的那一边补齐了高度，不需要往上更新了。
- parent-> _bf==1或者parent-> _bf==-1时说明之前parent-> _bf==0。说明parent左右子树原来是平衡的，现在新增节点后一边高一边低了，需要往上更新平衡因子。
- <font size=4 color="red">parent-> _bf==2或者parent-> _bf==-2时，说明之前parent-> _bf==1或者-1。新增节点后违反了规则，需要旋转！
AVL树的插入
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)//如果根节点是空
{
_root = new node(kv);
return true;
}
node* cur = _root;
node* parent = nullptr;
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 (cur->_kv.first < parent->_kv.first)//cur在parent的左边
{
parent->_left = cur;
cur->_parent = parent;
}
else {
parent->_right = cur;
cur->_parent = parent;
}
//调整平衡因子
while (parent)//最坏情况调整到根
{
if (cur == parent->_left)
{
parent->_bf--;//cur在parent的左边，平衡因子--
}
else
{
parent->_bf++;//cur在parent的右边，平衡因子++
}
//调整
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)//往上更新平衡因子
{
cur = parent;
parent = cur->_parent;
}else if(parent->_bf==2||parent->_bf==-2)//这个情况都需要旋转，旋转完后不需要再往上更新后续直接break
{
if (parent->_bf == 2 && cur->_bf == 1)//此时cur为新插入节点的parent
{
//左正旋
RotateL(parent);//旋谁传谁
}
else if (parent->_bf == -2 && cur->_bf == -1)//此时cur为新插入节点的parent
{
//右正旋
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;
}AVL树的旋转
旋转的目标：
- 让这颗子树左右高度差不超过1
- 旋转过程中任然保持搜索树
- 更新平衡因子
- 让这颗树插入节点前和插入节点后高度保持一致
左单旋
抽象图
当parent的平衡因子（_bf=2)&&subR(parent->right)的平衡因子( _bf=1 )时，就需要以subR为轴点，左单旋parent；过程：先把subR的左子树subRL链接到parent的右孩子，然后把parent节点左单旋到subR的左孩子，不要忘了这里有可能整棵树也可能是一部分子树，所以parent-> _parent也需要考虑怎么链接到subR：
parent-> _parent为空时，此时subR就是根节点；当parent为parent-> _parent的左孩子时，subR就链接到parent-> _parent的左孩子，当parent为parent-> _parent的右孩子时，subR就链接到parent-> _parent的右孩子。
最后把subR的平衡因子和parent的平衡因子都改成0
image-20230402155352393
动图
左旋转
h=0的具像图
image-20230402160251384
动图
RotateL h=0
h=1的具象图
image-20230402164741843
RotateL h=1
h>=2的具象图
image-20230402164846701
动图就不画了，具体旋转步骤h>=1时都一样
话不多说上代码
void RotateL(node* parent)//左单旋
{
node* ppnode = parent->_parent;
node* subR = parent->_right;
node*subRL= subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subR;
if (ppnode == nullptr)//父父节点为空
{
_root = subR;
subR->_parent = nullptr;
}
else//父父节点不为空
{
if (parent == ppnode->_left)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
subR->_bf = parent->_bf = 0;
}右单旋
当parent->_bf=-2&&subL-> _bf=-1时，就需要以subL为轴点，右单旋parent；过程：先把subL的右子树subLR链接到parent的左孩子，然后把parent节点右单旋到subL的右孩子，不要忘了这里有可能整棵树也可能是一部分子树，所以parent-> _parent也需要考虑怎么链接到subL：
parent-> _parent为空时，此时subL就是根节点；当parent为parent-> _parent的左孩子时，subL就链接到parent-> _parent的左孩子，当parent为parent-> _parent的右孩子时，subL就链接到parent-> _parent的右孩子。
最后把subL的平衡因子和parent的平衡因子都改成0
抽象图
image-20230402170828809
右旋转
h=0的具像图
image-20230402171440302
动图
RotateR h=0
h=1的具象图
image-20230402172423498
h=2的具象图
image-20230403101128662
void RotateR(node*parent)//右单旋
{
node* ppnode = parent->_parent;
node* subL = parent->_left;
node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (ppnode == nullptr)//父节点的父节点为空
{
_root = subL;
subL->_parent = nullptr;
}
else//父节点的父节点不为空
{
if (parent == ppnode->_left)//parent为父父节点的左
{
ppnode->_left = subL;
}
else//parent为父父节点的右
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
subL->_bf = parent->_bf = 0;
}左右正旋
image-20230403145801525
抽象图（两种情况）
h>=1时，在subLR的右子树新增节点。先以subLR为轴点左旋subL，使得图形转化为右正旋模型，然后再以subLR为轴点右旋parent；
旋完后subLR-> _bf=parent-> _bf=0 ,subL-> _bf=-1
image-20230403111001659
h>=1时，在subLR的左子树新增节点。先以subLR为轴点左旋subL，再以subLR为轴点右旋parent；旋完后subLR-> _bf=subL-> _bf=0 ,parent-> _bf=1
image-20230403150508535
h=0的动图
RotateLR h=0
void RotateLR(node* parent)//左右正旋
{
node* subL = parent->_left;
node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (bf == -1)//新增节点在subLR的左边
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)//新增节点在subLR的右边
{
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == 0)//subLR自己新增
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}右左正旋
image-20230403150149815
抽像图（两种情况）
h>=1时，在subLR的右子树新增节点。先以subRL为轴点右旋subR，再以subRL为轴点左旋parent；旋完后subRL-> _bf=subR-> _bf=0 ,parent-> _bf=-1
image-20230403125731565
h>=1时，在subRL的左子树新增节点。先以subRL为轴点右旋subR，再以subRL为轴点左旋parent；旋完后subRL-> _bf=parent-> _bf=0 ,subR-> _bf=1
image-20230403113019710
h=0的动图
RotateRL h=0
void RotateRL(node* parent)//右左正旋
{
node* subR = parent->_right;
node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (bf == -1)//subRL的左边增加节点
{
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)//subRL的右边增加节点
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
}
else if (bf == 0)//subRL自增
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}中序遍历打印节点
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 Height(node* root)//返回子树最大高度
{
if (root == nullptr)
return 0;
int lh = Height(root->_left);
int rh = Height(root->_right);
return lh > rh ? lh + 1 : rh + 1;
}
bool IsBalance()
{
return _IsBalance(_root);
}
bool _IsBalance(node* root)
{
if (root == nullptr)
{
return true;
}
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
if (rightHeight - leftHeight != root->_bf)//左右子树高度查不符合此时根的平衡因子
{
cout << root->_kv.first <<":"<< "平衡因子异常" << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2//验证该子树是否是平衡树
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}整体代码
template<class K, class V>
class AVLTreeNode
{
public:
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{}
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> node;
public:
//bool Insert(const pair<K, V>& kv)
//{
//}
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)//如果根节点是空
{
_root = new node(kv);
return true;
}
node* cur = _root;
node* parent = nullptr;
while(cur)//没找到空不出去---这里找空节点不是一两次得用while
{
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 (cur->_kv.first < parent->_kv.first)//cur在parent的左边
{
parent->_left = cur;
cur->_parent = parent;
}
else {
parent->_right = cur;
cur->_parent = parent;
}
//调整平衡因子
while (parent)//最坏情况调整到根
{
if (cur == parent->_left)
{
parent->_bf--;//cur在parent的左边，平衡因子--
}
else
{
parent->_bf++;//cur在parent的右边，平衡因子++
}
//调整
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = cur->_parent;
}//当不是上面的情况也不是下面的parent==2/-2的情况时就是报错了
else if(parent->_bf==2||parent->_bf==-2)
{
if (parent->_bf == 2 && cur->_bf == 1)//此时cur为新插入节点的parent
{
//左正旋
RotateL(parent);//旋谁传谁
}
else if (parent->_bf == -2 && cur->_bf == -1)//此时cur为新插入节点的parent
{
//右正旋
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 RotateL(node* parent)
{
node* ppnode = parent->_parent;
node* subR = parent->_right;
node* subRL = subR->_left;
parent->_right = subRL;
if (subRL != nullptr)
{
subRL->_parent = parent;
}
parent->_parent = subR;
subR->_left = parent;
if (ppnode == nullptr)//父父节点为空
{
_root = subR;
subR->_parent = __nullptr;
}
else
{
if (parent == ppnode->_left)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
subR->_bf = parent->_bf = 0;
}
void RotateR(node* parent)
{
node* ppnode = parent->_parent;
node* subL = parent->_left;
node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
parent->_parent = subL;
subL->_right = parent;
if (ppnode == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == ppnode->_left)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
subL->_bf = parent->_bf = 0;
}
void RotateLR(node* parent)//左右正旋
{
node* subL = parent->_left;
node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);//左正旋
RotateR(parent);//右正旋
if (bf == 1)//新增节点在subLR的右边
{
subLR->_bf = parent->_bf = 0;
subL->_bf = -1;
}
else if (bf == -1)//新增节点在subLR的左边
{
subLR->_bf = subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 0)//subLR自己就是新增节点
{
subLR->_bf = subL->_bf = parent->_bf = 0;
}
else
{
assert(false);
}
}
void RotateRL(node* parent)//右左正旋
{
node* subR = parent->_right;
node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (bf == 1)//新增节点在subRL的右边
{
subRL->_bf = subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)//新增节点在subRL的左边
{
subRL->_bf = parent->_bf = 0;
subR->_bf = 1;
}
else if (bf == 0)//subRL自己就是新增节点
{
subRL->_bf = subR->_bf = parent->_bf = 0;
}
else
{
assert(false);
}
}
void Inorder()
{
_Inorder(_root);
}
void _Inorder(node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.second << ":" << root->_kv.second << endl;
_Inorder(root->_right);
}
int hight(node* root)
{
if (root == nullptr)
{
return 0;
}
int lh = hight(root->_left);
int rh = hight(root->_right);
return lh > rh ? lh + 1 : rh + 1;
}
bool Isbalance()
{
return _Isbalance(_root);
}
bool _Isbalance(node* root)
{
if (root == nullptr)
{
return true;
}
int lefth = hight(root->_left);
int righth = hight(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);
}
private:
node* _root = nullptr;
};验证代码
void TestAVLTree()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
AVLTree<int, int> at;
for (auto e : a)
{
at.Insert(make_pair(e, e));
at.Isbalance();
}
at.Inorder();
// srand(time(0));
// const size_t N = 10000;
// AVLTree<int, int> t;
// for (size_t i = 0; i < N; ++i)
// {
// size_t x = rand();
// t.Insert(make_pair(x, x));
// // t.Isbalance();
// }
//
// t.Inorder();
}红黑树
image-20230405163127543
概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
性质（规则）
- 每个结点不是红色就是黑色
- 根结点必须是黑色
- 如果一个结点是红色，则它的两个孩子结点是黑色
- 对于每个结点，从该结点到其后代的叶子结点，均有相同数量的黑色结点
- 每个叶子结点（这里指空节点）都是黑色
以升序插入构建红黑树
以升序插入构建红黑树
以降序插入构建红黑树
以降序插入构建红黑树
红黑树的实现
结点定义
enum Colour//枚举常量颜色
{
RED,
Black,
};
template<class K,class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _parent;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
Colour _col;
RBTreeNode(const pair<K, V>& kv)
:_kv(kv)
,_parent(nullptr)
,_left(nullptr)
,_right(nullptr)
,_col(RED)
{}
};插入
image-20230405164105456
插入时，默认新增结点是红色，那么当新增结点的parent也是红色时，就会违反规则3，这时候就需要处理结点的颜色。
parent在grandparent的左
情况一：uncle结点存在且uncle结点也是红色
<font size=5 color="red">parent结点和uncle结点都是红色:此时把parent结点和uncle结点都变</font>黑，<font size=5 color="red">grandparent结点变红，再依次往上更新。</font>
image-20230405164553566
情况二：grandparent,parent,cur呈现直线状态
当uncle结点不存在
以parent为轴点，右正旋grandparent，然后把parent结点变为黑，grandparent结点变为红，然后结束，不需要往上调整。
image-20230405190113694
当uncle存在且为黑时
往往这种情况是由情况一变化来的，先把parent的右子树给grandparent的左孩子，然后以parent为轴点，右正旋grandparent即把grandparent链接到parent的右孩子上，然后把parent结点变为黑，grandparent结点变为红，然后结束。
image-20230405190403748
动图展示
红黑树情况二
情况三：grandparent,parent,cur呈现折线状态
uncle不存在
先以cur为轴点左正旋parent，转化成情况二，再以cur为轴点右正旋grandparent，最后把cur结点变为黑，grandparent结点变为红，然后结束。
image-20230405195118066
uncle存在且为黑
先把cur的左孩子给parent的右孩子，然后以cur为轴点左正旋parent。转化成情况二，再把cur的右孩子给grandparent的左孩子，再以cur为轴点右正旋grandparent，最后把cur结点变为黑，grandparent结点变为红，然后结束。
image-20230405194643068
动图展示
红黑树情况三
上代码
//做调整
while (parent && parent->_col == RED)//红色
{
node* grandparent = parent->_parent;
if (grandparent)//g不为空
{
if (parent == grandparent->_left)//parent在左，uncle在右？
{
node* uncle = grandparent->_right;
//情况一:uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = Black;//p和u变黑
grandparent->_col = RED;//g变红
cur = grandparent;
parent = cur->_parent;//往上调整
}
else
{
if (cur == parent->_left)//情况二,此时不需要考虑uncle结点了
{
RotateR(grandparent);
parent->_col = Black;
grandparent->_col = RED;
}
else//cur在parent的右孩子，呈现折现形式，情况三
{
RotateL(parent);
RotateR(grandparent);
cur->_col = Black;
grandparent->_col = RED;
}
break;
}
}
}parent在grandparent的右
else//parent在右，uncle在左？
{
node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)//情况一
{
parent->_col = uncle->_col = Black;
grandparent->_col = RED;
cur = grandparent;
parent=cur->_parent;
}
else
{
if (cur == parent->_right)//情况二
{
RotateL(grandparent);
parent->_col = Black;
grandparent->_col = RED;
}
else//情况三
{
RotateR(parent);
RotateL(grandparent);
cur->_col = Black;
grandparent->_col = RED;
}
break;
}
}
}整体插入函数
bool Insert(const pair<K, 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
return false;
}
}
//链接--cur找到空的位置
cur = new node(kv);
cur->_col = RED;
if (parent->_kv.first < cur->_kv.first)//比它大，链接右边
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//做调整
while (parent && parent->_col == RED)//红色
{
node* grandparent = parent->_parent;
if (grandparent)//g不为空
{
if (parent == grandparent->_left)//parent在左，uncle在右？
{
node* uncle = grandparent->_right;
//情况一:uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = Black;//p和u变黑
grandparent->_col = RED;//g变红
cur = grandparent;
parent = cur->_parent;//往上调整
}
else
{
if (cur == parent->_left)//情况二,此时不需要考虑uncle结点了
{
RotateR(grandparent);
parent->_col = Black;
grandparent->_col = RED;
}
else//cur在parent的右孩子，呈现折现形式，情况三
{
RotateL(parent);
RotateR(grandparent);
cur->_col = Black;
grandparent->_col = RED;
}
break;
}
}
else//parent在右，uncle在左？
{
node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)//情况一
{
parent->_col = uncle->_col = Black;
grandparent->_col = RED;
cur = grandparent;
parent=cur->_parent;
}
else
{
if (cur == parent->_right)//情况二
{
RotateL(grandparent);
parent->_col = Black;
grandparent->_col = RED;
}
else//情况三
{
RotateR(parent);
RotateL(grandparent);
cur->_col = Black;
grandparent->_col = RED;
}
break;
}
}
}
}
_root->_col = Black;
return true;
}左旋右旋（和AVL树的一致）
void RotateR(node* parent)//右旋
{
node* ppnode = parent->_parent;
node* subL = parent->_left;
node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (ppnode == nullptr)//父节点的父节点为空
{
_root = subL;
subL->_parent = nullptr;
}
else//父节点的父节点不为空
{
if (parent == ppnode->_left)//parent为父父节点的左
{
ppnode->_left = subL;
}
else//parent为父父节点的右
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
}
void RotateL(node* parent)//左旋
{
node* ppnode = parent->_parent;
node* subR = parent->_right;
node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subR;
if (ppnode == nullptr)//父父节点为空
{
_root = subR;
subR->_parent = nullptr;
}
else//父父节点不为空
{
if (parent == ppnode->_left)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
}打印，验证是否符合红黑树的性质
Isbalance函数和check函数验证了红黑树的性质2，3，4
bool check(node* root, int blacknum, int _ref)
{
if (root == nullptr)
{
if (blacknum != _ref)
{
cout << "每条路径上的黑色结点数量不相同，违反了规则4" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "红色结点连续出现，违背了规则3" << endl;
return false;
}
if (root->_col == Black)
blacknum++;
return check(root->_left, blacknum, _ref)
&& check(root->_right, blacknum, _ref);
}
bool Isbalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col == RED)
{
return false;
}
int ref = 0;
node* Left = _root;
while (Left)
{
if (Left->_col == Black)
ref++;//记录最左边路径上黑色结点的数量
Left = Left->_left;
}
return check(_root, 0, ref);
}验证案例
void TestRBTreee()
{
//特例验证--验证了情况一二三
// int a[]={4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
// int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// RBTree<int, int> rb;
// for (auto e : a)
// {
// rb.Insert(make_pair(e,e));
// rb.Isbalance();
// }
// rb.Inorder();
//随机数验证
srand(time(0));
const size_t N = 10000;
RBTree<int, int> t;
for (size_t i = 0; i < N; ++i)
{
size_t x = rand();
t.Insert(make_pair(x, x));
t.Isbalance();
}
t.Inorder();
}序列式容器和关联式容器
序列式容器
序列式容器（sequential container),其底层是线性数据结构，里面存储的元素是数据本身，元素的顺序不依赖于元素的值，而是于元素加入容器时的位置相对应。比如vector，list，deque等等。
关联式容器
关联式容器（associative container),该类容器也是用来存储数据的，但是里面的存储元素结构为<key,value>这样的键值对，其元素的查找、访问和元素在容器中的顺序是根据关键字key，在数据检索时比序列式容器更高效。
根据应用场景不同，STL总共实现了两种不同结构的关联式容器：树形结构和哈希结构。树形结构主要有四种：map,set,multimap,multiset。这四种容器的共同点是使用平衡搜索树即红黑树作为底层结构，容器中的元素是一个有序的序列。下面开始介绍这几个关联式容器
在介绍关联式容器之前先来介绍键值对
键值对
<font size=5 color="red">用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。因此又称KV键值对</font>
SGI—STL中关于键值对的定义：
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};定义了一个pair类，类的第一个参数模板为T1，第二个参数模板为T2，参数first和second。一般情况下，第一个参数为key，第二个参数为value即pair(const T1&key,const T2&value),value是键值key对应的信息。一般通过查找key来查询或者修改value。
比如map的pair<const key_type,mapped_type>这里可以看到map的key是不能随便改变的，而value是可以更改的
image-20230324191338174
后面介绍的容器里会有所体现键值对的价值。
set
set是啥？一句话：set的底层是一棵二叉搜索树（红黑树），其中的元素不重复且有序（去重且默认升序）
image-20230324190117268
T: set中存放元素的类型，实际在底层存储<value, value>的键值对。
Compare：set中元素默认按照小于来比较
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理
<font size=4 color="red">set里面的key(value也是key）是不能被修改的（这里红黑树的值被修改后就不是红黑树了）</font>
image-20230409172440535
在下图可以看到，插入了两个1打印出来时只有一个1，表明set去重了；且元素是以升序打印，那么遍历时应该是以中序遍历。
image-20230324115930073
与set相似的容器还有一个multiset，它和set共用一个头文件，那么multiset和set有什么区别呢？
image-20230324163021979
image-20230324164217602
通过看文档对比可以知道，set里的元素是唯一的，而multiset里的元素允许多个，即set里的key与value一一对应，而multiset里的key可以与多个value相对应。那么multiset的作用就只是排序（不去重）
image-20230324170251300
set头文件里有一个count函数，调用后返回元素对应的value个数
image-20230324170417751
set里的元素都是唯一的，那么调用后要么返回0要么返回1，而multiset里的元素对应的value是可以多样的，所以返回的count可以是里面key对应的value的个数
image-20230324170753800
这样的对比后可以知道count函数对于set意义不大，而对应multiset意义还是比较大的
那么在multiset里找同样的value时，是怎么的一个查找返回机制呢？
image-20230324172408046
image-20230324172518867
通过实验证明，在multiset里查找元素，是返回<font size=5 color="red">中序遍历</font>找到的第一个对应元素的迭代器！
lower_bound和upper_bound
调用lower_bound,返回>=传入的value的元素的迭代器
调用upper_bound,返回>传入的value的元素的迭代器
std::multiset<int> mymultiset;
std::multiset<int>::iterator itlow, itup;
for (int i = 1; i < 8; i++) mymultiset.insert(i * 10); // 10 20 30 40 50 60 70
itlow = mymultiset.lower_bound(35); //传入35，返回>=35的元素的迭代器即40的迭代器
cout << "返回小于等于35元素迭代器："<<*itlow<<"的迭代器" << endl;
itup = mymultiset.upper_bound(40); // 传入40，返回>40的元素的迭代器即50的迭代器
cout << "返回大于40元素迭代器："<<*itup<<"的迭代器" << endl;
for (auto e : mymultiset)
{
cout << e << " ";
}
cout << endl;
mymultiset.erase(itlow, itup); // 删除区间[40,50）的元素，打印 10 20 30 50 60 70
for (std::multiset<int>::iterator it = mymultiset.begin(); it != mymultiset.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
image-20230324185621499
map
- map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
- 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为
pair:typedef pair<const key, T> value_type;
- 在内部，map中的元素总是按照键值key进行比较排序的。
- map支持下标访问符，即在[]中放入key，就可以找到与key对应的value并且可以修改value。
- map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。key和value一一对应（排序去重）
int main()
{
map<string, string> dict;
dict.insert(pair<string, string>("蔡徐坤", "cxk"));
dict.insert(pair<string, string>("小黑子", "ikun"));
dict.insert(make_pair("爆炸", "boom"));
dict.insert(make_pair("篮球", "basketbll"));
//map<string, string>::iterator it = dict.begin();
auto it = dict.begin();
while (it != dict.end())
{
//cout << (*it).first << ":" << (*it).second << endl;
cout << it->first << ":" << it->second << endl;
it++;
}
return 0;
}
image-20230324195456453
image-20230324194445791
这里实现了一个对于出现的名称的次数统计
image-20230324204141794
通过迭代器、find和insert函数可以实现，但在这里operator[]就能完成
operator[]
image-20230324204341422
查阅文档map中的operator[]
image-20230324205959442
operator[]就是在insert时，返回值是pair，pair的first会返回一个迭代器,second返回true或flase;如果在map中没有此元素，那么就插入一个新的元素并且返回这个元素的迭代器，返回true表示插入成功；
但如果map中已经存在该元素就返回该元素的迭代器，返回false;this指针找到这个insert返回的first即迭代器并且解引用即元素的pair对象，然后取这个对象的second即value，并且返回value的引用，那么在上层就能够修改它！
operator[]简化一下就是如下图这样的功能
image-20230324210500464
若insert时map中已经有了该元素，那么insert就相当于充当了find的功能；这就可以知道operator[]具有插入、查找、修改的功能。
简单来说，在map中插入值时，如果值已经在了，（那么元素的second给你修改），但如果不在就给你插入
image-20230324211458877
multimap和map也共用同一个头文件，与multiset相同的multimap中也可存储与key相对应的多个value的元素，即只排序但不去重。但是multimap没有operator[]，因为operator[]中的insert返回元素的迭代器，当其中有多个相同value的元素时就不知道返回哪个元素的迭代器了。
用红黑树封装set和map
先实现RBTree的迭代器
迭代器类框架
template<class T,class Self,class Ptr>//依次是T，T&，T*
class __RBTreeIterator
{
typedef RBTreeNode<T> node;
public:
typedef __RBTreeIterator<T,Self,Ptr> self;//typedef迭代器本身
typedef __RBTreeIterator<T, T&, T*> iterator;//普通迭代器
node* _node;
__RBTreeIterator( node* node)//迭代器构造函数---结点构造迭代器
:_node(node)
{}
};<font size=5 color="red">begin是整棵树最左结点，end是空节点（这里我当作是根结点的父节点）</font>
迭代器加加
依次按照中序：左中右遍历；当当前结点的右子树遍历完就遍历父亲结点，否则迭代器跳到右子树的最左结点；这里的遍历父亲结点是遍历当前结点是父亲结点的左结点的那个父亲，否则依次更新，因为当前结点在父节点的右边，意味着此时的父节点已经遍历过了。
下面动图是假设迭代器it在begin位置，然后进行迭代器加加的行为
红黑树迭代器加加
self operator++()//迭代器++，返回值是self是迭代器模板参数，const迭代器和普通迭代器都能返回
{
if (_node->_right)
{
node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
else//右空了，找parent
{
node* cur = _node;
node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}迭代器减减
按照右中左的次序遍历，当此时结点的左子树遍历完后，就遍历到父亲节点，否则就跳到左子树的最右节点；这里要遍历的父节点是当前节点在父节点的右边的那个父节点，否则依次更新上去。
红黑树迭代器减减
self operator--()
{
if (_node->_left)
{
node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
else//左完了回空
{
node* cur = _node;
node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}完整迭代器代码
template<class T,class Self,class Ptr>//依次是T，T&，T*
class __RBTreeIterator
{
typedef RBTreeNode<T> node;
public:
typedef __RBTreeIterator<T,Self,Ptr> self;//typedef迭代器本身
typedef __RBTreeIterator<T, T&, T*> iterator;//typedef迭代器本身
node* _node;
__RBTreeIterator( node* node)//迭代器构造函数---结点构造迭代器
:_node(node)
{}
__RBTreeIterator(const iterator & s)//传入的是普通迭代器
//上层要const迭代器时，就是传入普通迭代器构造const迭代器；
//当上层要普通迭代器时，这个就是普通迭代器的拷贝构造
:_node(s._node)
{}
Self operator*()const
{
return _node->_data;//解引用返回数据本身
}
Ptr operator->()const
{
return &(_node->_data);//※，取地址--返回数据的地址
}
self operator++()//迭代器++
{
if (_node->_right)
{
node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
else//右空了，找parent
{
node* cur = _node;
node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
self operator--()
{
if (_node->_left)
{
node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
else//左完了回空
{
node* cur = _node;
node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const self&s)const
{
return _node != s._node;
}
bool operator==(const self& s)const
{
return _node == s._node;
}
};完善迭代器后的红黑树整体代码
template<class K,class T,class KeyofT>
class RBTree
{
typedef RBTreeNode<T> node;
public:
typedef __RBTreeIterator<T,T&,T*> iterator;//给外部使用，得放进公有
//const迭代器
typedef __RBTreeIterator<T,const T&,const T*> const_iterator;
iterator begin()
{
node* left = _root->_left;
while (left && left->_left)
{
left = left->_left;
}
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin()const
{
node* left = _root->_left;
while (left && left->_left)
{
left = left->_left;
}
return const_iterator(left);
}
const_iterator end()const
{
return const_iterator(nullptr);
}
pair<iterator,bool> Insert(const T& data)//这里是迎合了map的[]重载的改动
//使得[]具有插入，查找，更改的功能
//插入节点时，当该节点存在时，第一个参数就返回以存在节点的迭代器，第二个参数返回false；当节点不存在，那么就插入，插入成功后，第一个参数返回新节点的迭代器，第二个参数返回true
{
if (_root == nullptr)
{
_root = new node(data);
_root->_col = Black;
return make_pair(iterator(_root),true);
//第一个参数是返回迭代器，先用结点构造迭代器再返回；如果不存在该值的结点，就插入新结点，并且返回这个新结点的迭代器，第二个参数返回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
{
//找到相同元素。返回这个已存在节点的迭代器，返回false
return make_pair(iterator(cur),false);
}
}
//链接--cur找到空的位置
cur = new node(data);
cur->_col = RED;
node* newnode = cur;//后期cur的指向会变化，先记录新建结点的地址
if (kot(parent->_data) < kot(cur->_data))//比它大，链接右边
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//做调整
while (parent && parent->_col == RED)//红色
{
node* grandparent = parent->_parent;
if (grandparent)//g不为空
{
if (parent == grandparent->_left)//parent在左，uncle在右？
{
node* uncle = grandparent->_right;
//情况一:uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = Black;//p和u变黑
grandparent->_col = RED;//g变红
cur = grandparent;
parent = cur->_parent;//往上调整
}
else
{
if (cur == parent->_left)//情况二,此时不需要考虑uncle结点了
{
RotateR(grandparent);
parent->_col = Black;
grandparent->_col = RED;
}
else//cur在parent的右孩子，呈现折现形式，情况三
{
RotateL(parent);
RotateR(grandparent);
cur->_col = Black;
grandparent->_col = RED;
}
break;
}
}
else//parent在右，uncle在左？
{
node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)//情况一
{
parent->_col = uncle->_col = Black;
grandparent->_col = RED;
cur = grandparent;
parent=cur->_parent;
}
else
{
if (cur == parent->_right)//情况二
{
RotateL(grandparent);
parent->_col = Black;
grandparent->_col = RED;
}
else//情况三
{
RotateR(parent);
RotateL(grandparent);
cur->_col = Black;
grandparent->_col = RED;
}
break;
}
}
}
}
_root->_col = Black;
return make_pair(iterator(newnode),true);
//第一个参数是返回迭代器，先用结点构造迭代器再返回；如果不存在该值的结点，就插入新结点，并且返回这个新结点的迭代器，第二个参数返回true
}
void RotateR(node* parent)//右旋
{
node* ppnode = parent->_parent;
node* subL = parent->_left;
node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (ppnode == nullptr)//父节点的父节点为空
{
_root = subL;
subL->_parent = nullptr;
}
else//父节点的父节点不为空
{
if (parent == ppnode->_left)//parent为父父节点的左
{
ppnode->_left = subL;
}
else//parent为父父节点的右
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
}
void RotateL(node* parent)//左旋
{
node* ppnode = parent->_parent;
node* subR = parent->_right;
node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subR;
if (ppnode == nullptr)//父父节点为空
{
_root = subR;
subR->_parent = nullptr;
}
else//父父节点不为空
{
if (parent == ppnode->_left)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
}
void Inorder()
{
_Inorder(_root);
}
void _Inorder(node* root)//中序遍历打印
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << ":" << root->_col << endl;
_Inorder(root->_right);
}
bool check(node* root, int blacknum, int _ref)
{
if (root == nullptr)
{
if (blacknum != _ref)
{
cout << "每条路径上的黑色结点数量不相同，违反了规则4" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "红色结点连续出现，违背了规则3" << endl;
return false;
}
if (root->_col == Black)
blacknum++;
return check(root->_left, blacknum, _ref)
&& check(root->_right, blacknum, _ref);
}
bool Isbalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col == RED)
{
return false;
}
int ref = 0;
node* Left = _root;
while (Left)
{
if (Left->_col == Black)
ref++;//记录最左边路径上黑色结点的数量
Left = Left->_left;
}
return check(_root, 0, ref);
}
private:
node* _root = nullptr;
};set整体代码
template<class K>
class Set
{
public:
struct SetOT//构造模板函数处理比较问题
{
const K& operator()(const K& key)
{
return key;
}
};
//typedef的是一个类的内部类型，不知道是静态变量还是类型，typename告诉编译器这是类型
typedef typename RBTree<K, K, SetOT>::const_iterator iterator;//都是const迭代器，key不能指针修改
typedef typename RBTree<K, K, SetOT>::const_iterator const_iterator;//const迭代器
pair<iterator, bool> Insert(const K& key)
{
pair<iterator, bool> ret = _t.Insert(key);
return make_pair(ret.first,ret.second);
}
iterator begin()
{
return _t.begin();
}
iterator end()const//const成员函数使得this指针不能更改任何类中任何成员
{
return _t.end();
}
iterator begin()const
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
RBTree<K, K, SetOT>_t;//套用红黑树
};map整体代码
template<class K, class V>
class Map
{
public:
struct MapofT
{
const K& operator()(const pair<const K, V>& kv)const
{
return kv.first;
}
};
typedef typename RBTree<K, pair<const K, V>, MapofT>::iterator iterator;//这里编译器不知道是类中静态变量还是类型，typename告诉编译器这里是类型
typedef typename RBTree<K, pair<const K, V>, MapofT>::const_iterator const_iterator;//const迭代器
iterator begin()
{
return _mp.begin();
}
iterator end()
{
return _mp.end();
}
const_iterator begin()const
{
return _mp.begin();
}
const_iterator end()const
{
return _mp.end();
}
pair<iterator,bool> Insert(const pair<const K, V>& kv)
{
return _mp.Insert(kv);
}
V& operator[](const K& key)
//具备查找（find），插入（insert），修改的功能
//插入失败时（已存在相同节点）即是find又是修改，插入成功既是insert
{
pair<iterator, bool> ret = _mp.Insert(make_pair(key, V()));
return ret.first->second;
}
RBTree<K, pair<const K, V>, MapofT> _mp;
};红黑树如何区别对待map和set迭代器行为？
set的value也是key，所以set的value是不能被修改的，而map的value是pair<const K,V>类型，所以map的value是可以被修改的（修改value的第二个参数）；那么当map和set同时调用红黑树的普通迭代器时，红黑树应该如何区分上层的value是允许被修改是不许被修改呢？？？
看待set
image-20230408213723466
通过调试
set层
因为set的value是K，K即是键值又是value，所以K不能修改，所以在set层要用const迭代器，那为什么不只用RBtree的const _iterator呢？因为在set或者map在调用底层RBtree时，RBtree不知道是什么迭代器，所以RBtree层要外加一个普通迭代器构造const迭代器。
image-20230408214444279
看待map
map层
上层（map层）要的是普通迭代器，那么RBtree构造普通迭代器返回就好了，由于map迭代器的value是pair<const K,V>,第一个参数是const不能修改，第二个参数V要可以修改，所以用普通迭代器就足够了
image-20230408220053864
map的[]重载
[]重载在map具有查找，插入，修改的功能。插入新节点时，当该节点已经存在，则返回已存在节点的迭代器，返回false；当没有相同节点，那么插入新节点，返回新节点的迭代器，返回true，[]重载的返回值是value引用，可以通过返回来的节点迭代器去修改节点的value
通过调试
image-20230408223039552
好啦，AVL树，红黑树，红黑树封装map和set的介绍就到这里拉，如果这篇文章对你有帮助的话，请给博主点赞＋收藏，感谢看官的大力支持~
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读