C++map和set(个人笔记)

C++map和set

    • 1.set
      • 1.1set的使用
        • 1.1.1 set的模板参数列表
        • 1.1.2set的构造
        • 1.1.3set的迭代器
        • 1.1.4 set的容量
        • 1.1.5 set修改操作
        • 1.1.6 set的具体使用例子
    • 2.map
      • 2.1map的使用
        • 2.1.1map的模板参数列表
        • 2.1.2map的构造
        • 2.1.3map的迭代器
        • 2.1.4 map的容量与元素访问
        • 2.1.5 map中元素的修改
        • 2.1.6map的具体使用例子
    • 3.multiset
      • 3.1 multiset的具体使用
    • 4.multimap
    • 5.笔试题
    • 6.AVL树
      • 6.1AVL树的实现
        • 6.1.1AVL树节点的定义
        • 6.1.2AVL树的插入
        • 6.1.4AVL树的旋转
        • 6.1.5AVL树的验证
    • 7.红黑树
      • 7.1红黑树的性质
      • 7.2红黑树的实现
        • 7.2.1红黑树节点的定义
        • 7.2.2红黑树的插入操作
        • 7.2.3红黑树的验证
    • 8.红黑树与AVL树的比较
    • 9.map和set模拟实现
      • 9.1改造红黑树
      • 9.2map模拟实现
      • 9.3set的模拟实现

1.set

C++set官方文档

  1. set是按照一定次序存储元素的容器
  2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
  3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
  4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
  5. set在底层是用二叉搜索树(红黑树)实现的。

注意：

  1. 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
  2. set中插入元素时，只需要插入value即可，不需要构造键值对。
  3. set中的元素不可以重复(因此可以使用set进行去重)。
  4. 使用set的迭代器遍历set中的元素，可以得到有序序列
  5. set中的元素默认按照小于来比较
  6. set中查找某个元素，时间复杂度为： l o g 2 n log_2 n log2​n
  7. set中的元素不允许修改
  8. set中的底层使用二叉搜索树(红黑树)来实现。

1.1set的使用

1.1.1 set的模板参数列表

在这里插入图片描述
T: set中存放元素的类型，实际在底层存储<value, value>的键值对。
Compare：set中元素默认按照小于来比较
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

