• 【C++】AVL树 & 红黑树

    AVL树

    AVL树也是二叉搜索树的一种。因为对于普通的二叉搜索树，当插入的数据在有序或接近有序的情况下，二叉搜索树很可能退化成单支树，导致查找效率低下。而AVL树就很好的解决了这个问题。
    首先，AVL树是一棵二叉搜索树。同时对于AVL树中每个节点，它的左右子树高度之差的绝对值不超过1。
    对于有n个节点的AVL树，其搜索时间复杂度可以稳定的保持在 O ( l o g 2 n ) O(log_2 n) O(log2​n)。
    为了保证向AVL树中插入节点，仍保持其高度的平衡，可以引入平衡因子（平衡因子：右子树的高度 - 左子树的高度）来处理。

    // AVL树节点的定义
template<class K, class V>
class AVLTreeNode
{
public:
	AVLTreeNode(const pair<K, V>& kv)
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}

	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf; //  balance factor
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    因为AVL树仍是二叉搜索树，所以AVL树的插入可以分两步进行：

    1. 按照二叉搜索树的方式插入新节点
    2. 调整平衡因子
    // AVL树的插入
template<class K, class V>
class AVLTree
{
private:
	typedef AVLTreeNode<K, V> Node;
public:
	AVLTree(Node* root = nullptr)
		: _root(root)
	{}
	bool Insert(const pair<K, V>& kv)
	{
		/* 
		* 1.按照二叉搜索树的方式插入新节点
		*/
		
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		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 false;
			}
		}

		// 直接插入
		cur = new Node(kv);
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		/*
		* 2.调整平衡因子
		*/

		while (parent)
		{
			// 新增在右，parent->_bf++; 新增在左，parent->_bf--;
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}

			// 调整后，parent->_bf == 0, 说明parent插入前的平衡因子是 1 or -1，说明插入前左右子树一边高一边低，插入后两边一样高，
			// 即插入填上了矮的一边，插入后parent所在子树高度不变，不需要继续往上调整
			if (parent->_bf == 0)
			{
				break;
			}
			// 调整后，parent->_bf == 1 or -1, 说明parent插入前的平衡因子是0，插入前左右子树高度相等，插入后有一边变高了，
			// parent高度变了，需要继续往上更新
			else if (abs(parent->_bf) == 1)
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}
			// 调整后，parent->_bf == 2 or -2, 说明parent插入前的平衡因子是 1 or -1，已经是平衡临界值，
			// 插入后变成了 2 or -2，打破平衡，parent所在子树需要进行 旋转处理
			else if (abs(parent->_bf) == 2)
			{
				// 根据节点插入位置的不同，AVL树的旋转分为四种
				
				// 新节点插入在较高右子树的右侧（右右）
				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;
			}
			// 调整后，不可能出现parent->_bf > 2 or < -2，否则一定出bug了
			else
			{
				assert(abs(parent->_bf) <= 2);
			}
		}

		return true;
	}
private:
	// 左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		
		// 保存parent的双亲节点
		Node* ppNode = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;

		// parent作为整棵树的根存在
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		// parent作为子树的根存在
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}

		subR->_bf = parent->_bf = 0;
	}
	// 右单旋
	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 (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				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;
		
		// 保存subLR当前的平衡因子
		int bf = subLR->_bf;

		// 先左单旋
		RotateL(parent->_left);
		// 再右单旋
		RotateR(parent);

		// 此处对于平衡因子的调整，建议画图分析
		subLR->_bf = 0;
		if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
		}
		else if(bf == 0)
		{
			parent->_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);

		subRL->_bf = 0;
		if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
private:
	Node* _root;
};

    • 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
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276

    RotateL左单旋示意图：
    在这里插入图片描述
    RotateR右单旋示意图：
    在这里插入图片描述
    RotateLR左右双旋示意图：
    在这里插入图片描述
    在这里插入图片描述
    RotateRL右左双旋示意图：
    在这里插入图片描述
    可以通过下面程序对AVL树的正确性做一个验证。

    template<class K, class V>
