最新【C++进阶】map和set—，2024新一波程序员跳槽季

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上大数据知识点，真正体系化！

由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新

需要这份系统化资料的朋友，可以戳这里获取

此时：pParent的平衡因子可能有三种情况：0，正负1， 正负2

1. 如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整
   成0，此时满足AVL树的性质，插入成功
2. 如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更
   新成正负1，此时以pParent为根的树的高度增加，需要继续向上更新
3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进
   行旋转处理

pair<Node\*,bool> Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)//根节点为空时先new一个新节点
		{
			_root = new Node(kv);
			return make\_pair(_root, true);
		}
 
		Node\* cur = _root;
		Node\* parent = nullptr;
		//先利用while循环去找cur的空位
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make\_pair(cur, false);
			}
		}
		//将cur插入到相应位置
		cur = new Node(kv);
		Node\* newnode = cur;//用一个newnode记录一下新节点用以返回
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;//注意三叉链的链接逻辑顺序,等号左右方向不能反，先把cur链接到父节点的右边
			cur->_parent = parent;//然后再去把父指针知道父节点
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
 
		//进行旋转调整
		//while(cur!=\_root)
		while (parent)
		{
			//1.进入循环先对平衡因子进行调整
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}
 
			//分三种情况向上走
			if (parent->_bf == 0)//平衡因子等于0不需要调整
			{
				//为什么不需调整
				//因为等于0的话，说明底层子树高度不平衡，添加进入新元素后平衡了，只要平衡了高度并没发生变化，不会影响上面的父节点
				break;
			}
			else if (parent->_bf == -1 || parent->_bf == 1)
			{
				//平衡因子等于-1，说明插入新节点后子树的高度不平衡了，需要继续往上迭代查看父节点是否还满足平衡节点
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				if (parent->_bf == -2)//父节点等于-2，说明左边高，触发右旋的情况
				{
					if (cur->_bf == -1)//cur节点等于-1，说明在cur的左边更高，触发右单旋的情况
					{
						RotateR(parent);
					}
					else//cur等于-1,说明在cur的右边更高，触发左右双旋
					{
						RotateLR(parent);
					}
				}
				else//父节点等于1，说明右边更高，触发左旋的情况
				{
					if (cur->_bf == 1)//cur节点等于1时，说明在cur的右边更高，触发右单旋的情况
					{
						RotateL(parent);
					}
					else//cur等于-1,说明在cur的左边更高，触发右左双旋
					{
						RotateRL(parent);
					}
				}
				//思考：为什么上面在传参数的时候，都是传parent的节点呢？这样的好处是什么呢
 
				break;//调整完成后break退出循环
				//这里为什么调整完成过后就可以退出，通过旋转调整平衡因子后，parent节点的平衡因子都为0了，调整过后不需要再向上继续查找了
			}
			else
			{
				assert(false);
			}
		}
		return make\_pair(newnode,true);
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/882865