1.1.2set的构造
函数声明功能介绍
set (const Compare& comp = Compare(), const Allocator& = Allocator() );构造空的set
set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );用[first, last)区间中的元素构造set
set ( const set<Key,Compare,Allocator>& x);set的拷贝构造
1.1.3set的迭代器
函数声明功能介绍
iterator begin()返回set中起始位置元素的迭代器
iterator end()返回set中最后一个元素后面的迭代器
const_iterator cbegin() const返回set中起始位置元素的const迭代器
const_iterator cend() const返回set中最后一个元素后面的const迭代器
reverse_iterator rbegin()返回set第一个元素的反向迭代器，即end
reverse_iterator rend()返回set最后一个元素下一个位置的反向迭代器，即begin
const_reverse_iterator crbegin() const返回set第一个元素的反向const迭代器，即cend
const_reverse_iterator crend() const返回set最后一个元素下一个位置的反向const迭代器，即cbegin
1.1.4 set的容量
函数声明功能介绍
bool empty ( ) const检测set是否为空，空返回true，否则返回false
size_type size() const返回set中有效元素的个数
1.1.5 set修改操作
函数声明功能介绍
pair<iterator,bool> insert ( const value_type& x )在set中插入元素x，实际插入的是<x, x>构成的键值对，如果插入成功，返回<该元素在set中的位置，true>,如果插入失败，说明x在set中已经存在，返回<x在set中的位置，false>
void erase ( iterator position )删除set中position位置上的元素
size_type erase ( const key_type& x )删除set中值为x的元素，返回删除的元素的个数
void erase ( iterator first, iterator last )删除set中[first, last)区间中的元素
void swap ( set<Key,Compare,Allocator>& st );交换set中的元素
void clear ( )将set中的元素清空
iterator find ( const key_type& x ) const返回set中值为x的元素的位置
size_type count ( const key_type& x ) const返回set中值为x的元素的个数
1.1.6 set的具体使用例子
#include<iostream>
#include<set>
using namespace std;
void TestSet()
{
	//用数组arr中的元素构造set
	int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
	set<int> s(arr, arr + sizeof(arr) / sizeof(arr[0]));
	cout << s.size() << endl;

	//正向打印set中的元素,从打印结果中可以看出:set可以去重
	for (auto& e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	//使用迭代器逆向打印set中的元素
	for (auto it = s.begin();it != s.end();it++)
	{
		cout << *it << endl;
	}
	cout << endl;

	//set中值为3的元素出现了几次
	cout << s.count(3) << endl;
}

2.map

C++map的官方文档

  1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
  2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:
    typedef pair<const key, T> value_type;
  3. 在内部，map中的元素总是按照键值key进行比较排序的。
  4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
  5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
  6. map通常被实现为二叉搜索树(平衡二叉搜索树(红黑树))。

2.1map的使用

2.1.1map的模板参数列表

在这里插入图片描述
key: 键值对中key的类型
T： 键值对中value的类型
Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

2.1.2map的构造
函数声明功能介绍
map（）构造一个空的map
2.1.3map的迭代器
函数声明功能介绍
begin() 和 end()begin:首元素的位置，end最后一个元素的下一个位置
cbegin()和cend()与begin和end意义相同，但cbegin和cend所指向的元素不能修改
rbegin()和rend()反向迭代器，rbegin在end位置，rend在begin位置，其++和–操作与begin和end操作移动相反
crbegin()和crend()与rbegin和rend位置相同，操作相同，但crbegin和crend所指向的元素不能修改
2.1.4 map的容量与元素访问
函数声明功能介绍
bool empty ( ) const检测map中的元素是否为空，是返回true，否则返回false
size_type size() const返回map中有效元素的个数
mapped_type& operator[] (const key_type& k)返回去key对应的value

当key不存在时，operator[]用默认value与key构造键值对然后插入

2.1.5 map中元素的修改
函数声明功能介绍
pair<iterator,bool> insert ( const value_type& x )在map中插入键值对x，注意x是一个键值对，返回值也是键值对：iterator代表新插入元素的位置，bool代表释放插入成功
void erase ( iterator position )删除position位置上的元素
void erase ( const key_type& x )删除键值为x的元素
void erase ( iterator first, iterator last )删除[first, last)区间中的元素
void swap ( map<Key,T,Compare,Allocator>& mp )交换两个map中的元素
void clear ( )将map中的元素清空
iterator find ( const key_type& x )在map中寻找key为x的元素，找到返回该元素的位置的迭代器，否则返回end位置的迭代器
const_iterator find ( const key_type& x ) const在map中寻找key为x的元素，找到返回该元素的位置的const迭代器，否则返回cend位置的迭代器
size_type count ( const key_type& x ) const返回key为x的键值在map中的个数，注意map中key是唯一的，因此该函数的返回值要么为0，要么为1，因此也可以用该函数来检测一个key是否在map中
2.1.6map的具体使用例子
#include<string>
#include<map>
#include<iostream>
void TestMap()
{
	map<string, string> m;
	//向map中插入元素的方式:
	//将键值对<"peach","桃子">插入map中,用pair直接来构造键值对
	m.insert(pair<string, string>("peach", "桃子"));

	//将键值对<"peach","桃子">插入map中，用make_pair函数来构造键值对
	m.insert(make_pair("peach", "桃子"));

	//借用operator[]向map中插入元素
/*
 operator[]的原理是：
  用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中
  如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器
  如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器
  operator[]函数最后将insert返回值键值对中的value返回
 */

    // 将<"apple", "">插入map中，插入成功，返回value的引用，将“苹果”赋值给该引用结果，
	m["apple"] = "苹果";

	//用迭代器去遍历map中的元素，可以得到一个按照key排序的序列
	for (auto& e : m)
	{
		cout << e.first << "->" << e.second << endl;
	}
	cout << endl;

	//map中的键值对key一定是唯一的，如果key存在将插入失败
	auto ret = m.insert(make_pair("peach", "桃色"));
	if (ret.second)
	{
		cout << "<peach, 桃色>不在map中, 已经插入" << endl;
	}
	else
	{
		cout << "键值为peach的元素已经存在：" << ret.first->first << "--->"<< ret.first->second << " 插入失败" << endl;
	}

	//删除key为“apple”的元素
	m.erase("apple");
	if (1 == m.count("apple"))
	{
		cout << "apple还在" << endl;
	}
	else
	{
		cout << "apple被吃了" << endl;
	}
}

总结:

  1. map中的的元素是键值对
  2. map中的key是唯一的，并且不能修改
  3. 默认按照小于的方式对key进行比较
  4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列
  5. map的底层为平衡搜索树(红黑树)，查找效率比较高 O ( l o g 2 N ) O(log_2 N) O(log2​N)
  6. 支持[]操作符，operator[]中实际进行插入查找。

3.multiset

C++multiset官方文档

  1. multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
  2. 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
  3. 在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
  4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
  5. multiset底层结构为二叉搜索树(红黑树)。

注意：

  1. multiset中再底层中存储的是<value, value>的键值对
  2. mtltiset的插入接口中只需要插入即可
  3. 与set的区别是，multiset中的元素可以重复，set是中value是唯一的
  4. 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
  5. multiset中的元素不能修改
  6. 在multiset中找某个元素，时间复杂度为 O ( l o g 2 N ) O(log_2 N) O(log2​N)
  7. multiset的作用：可以对元素进行排序

3.1 multiset的具体使用

#include<set>
void TestSet()
{
	int arr[]= { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };
	//注意multiset在底层实际储存的是<int,int>的键值对
	multiset<int> s(arr, arr + sizeof(arr) / sizeof(arr[0]));
	for (auto& e : s)
	{
		cout << e << "";
	}
	cout << endl;
}

4.multimap

C++multimap的官方文档

  1. Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key, value>，其中多个键值对之间的key是可以重复的。
  2. 在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，
    value_type是组合key和value的键值对:
    typedef pair<const Key, T> value_type;
  3. 在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。
  4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
  5. multimap在底层用二叉搜索树(红黑树)来实现。

注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。

5.笔试题

前K个高频单词
在这里插入图片描述

class Solution {
public:
    struct kvCom
    {
        bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2)
        {
            return kv1.second > kv2.second || (kv1.first < kv2.first && kv1.second == kv2.second);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k)
    {
        map<string,int> mp;
        for(auto& e:words)
        {
            mp[e]++;
        }
        vector<pair<string,int>> sortV(mp.begin(),mp.end());
        sort(sortV.begin(),sortV.end(),kvCom());
        vector<string> v;
        for(size_t i=0;i<k;i++)
        {
            v.push_back(sortV[i].first);
        }
        return v;
    }
};

两个数组的交集
在这里插入图片描述

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
    {
        vector<int> v;
        set<int> s1(nums1.begin(),nums1.end());
        set<int> s2(nums2.begin(),nums2.end());
        auto it1=s1.begin();
        auto it2=s2.begin();
        while(it1!=s1.end()&&it2!=s2.end())
        {
            if(*it1<*it2)
            {
                it1++;
            }
            else if(*it1>*it2)
            {
                it2++;
            }
            else
            {
                v.push_back(*it1);
                it1++;
                it2++;
            }
        }
        return v;
    }
};