class AVLTree
{
private:
	typedef AVLTreeNode<K, V> Node;
public:
	// 1.验证其为二叉搜索树
	void InOrderTraversal()
	{
		_InOrderTraversal(_root);
	}
	
	// 2.验证其为平衡树
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
private:
	// 如果中序遍历为有序序列，则说明为二叉搜索树
	void _InOrderTraversal(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrderTraversal(root->_left);
		cout << root->_kv.first << " : " << root->_kv.second << endl;
		_InOrderTraversal(root->_right);
	}
	
	// 要求每个节点的子树高度差的绝对值不超过1，并且高度差要和平衡因子相等
	bool _IsBalance(Node* root)
	{
		// 空树也算AVL树
		if (root == nullptr)
		{
			return true;
		}

		int leftHt = Height(root->_left);
		int rightHt = Height(root->_right);
		int diff = rightHt - leftHt;

		if (diff != root->_bf)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}
		
		return abs(diff) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}
	int Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftHt = Height(root->_left);
		int rightHt = Height(root->_right);

		return max(leftHt, rightHt) + 1;
	}
private:
	Node* _root;
};

    • 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

    红黑树

    红黑树也是二叉搜索树的一种。
    在这里插入图片描述
    红黑树的性质要求如下：

    1. 每个节点不是红色就是黑色
    2. 根节点是黑色的
    3. 如果一个节点是红色的，则它的两个孩子节点必须是黑色的（或者说不允许存在父子节点同时为红色）
    4. 对于每个节点，从该节点到其后代叶节点的所有简单路径上，都只包含相同数量的黑色节点
    5. 所有的叶节点都是黑色的（叶节点指的是NIL节点）

    通过以上5条性质的约束，就可以确保红黑树中 最长路径 ≤ 2 × 最短路径 最长路径 \leq 2 \times 最短路径 最长路径≤2×最短路径，从而来保证了红黑树的平衡性能。
    虽然红黑树的平衡性能比AVL的略差些，但插入同样的数据，红黑树旋转更少。

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

template<class K, class V>
class RBTreeNode
{
public:
	RBTreeNode(const pair<K, V>& kv)
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
	
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    因为红黑树仍是二叉搜索树，所以红黑树的插入可以分两步进行：

