• C++：AVL树

    目录

    一.AVL树介绍

    1.AVL树的概念

    2.AVL树性质

    平衡因子：左右子树高度之差

    3.为什么设计高度差不超过1？

    4.AVL相比满二叉树:

    5.AVL树图例

    二.模拟实现AVL树

    阶段一：左单旋

    阶段二：右单旋 

    三：左右双旋

    1.先左后右

    2.先右后左 双旋:

    情况1： 

    情况2：

    AVL树总代码：

     

     

    一.AVL树介绍

    1.AVL树的概念

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

    2.AVL树性质

    一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
    它的左右子树都是 AVL 树
    左右子树高度之差 ( 简称平衡因子 ) 的绝对值不超过1(-1/0/1)（即：树中任何一个子树高度差都不超过1）

    078b3e1a5d6f4403b86a91b57297009e.png

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

    平衡因子：左右子树高度之差

    平衡因子不是必须要维护的，在操作时也可以直接通过高度函数来算，只不过比较麻烦

    3.为什么设计高度差不超过1？

    只有满二叉树才能保证每个子树高度差是0（2^h-1）
    做不到相等，退而求其次，左右高度差不超过1

    4.AVL相比满二叉树:

    完全二叉树:最后一层缺一些节点
    AVL二叉树:最后两层缺一些节点

    5.AVL树图例

    8d1598ea5d474046aaafe711526b9e4f.png

    二.模拟实现AVL树

    c20c271fa8a74704b335d973ef557f33.png

    阶段一：左单旋

    右边高--左旋转
    旋转原则:
    1、保持搜索树的规则
    2、子树变平衡

    左单旋的条件：(30)parent->_bf = 2，(60)subR->_bf = 1   （_bf是平衡因子，subR是parent的右孩子）

    左单旋规则：对30进行左单旋，60必须是30的右支，父亲30是儿子60的左支就是左旋，右支就是右旋（如果在b下加子节点 就等价 先右后左双旋的情况2了，图在下面）

    左单旋：（右边高）在c下插入一个节点时，把b给根30右节点，再把30给60的左节点。

     

    27854139de3b43b4a8c52d6a87b21c0a.png

     

    30这棵树可能是局部的子树，上面还有根节点ppNode，更新完30开始的这颗子树的平衡因子后不必再向上更新，因为30为根的这个树旋转前高度是h+2(30,60,h)，旋转后高度还是h+2 没变

    7186070b04e94ac79bd7a4afcb83f1e3.png
    0e964a0620634840af80b9d0e94212af.png

    （如果在b下加子节点 就等价 先右后左双旋的情况2了）

    dbed78404e534eb4b4d072042b95b9ae.png

     

     20f934a46ed34ffeafbcdf9da2e5e19a.png

     

     

     

    1. #pragma once
    2.  
    3. template<class K, class V>
    4. struct AVLTreeNode
    5. {
    6. 	pair _kv;
    7. 	AVLTreeNode* _left;
    8. 	AVLTreeNode* _right;
    9. 	AVLTreeNode* _parent;
    10.  
    11. 	// 右子树-左子树的高度差
    12. 	int _bf;  // balance factor
    13.  
    14. 	AVLTreeNode(const pair& kv)
    15. 		:_kv(kv)
    16. 		, _left(nullptr)
    17. 		, _right(nullptr)
    18. 		, _parent(nullptr)
    19. 		, _bf(0)
    20. 	{}
    21.  
    22. 	// AVL树并没有规定必须要设计平衡因子
    23. 	// 只是一个实现的选择，方便控制平衡
    24. };
    25.  
    26. template<class K, class V>
    27. class AVLTree
    28. {
    29. 	typedef AVLTreeNode Node;
    30. public:
    31. 	bool Insert(const pair& kv)
    32. 	{
    33. 		// 1、搜索树的规则插入
    34. 		// 2、看是否违反平衡规则，如果违反就需要处理：旋转
    35. 		if (_root == nullptr)
    36. 		{
    37. 			_root = new Node(kv);
    38. 			_root->_bf = 0;
    39. 			return true;
    40. 		}
    41.  
    42. 		Node* parent = nullptr;
    43. 		Node* cur = _root;
    44. 		while (cur)
    45. 		{
    46. 			if (cur->_kv.first < kv.first)
    47. 			{
    48. 				parent = cur;
    49. 				cur = cur->_right;
    50. 			}
    51. 			else if (cur->_kv.first > kv.first)
    52. 			{
    53. 				parent = cur;
    54. 				cur = cur->_left;
    55. 			}
    56. 			else
    57. 			{
    58. 				return false;
    59. 			}
    60. 		}
    61.  
    62. 		cur = new Node(kv);
    63. 		if (parent->_kv.first < kv.first)
    64. 		{
    65. 			parent->_right = cur;
    66. 		}
    67. 		else
    68. 		{
    69. 			parent->_left = cur;
    70. 		}
    71.  
    72. 		cur->_parent = parent;
    73.  
    74. 		// ...
    75. 		// 更新平衡因子
    76. 		while (parent) // 最远要更新根
    77. 		{
    78. 			if (cur == parent->_right)
    79. 			{
    80. 				parent->_bf++;
    81. 			}
    82. 			else
    83. 			{
    84. 				parent->_bf--;
    85. 			}
    86.  
    87. 			// 是否继续更新？
    88. 			if (parent->_bf == 0)  // 1 or -1  -》 0  插入节点填上矮的那边
    89. 			{
    90. 				// 高度不变，更新结束
    91. 				break;
    92. 			}
    93. 			else if (parent->_bf == 1 || parent->_bf == -1)
    94. 				// 0  -》 1 或 -1  插入节点导致一边变高了
    95. 			{
    96. 				// 子树的高度变了，继续更新祖先
    97. 				cur = cur->_parent;
    98. 				parent = parent->_parent;
    99. 			}
    100. 			else if (parent->_bf == 2 || parent->_bf == -2)
    101. 				// -1 or 1  -》 2 或 -2  插入节点导致本来高一边又变高了
    102. 			{
    103. 				// 子树不平衡 -- 需要旋转处理
    104. 				// ...
    105. 			}
    106. 			else
    107. 			{
    108. 				// 插入之前AVL就存在不平衡子树，|平衡因子| >= 2的节点
    109. 				assert(false);
    110. 			}
    111. 		}
    112.  
    113. 		return true;
    114. 	}
    115. private:
    116. 	void RotateL(Node* parent)
    117. 	{
    118. 		Node* subR = parent->_right;
    119. 		Node* subRL = subR->_left;
    120.  
    121. 		parent->_right = subRL;
    122. 		if (subRL)
    123. 			subRL->_parent = parent;
    124.  
    125. 		Node* ppNode = parent->_parent;
    126.  
    127. 		subR->_left = parent;
    128. 		parent->_parent = subR;
    129.  
    130. 		if (parent == _root)
    131. 		{
    132. 			_root = subR;
    133. 			_root->_parent = nullptr;
    134. 		}
    135. 		else
    136. 		{
    137. 			if (parent == ppNode->_left)
    138. 			{
    139. 				ppNode->_left = subR;
    140. 			}
    141. 			else
    142. 			{
    143. 				ppNode->_right = subR;
    144. 			}
    145.  
    146. 			subR->_parent = ppNode;
    147. 		}
    148. 	}
    149.  
    150. private:
    151. 	Node* _root = nullptr;
    152. };
    153.  
    154. void TestAVLTree()
    155. {
    156. 	AVLTree<int, int> t;
    157. 	t.Insert(make_pair(1, 1));
    158. 	t.Insert(make_pair(2, 2));
    159. 	t.Insert(make_pair(3, 3));
    160. }

    阶段二：右单旋 

    右单旋的条件：(60)parent->_bf = -2，(60)subL->_bf = -1

    动的就是parent 60，subL 30，subLR b

    c39add27f71649219e7de83aafcda7b3.png

     

    示例：

     

    代码：

    1. void RotateR(Node* parent)
    2. 	{
    3. 		Node* subL = parent->_left;
    4. 		Node* subLR = subL->_right;
    5.  
    6. 		parent->_left = subLR;
    7. 		if (subLR)
    8. 			subLR->_parent = parent;
    9.  
    10. 		Node* ppNode = parent->_parent;
    11.  
    12. 		subL->_right = parent;
    13. 		parent->_parent = subL;
    14.  
    15. 		if (parent == _root)
    16. 		{
    17. 			_root = subL;
    18. 			_root->_parent = nullptr;
    19. 		}
    20. 		else
    21. 		{
    22. 			if (ppNode->_left == parent)
    23. 			{
    24. 				ppNode->_left = subL;
    25. 			}
    26. 			else
    27. 			{
    28. 				ppNode->_right = subL;
    29. 			}
    30. 			subL->_parent = ppNode;
    31. 		}
    32.  
    33. 		subL->_bf = parent->_bf = 0;	
    34. 	}

    三：左右双旋

    1.先左后右

    AVL树的双旋转使用对应的单旋转后还要更新平衡因子

    先左后右双旋的条件：parent->_bf = -2，subL->_bf = 1，不用管subLR是几

    树 h>=1

    相当于是把60的左给30的右，把60的右给90的左，30,90作左右子树，60再做根节点

    90f6a1457b7849bca243f60a922b0027.png

     

    h==0，先左后右 双旋最简单的情况

    66dcaff4d6e84b8cb94d9694273ec385.png

     

     

    361d290a99124248a77039ffafbdfa3d.png

     

    2.先右后左 双旋:

    先右后左双旋的条件：parent->_bf = 2，subR->_bf = -1，不用管subRL是几

    情况1： 

    f60f3f0b18514e119c8ffb3aa8ab6747.png

    情况2：

    a16b942b0d99417683d36fa1953cb72b.png

     

     

    AVL树总代码：

    1. #pragma once
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6.  
    7. template<class K, class V>
    8. struct AVLTreeNode
    9. {
    10. 	pair _kv;
    11. 	AVLTreeNode* _left;
    12. 	AVLTreeNode* _right;
    13. 	AVLTreeNode* _parent;
    14.  
    15. 	// 右子树-左子树的高度差
    16. 	int _bf;  // balance factor
    17.  
    18. 	AVLTreeNode(const pair& kv)
    19. 		:_kv(kv)
    20. 		, _left(nullptr)
    21. 		, _right(nullptr)
    22. 		, _parent(nullptr)
    23. 		, _bf(0)
    24. 	{}
    25.  
    26. 	// AVL树并没有规定必须要设计平衡因子
    27. 	// 只是一个实现的选择，方便控制平衡
    28. };
    29.  
    30. template<class K, class V>
    31. class AVLTree
    32. {
    33. 	typedef AVLTreeNode Node;
    34. public:
    35. 	// Find
    36. 	// Erase
    37. 	bool Insert(const pair& kv)
    38. 	{
    39. 		// 1、搜索树的规则插入
    40. 		// 2、看是否违反平衡规则，如果违反就需要处理：旋转
    41. 		if (_root == nullptr)
    42. 		{
    43. 			_root = new Node(kv);
    44. 			_root->_bf = 0;
    45. 			return true;
    46. 		}
    47.  
    48. 		Node* parent = nullptr;
    49. 		Node* cur = _root;
    50. 		while (cur)
    51. 		{
    52. 			if (cur->_kv.first < kv.first)
    53. 			{
    54. 				parent = cur;
    55. 				cur = cur->_right;
    56. 			}
    57. 			else if (cur->_kv.first > kv.first)
    58. 			{
    59. 				parent = cur;
    60. 				cur = cur->_left;
    61. 			}
    62. 			else
    63. 			{
    64. 				return false;
    65. 			}
    66. 		}
    67.  
    68. 		cur = new Node(kv);
    69. 		if (parent->_kv.first < kv.first)
    70. 		{
    71. 			parent->_right = cur;
    72. 		}
    73. 		else
    74. 		{
    75. 			parent->_left = cur;
    76. 		}
    77.  
    78. 		cur->_parent = parent;
    79.  
    80. 		// ...
    81. 		// 更新平衡因子
    82. 		while (parent) // 最远要更新根
    83. 		{
    84. 			if (cur == parent->_right)
    85. 			{
    86. 				parent->_bf++;
    87. 			}
    88. 			else
    89. 			{
    90. 				parent->_bf--;
    91. 			}
    92.  
    93. 			// 是否继续更新？
    94. 			if (parent->_bf == 0)  // 1 or -1  -》 0  插入节点填上矮的那边
    95. 			{
    96. 				// 高度不变，更新结束
    97. 				break;
    98. 			}
    99. 			else if (parent->_bf == 1 || parent->_bf == -1)
    100. 				// 0  -》 1 或 -1  插入节点导致一边变高了
    101. 			{
    102. 				// 子树的高度变了，继续更新祖先
    103. 				cur = cur->_parent;
    104. 				parent = parent->_parent;
    105. 			}
    106. 			else if (parent->_bf == 2 || parent->_bf == -2)
    107. 				// -1 or 1  -》 2 或 -2  插入节点导致本来高一边又变高了
    108. 			{
    109. 				// 子树不平衡 -- 需要旋转处理
    110. 				if (parent->_bf == 2 && cur->_bf == 1) // 左单旋
    111. 				{
    112. 					RotateL(parent);
    113. 				}
    114. 				else if (parent->_bf == -2 && cur->_bf == -1) // 右单旋
    115. 				{
    116. 					RotateR(parent);
    117. 				}
    118. 				else if (parent->_bf == -2 && cur->_bf == 1) // 左右双旋
    119. 				{
    120. 					RotateLR(parent);
    121. 				}
    122. 				else if (parent->_bf == 2 && cur->_bf == -1) // 右左双旋
    123. 				{
    124. 					RotateRL(parent);
    125. 				}
    126. 				
    127. 				break;
    128. 			}
    129. 			else
    130. 			{
    131. 				// 插入之前AVL就存在不平衡子树，|平衡因子| >= 2的节点
    132. 				assert(false);
    133. 			}
    134. 		}
    135.  
    136. 		return true;
    137. 	}
    138. private:
    139. 	void RotateL(Node* parent)
    140. 	{
    141. 		Node* subR = parent->_right;
    142. 		Node* subRL = subR->_left;
    143.  
    144. 		parent->_right = subRL;
    145. 		if (subRL)
    146. 			subRL->_parent = parent;
    147.  
    148. 		Node* ppNode = parent->_parent;
    149.  
    150. 		subR->_left = parent;
    151. 		parent->_parent = subR;
    152.  
    153. 		if (parent == _root)
    154. 		{
    155. 			_root = subR;
    156. 			_root->_parent = nullptr;
    157. 		}
    158. 		else
    159. 		{
    160. 			if (parent == ppNode->_left)
    161. 			{
    162. 				ppNode->_left = subR;
    163. 			}
    164. 			else
    165. 			{
    166. 				ppNode->_right = subR;
    167. 			}
    168.  
    169. 			subR->_parent = ppNode;
    170. 		}
    171.  
    172. 		// 更新平衡因子
    173. 		parent->_bf = 0;
    174. 		subR->_bf = 0;
    175. 	}
    176.  
    177. 	void RotateR(Node* parent)
    178. 	{
    179. 		Node* subL = parent->_left;
    180. 		Node* subLR = subL->_right;
    181.  
    182. 		parent->_left = subLR;
    183. 		if (subLR)
    184. 			subLR->_parent = parent;
    185.  
    186. 		Node* ppNode = parent->_parent;
    187.  
    188. 		subL->_right = parent;
    189. 		parent->_parent = subL;
    190.  
    191. 		if (parent == _root)
    192. 		{
    193. 			_root = subL;
    194. 			_root->_parent = nullptr;
    195. 		}
    196. 		else
    197. 		{
    198. 			if (ppNode->_left == parent)
    199. 			{
    200. 				ppNode->_left = subL;
    201. 			}
    202. 			else
    203. 			{
    204. 				ppNode->_right = subL;
    205. 			}
    206. 			subL->_parent = ppNode;
    207. 		}
    208.  
    209. 		subL->_bf = parent->_bf = 0;	
    210. 	}
    211.  
    212. 	void RotateLR(Node* parent)
    213. 	{
    214. 		Node* subL = parent->_left;
    215. 		Node* subLR = subL->_right;
    216. 		int bf = subLR->_bf;
    217. 			
    218. 		RotateL(parent->_left);
    219. 		RotateR(parent);
    220.  
    221. 		// 更新平衡因子
    222. 		if(bf == 0)
    223. 		{
    224. 			parent->_bf = 0;
    225. 			subL->_bf = 0;
    226. 			subLR->_bf = 0;
    227. 		}
    228. 		else if (bf == 1)
    229. 		{
    230. 			parent->_bf = 0;
    231. 			subL->_bf = -1;
    232. 			subLR->_bf = 0;
    233. 		}
    234. 		else if (bf == -1)
    235. 		{
    236. 			parent->_bf = 1;
    237. 			subL->_bf = 0;
    238. 			subLR->_bf = 0;
    239. 		}
    240. 		else
    241. 		{
    242. 			// subLR->_bf旋转前就有问题
    243. 			assert(false);
    244. 		}
    245. 	}
    246.  
    247. 	void RotateRL(Node* parent)
    248. 	{
    249. 		Node* subR = parent->_right;
    250. 		Node* subRL = subR->_left;
    251. 		int bf = subRL->_bf;
    252.  
    253. 		RotateR(parent->_right);
    254. 		RotateL(parent);
    255.  
    256. 		if (bf == 0)
    257. 		{
    258. 			subRL->_bf = 0;
    259. 			parent->_bf = 0;
    260. 			subR->_bf = 0;
    261. 		}
    262. 		else if (bf == 1)
    263. 		{
    264. 			subRL->_bf = 0;
    265. 			parent->_bf = -1;
    266. 			subR->_bf = 0;
    267. 		}
    268. 		else if (bf == -1)
    269. 		{
    270. 			subRL->_bf = 0;
    271. 			parent->_bf = 0;
    272. 			subR->_bf = 1;
    273. 		}
    274. 		else
    275. 		{
    276. 			// subLR->_bf旋转前就有问题
    277. 			assert(false);
    278. 		}
    279. 	}
    280.  
    281. 	void _InOrder(Node* root)
    282. 	{
    283. 		if (root == nullptr)
    284. 			return;
    285.  
    286. 		_InOrder(root->_left);
    287. 		cout << root->_kv.first <<" ";
    288. 		_InOrder(root->_right);
    289. 	}
    290.  
    291. 	int _Height(Node* root)
    292. 	{
    293. 		if (root == nullptr)
    294. 			return 0;
    295.  
    296. 		int lh = _Height(root->_left);
    297. 		int rh = _Height(root->_right);
    298.  
    299. 		return lh > rh ? lh + 1 : rh + 1;
    300. 	}
    301.  
    302. 	bool _IsBalanceTree(Node* root)
    303. 	{
    304. 		// 空树也是AVL树
    305. 		if (nullptr == root)
    306. 			return true;
    307.  
    308. 		// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
    309. 		int leftHeight = _Height(root->_left);
    310. 		int rightHeight = _Height(root->_right);
    311. 		int diff = rightHeight - leftHeight;
    312.  
    313. 		// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
    314. 		// pRoot平衡因子的绝对值超过1，则一定不是AVL树
    315. 		if (abs(diff) >= 2)
    316. 		{
    317. 			cout << root->_kv.first << "节点平衡因子异常" << endl;
    318. 			return false;
    319. 		}
    320.  
    321. 		if (diff != root->_bf)
    322. 		{
    323. 			cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
    324. 			return false;
    325. 		}
    326.  
    327. 		// pRoot的左和右如果都是AVL树，则该树一定是AVL树
    328. 		return _IsBalanceTree(root->_left)
    329. 			&& _IsBalanceTree(root->_right);
    330. 	}
    331.  
    332. public:
    333.  
    334. 	void InOrder()
    335. 	{
    336. 		_InOrder(_root);
    337. 		cout << endl;
    338. 	}
    339.  
    340. 	vectorint>> levelOrder() {
    341. 		vectorint>> vv;
    342. 		if (_root == nullptr)
    343. 			return vv;
    344.  
    345. 		queue q;
    346. 		int levelSize = 1;
    347. 		q.push(_root);
    348.  
    349. 		while (!q.empty())
    350. 		{
    351. 			// levelSize控制一层一层出
    352. 			vector<int> levelV;
    353. 			while (levelSize--)
    354. 			{
    355. 				Node* front = q.front();
    356. 				q.pop();
    357. 				levelV.push_back(front->_kv.first);
    358. 				if (front->_left)
    359. 					q.push(front->_left);
    360.  
    361. 				if (front->_right)
    362. 					q.push(front->_right);
    363. 			}
    364. 			vv.push_back(levelV);
    365. 			for (auto e : levelV)
    366. 			{
    367. 				cout << e << " ";
    368. 			}
    369. 			cout << endl;
    370.  
    371. 			// 上一层出完，下一层就都进队列
    372. 			levelSize = q.size();
    373. 		}
    374.  
    375. 		return vv;
    376. 	}
    377.  
    378. 	bool IsBalanceTree()
    379. 	{
    380. 		return _IsBalanceTree(_root);
    381. 	}
    382.  
    383. 	int Height()
    384. 	{
    385. 		return _Height(_root);
    386. 	}
    387. private:
    388. 	Node* _root = nullptr;
    389. };
    390.  
    391. void TestAVLTree1()
    392. {
    393. 	//int a[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
    394. 	int a[] = { 30,29,28,27,26,25,24,11,8,7,6,5,4,3,2,1 };
    395. 	AVLTree<int, int> t;
    396. 	for (auto e : a)
    397. 	{
    398. 		t.Insert(make_pair(e, e));
    399. 	}
    400. 	t.levelOrder();
    401. }
    402.  
    403. void TestAVLTree2()
    404. {
    405. 	const size_t N = 1024*1024*10;
    406. 	vector<int> v;
    407. 	v.reserve(N);
    408. 	srand(time(0));
    409. 	for (size_t i = 0; i < N; ++i)
    410. 	{
    411. 		//v.push_back(rand());
    412. 		v.push_back(i);
    413. 	}
    414.  
    415. 	AVLTree<int, int> t;
    416. 	for (auto e : v)
    417. 	{
    418. 		t.Insert(make_pair(e, e));
    419. 	}
    420.  
    421. 	//t.levelOrder();
    422. 	//cout << endl;
    423. 	cout << "是否平衡?" << t.IsBalanceTree() << endl;
    424. 	cout << "高度:" << t.Height() << endl;
    425.  
    426.  
    427. 	//t.InOrder();
    428. }

     

     

     

     

  • 相关阅读:
    Java 字符流案例_集合与文件内容的相互转化(升级版)
    软件测试学习路线
    【计算机网络微课堂】5.8 TCP的运输连接管理
    常见的ssh功能
    为什么资源管理对现代企业很重要?
    【MySQL基础】MySQL常用的图形化管理工具有那些？
    微信小程序 原生开发 实现弹窗遮罩层 并且在遮罩层内使用scroll-view实现滚动内容（包括图片）
    掌握 Git：代码版本控制的基本步骤（强力推荐的工具）
    Python教程之字典(Dictionary)操作详解
    有哪些不起眼却赚钱的行业？
  • 原文地址：https://blog.csdn.net/zhang_si_hang/article/details/126419169