6.AVL树

向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

  1. 它的左右子树都是AVL树
  2. 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在
O ( l o g 2 n ) O(log_2 n) O(log2​n)，搜索时间复杂度O( l o g 2 n log_2 n log2​n)。

6.1AVL树的实现

6.1.1AVL树节点的定义
template<class K, class V>
struct AVLTreeNode
{
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;  // balance factor

	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};
6.1.2AVL树的插入

在这里插入图片描述

分两步：

  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子
bool Insert(const pair<K, 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->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}

	cur->_parent = parent;

	// ... 控制平衡
	// 更新平衡因子
	while (parent)
	{
		if (cur == parent->_left)
		{
			parent->_bf--;
		}
		else // if (cur == parent->_right)
		{
			parent->_bf++;
		}

		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)
			{
				RotateL(parent);
			}
			else if (parent->_bf == -2 && cur->_bf == -1)
			{
				RotateR(parent);
			}
			else if (parent->_bf == 2 && cur->_bf == -1)
			{
				RotateRL(parent);
			}
			else if (parent->_bf == -2 && cur->_bf == 1)
			{
				RotateLR(parent);
			}

			break;
		}
		else
		{
			assert(false);
		}
	}


	return true;
}
6.1.4AVL树的旋转

左单旋：
在这里插入图片描述