    1. 按照二叉搜索树的方式插入新节点
    2. 检测插入新节点后，红黑树的性质是否受到破坏，并做变色或旋转调整
    template<class K, class V>
class RBTree
{
private:
	typedef RBTreeNode<K, V> Node;
public:
	RBTree(Node* root = nullptr)
		: _root(root)
	{}
	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 (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		// 直接插入新节点
		cur = new Node(kv);
		// 对于插入的新节点赋为红色
		cur->_col = RED;
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		
		// 如果父节点存在且为黑，没有破坏红黑树的规则，不需要调整
		// 如果父节点存在且为红，破坏了性质3
		while (parent && parent->_col == RED)
		{
			// 此时祖父节点一定存在且为黑
			Node* grandparent = parent->_parent;
			assert(grandparent);
			assert(grandparent->_col == BLACK);
			
			// 关键看叔叔(节点)
			// parent 为 grandparent 的左孩子
			if (parent == grandparent->_left)
			{
				Node* uncle = grandparent->_right;
				// 情况一 uncle存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 将 parent 和 uncle 改为黑，grandparent 改为红，
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					// 然后把 grandparent 当成 cur，继续向上调整
					cur = grandparent;
					parent = cur->_parent;
				}
				// 情况二三 uncle不存在，或uncle存在且为黑
				else
				{
					// parent 为 grandparent 的左孩子，且 cur 为 parent 的左孩子
					if (cur == parent->_left)
					{
						// 右单旋
						RotateR(grandparent);
						// 变色: parent 变黑，grandparent 变红
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					// parent 为 grandparent 的左孩子，且 cur 为 parent 的右孩子
					else
					{
						// 左右双旋
						RotateL(parent);
						RotateR(grandparent);
						// 变色: parent 变黑，grandparent 变红
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
					break;
				}
			}
			// parent 为 grandparent 的右孩子
			else
			{
				Node* uncle = grandparent->_left;
				// 情况一 uncle存在且为红
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					
					cur = grandparent;
					parent = cur->_parent;
				}
				// 情况二三 uncle不存在，或uncle存在且为黑
				else
				{
					// parent 为 grandparent 的右孩子，且 cur 为 parent 的右孩子
					if (cur == parent->_right)
					{
						RotateL(grandparent);
						
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					// parent 为 grandparent 的右孩子，且 cur 为 parent 的左孩子
					else
					{
						RotateR(parent);
						RotateL(grandparent);
						
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
					break;
				}
			}
		}
		
		_root->_col = BLACK;
		return true;
	}
private:
	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 (_root == parent)
		{
			_root = subR;
			subR->_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 (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}
private:
	Node* _root;
};

    • 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
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212

    uncle存在且为红：
    在这里插入图片描述
    可以通过下面程序对红黑树的正确性做一个验证。

    template<class K, class V>
class RBTree
{
private:
	typedef RBTreeNode<K, V> Node;
public:
	// 1.验证其为二叉搜索树
	void InOrderTraversal()
	{
		_InOrderTraversal(_root);
	}
	
	// 2. 通过红黑树的性质验证其平衡性
	bool IsBalance()
	{
		// 空树也算红黑树
		if (_root == nullptr)
		{
			return true;
		}
		
		// 验证性质2
		if (_root->_col == RED)
		{
			cout << "根节点不是黑色" << endl;
			return false;
		}

		// benchmark作为每条路径上黑色节点数量的基准值
		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++benchmark;
			}

			cur = cur->_left;
		}

		return PrevCheck(_root, 0, benchmark);	
	}
private:
	// 如果中序遍历为有序序列，则说明为二叉搜索树
	void _InOrderTraversal(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrderTraversal(root->_left);
		cout << root->_kv.first << " : " << root->_kv.second << endl;
		_InOrderTraversal(root->_right);
	}
	
	bool PrevCheck(Node* root, int blackNum, int benchmark)
	{
		if (root == nullptr)
		{
			// 验证性质4
			if (blackNum != benchmark)
			{
				cout << "路径上黑色节点数量不相等" << endl;
				return false;
			}
			else
			{
				return true;
			}
		}
		
		// 验证性质3
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在连续的红色节点" << endl;
			return false;
		}

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

		return PrevCheck(root->_left, blackNum, benchmark)
			&& PrevCheck(root->_right, blackNum, benchmark);
	}
private:
	Node* _root;
};

    • 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

    红黑树相比AVL树不追求绝对的平衡，其只需保证最长路径不超过最短路径的2倍即可，所以相对而言红黑树减少了插入时旋转的次数，在经常需要进行增删的结构中性能比AVL树更优，实际运用中也是红黑树更多。

  • 相关阅读:
    （附源码）ssm高校专升本考试管理系统 毕业设计 201631
    【Python爬虫三天从0到1】Day1：爬虫核心
    【自然语言处理】【向量表示】AugSBERT：改善用于成对句子评分任务的Bi-Encoders的数据增强方法
    快速体验Spring Boot了解使用、运行和打包 | SpringBoot 2.7.2学习系列
    NSS [SWPUCTF 2021 新生赛]PseudoProtocols
    企业使用Windows Sysprep工具来封装Win10、Win11操作系统（全网最新最全）
    数据库技术基础--关系数据库
    2022“杭电杯”中国大学生算法设计超级联赛（3）
    代码随想录 -- 动态规划 -- 不同路径 II
    IDEA抢救10年前WEB项目
  • 原文地址：https://blog.csdn.net/weixin_62172209/article/details/133578970