• 浅谈AVL树

    文章目录


    在这里插入图片描述

    1.介绍

    1.1定义

    AVL树 – 平衡二叉树 – 平衡二叉搜索（排序）树 – 高度平衡搜索树
    Balanced Binary Tree （BBT）

    1.2来源

    AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
    二叉搜索树可以缩短查找的效率，但在数据有序或接近有序时它将退化为单支树，查找元素相当于在顺序表中搜索，效率低下。两位俄罗斯的数学家发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

    1.3概念

    1.特性

    • 一棵空树或左右两个子树高度差绝对值不超过1
    • 左右两个子树也都是一棵高度平衡搜索树

    2.平衡因子[ Balance Factor-- _bf ]

    1. 结点的平衡因子 == 右子树高度 - 左子树高度
    2. | _bf | <= 1
    3. AVL树不一定有平衡因子, 使用平衡因子只是一种较为简单的实现方式
      在这里插入图片描述

    2.BST==>AVL

    [设定 _bf = 右子树高度 - 左子树高度]

    1.示例分析

    先看一下下面的图 了解一下什么叫做旋转 以及旋转的目的

    在这里插入图片描述
    在这里插入图片描述

    2.情况分类

    在这里插入图片描述

    3.代码剖析

    3.1左左型-右单旋

    在这里插入图片描述

    	void RotateRight(Node* dad)
	{
		Node* Grandpa = dad->_parent;
		Node* sonL = dad->_left;
		Node* sonLR = sonL->_right;

		//dad连接sonLR sonLR不空-继承dad 为空不继承
		dad->_left = sonLR;
		if (sonLR)
			sonLR->_parent = dad;
        //sonL连接dad dad继承sonL
		sonL->_right = dad;
		dad->_parent = sonL;
		//G为空 表明dad为根结点 
		if (Grandpa == nullptr)
		{
			//更新根结点
			_root = sonL;
			//更新根结点成员属性
			_root->_parent = nullptr;
		}
		else
		{
			//父连子
			if (Grandpa->_left == dad)
				Grandpa->_left = sonL;
			else
				Grandpa->_right = sonL;
			//子继承父
			sonL->_parent = Grandpa;
		}
		//更新_bf
		sonL->_bf = dad->_bf = 0;
	}

    • 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

    3.2右右型-左单旋

    在这里插入图片描述

    void RotateLeft(Node* dad)
{
	Node* Grandpa = dad->_parent;
	Node* sonR = dad->_right;
	Node* sonRL = sonR->_left;

	//dad连接sonRL sonRL不空继承dad 为空不继承
	dad->_right = sonRL;
	if (sonRL)
		sonRL->_parent = dad;
	//sonR连接dad dad继承sonR
	sonR->_left = dad;
	dad->_parent = sonR;
	//Grandpa为空--dad为根节点 更新后 sonR为根节点 根节点的_parent置空
	if (Grandpa == nullptr)
	{
		_root = sonR;
		_root->_parent = nullptr;
	}
	//不为空 依实际连接
	else
	{
		//父连子
		if (Grandpa->_left == dad)
			Grandpa->_left = sonR;
		else
			Grandpa->_right = sonR;
		//子继承父
		sonR->_parent = Grandpa;
	}
	//左旋目的达到 更新_bf
	dad->_bf = sonR->_bf = 0;
}

    • 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

    3.3左右型-左右旋

    在这里插入图片描述
    在这里插入图片描述

    void RotateLR(Node* dad)
{
	Node* sonL = dad->_left;
	Node* sonLR = sonL->_right;
	int bf = sonLR->_bf;

	RotateLeft(sonL);
	RotateRight(dad);

	if (bf == 1)
	{
		sonLR->_bf = 0;
		sonL->_bf = -1;
		dad->_bf = 0;
	}
	else if (bf == -1)
	{
		sonLR->_bf = 0;
		sonL->_bf = 0;
		dad->_bf = 1;
	}
	else if (bf == 0)
	{
		sonLR->_bf = 0;
		sonL->_bf = 0;
		dad->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

    • 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

    3.4右左型:右左旋

    在这里插入图片描述
    在这里插入图片描述

    void RotateRL(Node* dad)
{
	Node* sonR = dad->_right;
	Node* sonRL = sonR->_left;
	int bf = sonRL->_bf;//最终根结点的_bf

	RotateLeft(dad->_right);
	RotateRight(dad);

	if (bf == 1)
	{
		sonRL->_bf = 0;
		dad->_bf = -1;
		sonR->_bf = 0;
	}
	else if (bf == -1)
	{
		sonRL->_bf = 0;
		dad->_bf = 0;
		sonR->_bf = 1;
	}
	else if (bf == 0)
	{
		sonRL->_bf = 0;
		dad->_bf = 0;
		sonR->_bf = 0;1
	}
	else
	{
		assert(false);
	}
}

    • 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

    3.5总图

    在这里插入图片描述

    3.完整代码

    3.1AVLTree.h

    #pragma once
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _pair;
	int _bf;           // balance factor

	AVLTreeNode(const pair<K, V>& pair)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _pair(pair)
		, _bf(0)
	{

	}
};

//高度平衡搜索树
template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:

	//插入--创建二叉树
	bool Insert(const pair<K, V>& pair)
	{
		//空树--new结点
		if (_root == nullptr)
		{
			_root = new Node(pair);
			return true;
		}

		//非空--插入
		//1.定位到合适位置
		Node* parent = nullptr;
		Node* cp = _root;
		while (cp)
		{
			if (pair.first > cp->_pair.first)
			{
				parent = cp;
				cp = cp->_right;
			}
			else if (pair.first < cp->_pair.first)
			{
				parent = cp;
				cp = cp->_left;
			}
			else
			{
				//搜索树不可有数据重复 -- 插入失败
				return false;
			}
		}

		//2.链接
		cp = new Node(pair);
		if (pair.first < parent->_pair.first)
		{
			parent->_left = cp;
		}
		else
		{
			parent->_right = cp;
		}
		//cp继承parent
		cp->_parent = parent;

		//构建AVL树
		while (parent)
		{
			//一、更新平衡因子

			//插入结点在右子树
			if (cp == parent->_right)
			{
				parent->_bf++;
			}
			//插入结点在左子树
			else
			{
				parent->_bf--;
			}

			//二、分类讨论

			// _bf == 1/-1 原为0 现高度受到影响
			// 回溯直至遇到根源结点 即_bf==2/-2的结点
			if (parent->_bf == 1 || parent->_bf == -1)
			{
				parent = parent->_parent;
				cp = cp->_parent;
			}
			//_bf == 0 不做处理 原为-1/1 现已满足 不继续更新
			else if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//旋转处理目的:
				//1.使得当前子树平衡 2.降低当前子树的高度

				//左单旋
				if (parent->_bf == 2 && cp->_bf == 1)
				{
					RotateL(parent);
				}
				//右单旋
				else if (parent->_bf == -2 && cp->_bf == -1)
				{
					RotateR(parent);
				}
				//左右旋
				else if (parent->_bf == -2 && cp->_bf == 1)
				{
					RotateLR(parent);
				}
				//右左旋
				else if (parent->_bf == 2 && cp->_bf == -1)
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}

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

		return true;
	}

	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	//高度接口
	int Height()
	{
		return _Height(_root);
	}

	//判断是否满足AVL树平衡
	bool IsBalance()
	{
		return _IsBalance(_root);
	}

private:

	// 中序遍历
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

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

	//高度接口
	int _Height(Node* root)
	{
		if (root == NULL)
			return 0;

		int leftH = _Height(root->_left);
		int rightH = _Height(root->_right);

		return leftH > rightH ? leftH + 1 : rightH + 1;
	}

	//判断是否满足AVL树平衡
	bool _IsBalance(Node* root)
	{
		if (root == NULL)
		{
			return true;
		}

		int leftH = _Height(root->_left);
		int rightH = _Height(root->_right);

		if (rightH - leftH != root->_bf)
		{
			cout << root->_pair.first << "Abnormal node balance factor!" << endl;
			return false;
		}

		return abs(leftH - rightH) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

	//左单旋
	void RotateL(Node* parent)
	{
		//记录Grandpa
		Node* Grandpa = parent->_parent;

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

		//parent链接subRL subRL不空继承parent 空没必要继承
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		//subR连接parent parent继承subR
		subR->_left = parent;
		parent->_parent = subR;

		//Grandpa为空--parent为根节点 更新后 subR为根节点 根节点的_parent置空
		if (Grandpa == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		//不为空 依实际连接
		else
		{
			//父连子
			if (Grandpa->_left == parent)
			{
				Grandpa->_left = subR;
			}
			else
			{
				Grandpa->_right = subR;
			}
			//子继承父
			subR->_parent = Grandpa;
		}

		parent->_bf = subR->_bf = 0;
	}

	//右单旋
	void RotateR(Node* parent)
	{
		Node* Grandpa = 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 (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (Grandpa->_left == parent)
			{
				Grandpa->_left = subL;
			}
			else
			{
				Grandpa->_right = subL;
			}
			subL->_parent = Grandpa;
		}

		subL->_bf = parent->_bf = 0;
	}

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

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

		if (bf == 1)
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subL->_bf = -1;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subLR->_bf = 0;
			subL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subLR->_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);

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


private:
	Node* _root = nullptr;
};

void Test_AVLTree1()
{
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int b[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTree<int, int> tree;
	for (auto e : b)
	{
		tree.Insert(make_pair(e, e));
		if (tree.IsBalance())
		{
			cout << e << "插入成功!" << endl;
		}
		else
		{
			cout << e << "插入失败!" << endl;
		}
	}

	cout << "此树中序遍历:" << endl;
	tree.InOrder();

	if (tree.IsBalance())
	{
		cout << "此树为一棵AVL树" << endl;
	}
	else
	{
		cout << "此树不为一棵AVL树!" << endl;
	}
}

void Test_AVLTree2()
{
	srand(time(0));
	const size_t N = 10;
	AVLTree<int, int> tree;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand() + i;
		tree.Insert(make_pair(x, x));
		if (tree.IsBalance())
		{
			cout << x << "插入成功!" << endl;
		}
		else
		{
			cout << x << "插入失败!" << endl;
		}
	}

	cout << "此树中序遍历:" << endl;
	tree.InOrder();

	if (tree.IsBalance())
	{
		cout << "此树为一棵AVL树" << endl;
	}
	else
	{
		cout << "此树不为一棵AVL树!" << endl;
	}

	cout << "此树高度为:" << tree.Height() << endl;
}


    • 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
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375
    • 376
    • 377
    • 378
    • 379
    • 380
    • 381
    • 382
    • 383
    • 384
    • 385
    • 386
    • 387
    • 388
    • 389
    • 390
    • 391
    • 392
    • 393
    • 394
    • 395
    • 396
    • 397
    • 398
    • 399
    • 400
    • 401
    • 402
    • 403
    • 404
    • 405
    • 406
    • 407
    • 408
    • 409
    • 410
    • 411
    • 412
    • 413
    • 414
    • 415
    • 416
    • 417
    • 418
    • 419
    • 420
    • 421
    • 422
    • 423
    • 424
    • 425
    • 426
    • 427
    • 428
    • 429
    • 430
    • 431
    • 432
    • 433
    • 434
    • 435
    • 436
    • 437
    • 438
    • 439
    • 440
    • 441
    • 442
    • 443

    3.2Test.cpp

    #define _CRT_SECURE_NO_WARNINGS 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#include "AVLTree.h"

int main()
{
	Test_AVLTree1();
	return 0;
}

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

    4.AVL树的性能

    1. AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1.保证查找时间复杂度为logN。
    2. 创建一棵AVL树成本太大:插入时要维护其绝对平衡，旋转的次数比较多，删除时有可能要一直旋转直到根的位置。
    3. 如果需要一种查询高效且有序的数据结构，且数据的个数为不改变，可以考虑AVL树
    4. AVL树不适合需要经常修改结构的
  • 相关阅读:
    5-4 jmu-报数游戏 (15分)
    linux安全--DNS服务部署
    分布式--OpenResty+lua+Redis实现限流与防爬虫
    JS排序算法
    贪心算法归纳
    双点重发布+路由策略实验
    “Redis与Spring整合及缓存优化“
    EPICS base macLib库解析与测试
    嵌入式简介
    【改进和增强Microsoft Office应用程序】ExtendOffice软件产品介绍
  • 原文地址：https://blog.csdn.net/LHRan_ran_/article/details/133249554