void RotateL(Node* parent)
{
	++_rotateCount;

	Node* cur = parent->_right;
	Node* curleft = cur->_left;

	parent->_right = curleft;
	if (curleft)
	{
		curleft->_parent = parent;
	}

	cur->_left = parent;

	Node* ppnode = parent->_parent;

	parent->_parent = cur;


	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)
{
	++_rotateCount;

	Node* cur = parent->_left;
	Node* curright = cur->_right;

	parent->_left = curright;
	if (curright)
		curright->_parent = parent;

	Node* ppnode = parent->_parent;
	cur->_right = parent;
	parent->_parent = cur;

	if (ppnode == nullptr)
	{
		_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 RotateRL(Node* parent)
{
	Node* cur = parent->_right;
	Node* curleft = cur->_left;
	int bf = curleft->_bf;

	RotateR(parent->_right);
	RotateL(parent);

	if (bf == 0)
	{
		cur->_bf = 0;
		curleft->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 1)
	{
		cur->_bf = 0;
		curleft->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1)
	{
		cur->_bf = 1;
		curleft->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

左右单旋：
在这里插入图片描述

void RotateLR(Node* parent)
{
	Node* cur = parent->_left;
	Node* curright = cur->_right;
	int bf = curright->_bf;

	RotateL(parent->_left);
	RotateR(parent);

	if (bf == 0)
	{
		parent->_bf = 0;
		cur->_bf = 0;
		curright->_bf = 0;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		cur->_bf = 0;
		curright->_bf = 0;
	}
	else if (bf == 1)
	{
		parent->_bf = 0;
		cur->_bf = -1;
		curright->_bf = 0;
	}
}
6.1.5AVL树的验证
  1. 验证其为二叉搜索树
    如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
void _InOrder(Node* root)
{
	if (root == nullptr)
	{
		return;
	}
	_InOrder(root->_left);
	cout << root->_kv.first << " ";
	_InOrder(root->_right);
}
  1. 验证其为平衡树
    每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
    节点的平衡因子是否计算正确
int _Height(Node* root)
{
	if (root == nullptr)
	{
		return 0;
	}
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	return leftHeight < rightHeight ? leftHeight + 1 : rightHeight + 1;
}

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);
}

7.红黑树

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

7.1红黑树的性质

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 （就是不能有连续的红色节点）
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

7.2红黑树的实现

7.2.1红黑树节点的定义
enum Colour
{
	RED,
	BLACK
};

template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};
7.2.2红黑树的插入操作

新增：插入红色节点

1.插入节点的父亲是黑色节点，那么直接就结束了，没有违反任何规则
2.插入节点的父亲是红色节点，那么存在连续的红色节点，违反规则三，需要处理
情况一：cur为红，p为红，g为黑，u存在且为红
解决方案：将p，u改为黑，g改为红，然后把g赋值给cur，继续向上调整
在这里插入图片描述
情况二：
1.cur为红，p为红，g为黑，u不存在
解决方案：p为g的左孩子，cur为p的左孩子，则进行右单旋，相反，p为g的右孩子，cur为p的右孩子，则进行左单旋，p变黑，g变红
在这里插入图片描述
2.cur为红，p为红，g为黑，u存在且为黑（中间态是由下层变上来的）
在这里插入图片描述
情况三：cur为红，p为红，g为黑，u不存在或者存在且为黑（其实就是g，p，c是折线，经过一次旋转后变成情况二）
在这里插入图片描述

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;
		}
	}

	// 新增节点给红色
	cur = new Node(kv);
	cur->_col = RED;
	if (parent->_kv.first < kv.first)
	{
		parent->_right = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_left = cur;
		cur->_parent = parent;
	}

	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;
		if (parent == grandfather->_left)
		{
			//     g
			//   p   u
			// c
			Node* uncle = grandfather->_right;
			if (uncle && uncle->_col == RED)
			{
				// 变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续往上更新处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				if (cur == parent->_left)
				{
					// 单旋
					//     g
					//   p
					// c
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					// 双旋
					//     g
					//   p
					//     c
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}
		else  // parent == grandfather->_right
		{
			//     g
			//   u   p 
			//          c
			//
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == RED)
			{
				// 变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				//        g
				//           p
				//              c
				if (cur == parent->_right)
				{
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//     g
					//   u   p 
					//     c
					//
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}
	}

	_root->_col = BLACK;

	return true;
}

void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	subR->_left = parent;

	Node* parentParent = parent->_parent;

	parent->_parent = subR;
	if (subRL)
		subRL->_parent = parent;

	if (_root == parent)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (parentParent->_left == parent)
		{
			parentParent->_left = subR;
		}
		else
		{
			parentParent->_right = subR;
		}

		subR->_parent = parentParent;
	}
}

void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;

	Node* parentParent = parent->_parent;

	subL->_right = parent;
	parent->_parent = subL;

	if (_root == parent)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (parentParent->_left == parent)
		{
			parentParent->_left = subL;
		}
		else
		{
			parentParent->_right = subL;
		}

		subL->_parent = parentParent;
	}
}
7.2.3红黑树的验证
  1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
  2. 检测其是否满足红黑树的性质
void InOrder()
{
	_InOrder(_root);
	cout << endl;
}

void _InOrder(Node* root)
{
	if (root == nullptr)
		return;

	_InOrder(root->_left);
	cout << root->_kv.first << " ";
	_InOrder(root->_right);
}

bool Check(Node* root, int blacknum, const int refVal)
{
	if (root == nullptr)
	{
		//cout << balcknum << endl;
		if (blacknum != refVal)
		{
			cout << "存在黑色节点数量不相等的路径" << endl;
			return false;
		}

		return true;
	}

	if (root->_col == RED && root->_parent->_col == RED)
	{
		cout << "有连续的红色节点" << endl;

		return false;
	}

	if (root->_col == BLACK)
	{
		++blacknum;
	}

	return Check(root->_left, blacknum, refVal)
		&& Check(root->_right, blacknum, refVal);
}

bool IsBalance()
{
	if (_root == nullptr)
		return true;

	if (_root->_col == RED)
		return false;

	//参考值
	int refVal = 0;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			++refVal;
		}

		cur = cur->_left;
	}

	int blacknum = 0;
	return Check(_root, blacknum, refVal);
}

8.红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( l o g 2 N log_2 N log2​N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

9.map和set模拟实现

9.1改造红黑树

#pragma once

// set ->key
// map ->key/value

enum Colour
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	T _data;

	Colour _col;

	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};

template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T, Ref, Ptr> Self;
	Node* _node;

	__TreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	Self& operator--();

	Self& operator++()
	{
		if (_node->_right)
		{
			// 下一个就是右子树的最左节点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}

			_node = cur;
		}
		else
		{
			// 左子树 根 右子树
			// 右为空，找孩子是父亲左的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}

	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
};

// set->RBTree<K, K, SetKeyOfT> _t;
// map->RBTree<K, pair<const K, T>, MapKeyOfT> _t;
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __TreeIterator<T, T&, T*> iterator;
	typedef __TreeIterator<T, 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);
	}

	const_iterator begin() const
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return const_iterator(cur);
	}

	const_iterator end() const
	{
		return const_iterator(nullptr);
	}

	//pair<iterator, bool> Insert(const T& data)
	pair<Node*, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(_root, 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
			{
				return make_pair(cur, false);
			}
		}

		// 新增节点给红色
		cur = new Node(data);
		Node* newnode = cur;
		cur->_col = RED;
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				//     g
				//   p   u
				// c
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上更新处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						// 单旋
						//     g
						//   p
						// c
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						// 双旋
						//     g
						//   p
						//     c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else  // parent == grandfather->_right
			{
				//     g
				//   u   p 
				//          c
				//
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//     g
						//   u   p 
						//     c
						//
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;

		return make_pair(newnode, true);
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		subR->_left = parent;

		Node* parentParent = parent->_parent;

		parent->_parent = subR;
		if (subRL)
			subRL->_parent = parent;

		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		}
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}

	// 根节点->当前节点这条路径的黑色节点的数量
	bool Check(Node* root, int blacknum, const int refVal)
	{
		if (root == nullptr)
		{
			//cout << balcknum << endl;
			if (blacknum != refVal)
			{
				cout << "存在黑色节点数量不相等的路径" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "有连续的红色节点" << endl;

			return false;
		}

		if (root->_col == BLACK)
		{
			++blacknum;
		}

		return Check(root->_left, blacknum, refVal)
			&& Check(root->_right, blacknum, refVal);
	}

	bool IsBalance()
	{
		if (_root == nullptr)
			return true;

		if (_root->_col == RED)
			return false;

		//参考值
		int refVal = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refVal;
			}

			cur = cur->_left;
		}

		int blacknum = 0;
		return Check(_root, blacknum, refVal);
	}

	int Height()
	{
		return _Height(_root);
	}

	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	size_t Size()
	{
		return _Size(_root);
	}

	size_t _Size(Node* root)
	{
		if (root == NULL)
			return 0;

		return _Size(root->_left)
			+ _Size(root->_right) + 1;
	}

	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 NULL;
	}

private:
	Node* _root = nullptr;
};

9.2map模拟实现

底层红黑树，结合改造红黑树的代码

#pragma once
#include"RBTree.h"

namespace ljh
{
	template<class K, class V>
	class map
	{
	public:
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

		// 对类模板取内嵌类型，加typename告诉编译器这里是类型
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;


		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert(make_pair(key, V()));
			return ret.first->second;
		}

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}
	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
	};
}

9.3set的模拟实现

底层红黑树，结合改造红黑树的代码

#pragma once
#include"RBTree.h"

namespace ljh
{
	template<class K>
	class set
	{
	public:
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;


		iterator begin() const
		{
			return _t.begin();
		}

		iterator end() const
		{
			return _t.end();
		}

		pair<iterator, bool> insert(const K& key)
		{
			return _t.Insert(key);
		}

	private:
		RBTree<K, K, SetKeyOfT> _t;
	};
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/610577.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

资源管理游戏模版进入The Sandbox

资源管理游戏模版进入The Sandbox

我们非常高兴地向您介绍 Game Maker 的最新模板&#xff1a;资源管理游戏&#xff01; 这一全新的模板让您能够深入身临其境的游戏体验中&#xff0c;同时掌握令人兴奋的新机制。通过揭开模板的神秘面纱&#xff0c;您可以锤炼您的游戏设计技能。 什么是资源管理游戏&#xff1…
阅读更多...
【C语言和Java的对比学习】2（布尔类型、运算符、程序逻辑控制）

【C语言和Java的对比学习】2（布尔类型、运算符、程序逻辑控制）

【C语言和Java的对比学习】2&#xff08;布尔类型、运算符、程序逻辑控制&#xff09; 1. 布尔类型变量2. 逻辑运算符的短路问题2.1 &&和||使用举例2.2 &和|的使用举例 3.位移运算4. switch语句 1. 布尔类型变量 下面我们直接先看下面一组代码的对比图。 注意&am…
阅读更多...
马化腾用了一年多的时间，告诉所有人，视频号小店是新风口！

马化腾用了一年多的时间，告诉所有人，视频号小店是新风口！

大家好&#xff0c;我是电商笨笨熊 当腾讯说出自己要做电商的时候&#xff0c;所有人都在说&#xff0c;根本不可能&#xff1b; 甚至在视频号小店正式推出之后&#xff0c;依旧有人说&#xff0c;腾讯做电商就是笑话&#xff1b; 一个“抄”过来的项目&#xff0c;毫无特色…
阅读更多...
whisper之初步使用记录

whisper之初步使用记录

文章目录 前言 一、whisper是什么&#xff1f; 二、使用步骤 1.安装 2.python调用 3.识别效果评估 4.一点封装 5.参考链接 总结 前言 随着AI大模型的不断发展&#xff0c;语音识别等周边内容也再次引发关注&#xff0c;通过语音转文字再与大模型交互&#xff0c;从而…
阅读更多...
数据库入门（sql文档+命令行）

数据库入门（sql文档+命令行）

一.基础知识 1.SQL&#xff08;Structured Query Language&#xff09;结构化查询语言分类&#xff1a; DDL数据定义语言用来定义数据库对象&#xff1a;数据库、表、字段DML数据操作语言对数据库进行增删改查DQL数据查询语言查询数据库中表的信息DCL数据控制语言用来创建数据…
阅读更多...
用数字化武装文物——博物馆文物管理平台

用数字化武装文物——博物馆文物管理平台

一、引言 在数字化与信息化高速发展的今天&#xff0c;博物馆文物管理面临着前所未有的挑战与机遇。随着科技的不断进步&#xff0c;传统的管理方式已难以满足现代博物馆对文物管理和保护的需求。在此情况下&#xff0c;博物馆文物管理平台以其强大的功能&#xff0c;正成为文物…
阅读更多...
快速理解SPI通信协议（超简单）

快速理解SPI通信协议（超简单）

SPI通信协议 一、SPI协议介绍二、发送数据三、读数据注意 一、SPI协议介绍 SPI是一种全双工的串行通信协议 他有四条线 SCLK&#xff08;Serial Clock&#xff09;&#xff1a;时钟线 MOSI&#xff08;Master Output, Slave Input&#xff09;&#xff1a;关键字母"O&q…
阅读更多...
Highcharts 实现3D饼图 tooltip轮播

Highcharts 实现3D饼图 tooltip轮播

实现3D饼图&#xff0c;并且轮播显示tooltip 自定义toottip样式 import Highcharts from highcharts; import highcharts from highcharts; import highcharts3d from highcharts/highcharts-3d;highcharts3d(Highcharts); highcharts3d(highcharts); import { useEffect, use…
阅读更多...
Docker安装达梦数据库

Docker安装达梦数据库

1.确保已安装Docker 可参考&#xff1a;Linux安装Docker-CSDN博客 2.上传dm镜像并导入安装包 可以从&#xff1a;产品下载 | 达梦数据库下载dm镜像&#xff0c;如下图&#xff1a; docker load -i dm8_20230808.tar 3.导入后查看镜像 docker images 4.启动容器 docker run …
阅读更多...
工业数据采集软件 高效的数字化信息管理系统

工业数据采集软件 高效的数字化信息管理系统

近年来&#xff0c;随着产线自动化程度的提升&#xff0c;越来越多的工业设备被运用到自动化生产中&#xff0c;产线中各位置所产生的数据也越来越多&#xff0c;每个设备又都是独立的&#xff0c;如何将其整合&#xff0c;进行系统化查看处理&#xff0c;就是工业数据采集软件…
阅读更多...
数据结构05：树与二叉树 习题01[C++]

数据结构05：树与二叉树 习题01[C++]

考研笔记整理&#xff0c;本篇作为树与二叉树的基本概念习题&#xff0c;供小伙伴们参考~&#x1f95d;&#x1f95d; 之前的博文链接在此&#xff1a;数据结构05&#xff1a;树与二叉树[C]-CSDN博客~&#x1f95d;&#x1f95d; 第1版&#xff1a;王道书的课后习题~&#x1…
阅读更多...
有什么方便实用的黏土特效教程？6个软件教你快速进行特效制作

有什么方便实用的黏土特效教程？6个软件教你快速进行特效制作

有什么方便实用的黏土特效教程&#xff1f;6个软件教你快速进行特效制作 作为时尚小达人&#xff0c;你自己是否想要制作出属于自己的黏土特效照片呢&#xff1f;比如下面几种。 看到这些黏土特效软件有没有心动&#xff0c;下面我也为大家详细的介绍一下可以制作出对应特效的…
阅读更多...
金石传拓非遗研学基地 入驻蔚蓝书店

金石传拓非遗研学基地 入驻蔚蓝书店

好消息&#xff01;&#xff01;&#xff01; 金石传拓非遗研学基地&#xff0c;正式入驻蔚蓝书店啦&#xff01;&#xff01;&#xff01; “缣竹易销&#xff0c;金石难灭&#xff0c;托以高山&#xff0c;永留不绝。”“金”指的是三代青铜器上的铭文。 “石”指的是石刻、…
阅读更多...
视频号小店应该如何开店呢？详细的开店流程分享给你！

视频号小店应该如何开店呢？详细的开店流程分享给你！

大家好&#xff0c;我是电商小V 视频号小店就是威信视频号团队为咱们商家提供的卖货平台&#xff0c;可以说是支持咱们商家在视频号场景中开店进行经营的模式&#xff0c; 视频号大概的开店流程那就是&#xff1a;找到视频号开店&#xff0c;选择企业入驻&#xff0c;填写信息&…
阅读更多...
win7安装camera raw13.0.2详解。

win7安装camera raw13.0.2详解。

首先win7是不能直接安装camera raw13.0.2的。所以我安装的是camera raw12版本。 然后就是重点了&#xff0c;打开文件C:\Program Files\Common Files\Adobe\Plug-Ins\CC\File Formats&#xff0c; 复制下载的camera raw13.0.2的8bi文件。 替换 这样就能在window7中使用了。网…
阅读更多...
LinkedList链表

LinkedList链表

LinkedList 的全面说明 LinkList底层实现了双向链表和双端队列特点可以添加任意元素&#xff08;元素可以重复&#xff09;&#xff0c;包括null线程不安全&#xff0c;没有实现同步 LinkedList 的底层操作机制 LinkedList底层维护了一个双向链表LinkList中维护了两个属性fi…
阅读更多...
学习javascript，实现一个简易售卖机的功能

学习javascript，实现一个简易售卖机的功能

有同学提问&#xff0c;说想实现一个JS售卖机的功能&#xff0c;我觉得这个挺有意思的&#xff0c;正是初学者学习JS&#xff0c;锻炼软件开发思维的一个好题目&#xff0c;所以就实现了一下&#xff0c;希望可以有帮助。 目录 1 需求分析 2 开发实现 2.1 商家端录入 2.2…
阅读更多...
Linux中的fork与进程地址空间

Linux中的fork与进程地址空间

目录 前言 一、进程地址空间 二、fork的值返回 三、高清图链接 总结 前言 在博主的《进程状态解析》一文中&#xff0c;在讨论进程创建时&#xff0c;提到了一个系统调用接口fork&#xff0c;它在使用过程中表现出对于父子进程不一致的返回结果&#xff0c;而且似乎还具有…
阅读更多...
深入学习指针2

深入学习指针2

前言 hello,我又来了&#xff0c;今天有我继续带领大家深入的学习指针&#xff0c;通过上次的学习&#xff0c;我们已经了解到了指针的基本概念&#xff0c;指针如何使用&#xff0c;指针使用的益处&#xff0c;以及一些相关的概念&#xff0c;那今天我们就继续深入的学习&am…
阅读更多...
Docker笔记（七）使用Docker部署Spring Boot项目

Docker笔记（七）使用Docker部署Spring Boot项目

本文介绍如何使用Docker打包并部署Spring Boot多模块项目。 其中本文涉及的Docker的私库是用Nexus3搭建的。 使用Docker部署Spring Boot项目有三种方式 &#xff08;1&#xff09;使用 spring-boot-maven-plugin内置的build-image. &#xff08;2&#xff09;使用 Google 的 j…
阅读更多...
最新文章

Copyright @ 2022~2023