• 数据结构 - 平衡二叉树（AVL树）概念 | 插入与平衡调整

    目录

     

    前言 

    AVL树的概念

    AVL树结点的定义

    AVL树的插入

    AVL树的平衡调整（重点）

    LL型不平衡（需右单旋转)

    RR型不平衡（需左单旋转)

    LR型不平衡（需左右双旋转)

    RL型不平衡（需右左双旋转)

    AVL树简单实现以及验证-插入

     完整代码实现：

    前言 

    前面对 map/multimap/set/multiset 进行了简单的介绍，在其文档介绍中发现，这几个容器有个
    共同点是： 其底层都是按照二叉搜索树来实现的 ，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N) ，因此map、 set 等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

    AVL树的概念

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

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

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

    如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在

    O(log2_ n)，搜索时间复杂度O(log2_ n)。

    AVL树结点的定义

    我们这里直接实现KV模型的AVL树，为了方便后续的操作，这里将AVL树中的结点定义为三叉链结构，并在每个结点当中引入平衡因子（右子树高度-左子树高度）。除此之外，还需编写一个构造新结点的构造函数，由于新构造结点的左右子树均为空树，于是将新构造结点的平衡因子初始设置为0即可。

    1. template<class T>
    2. struct AVLTreeNode
    3. {
    4. 	AVLTreeNode(const T& data)
    5. 		: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
    6. 		, _data(data), _bf(0)
    7. 	{}
    8. 	AVLTreeNode* _pLeft;   // 该节点的左孩子
    9. 	AVLTreeNode* _pRight;  // 该节点的右孩子
    10. 	AVLTreeNode* _pParent; // 该节点的双亲
    11. 	T _data;
    12. 	int _bf;                  // 该节点的平衡因子
    13. };

    注意： 

    • 给每个结点增加平衡因子并不是必须的，只是实现AVL树的一种方式，不引入平衡因子也可以实现AVL树，只不过会麻烦一点 
    • 树中最大元素一定是无左子树，因为最大元素如果存在左子树，中序遍历就不可能是降序序列
    • 插入时，AVL树最多只需要旋转两次

    AVL树的插入

    AVL树插入结点时有以下三个步骤：

    1. 按照二叉搜索树的插入方法，找到待插入位置。
    2. 找到待插入位置后，将待插入结点插入到树中。
    3. 更新平衡因子，如果出现不平衡，则需要进行旋转。

    因为AVL树本身就是一棵二叉搜索树，因此寻找结点的插入位置是非常简单的，按照二叉搜索树的插入规则：

    1. 待插入结点的key值比当前结点小就插入到该结点的左子树。
    2. 待插入结点的key值比当前结点大就插入到该结点的右子树。
    3. 待插入结点的key值与当前结点的key值相等就插入失败。

    如此进行下去，直到找到与待插入结点的key值相同的结点判定为插入失败，或者最终走到空树位置进行结点插入。

    AVL树的平衡调整（重点）

    向AVL树中插入新数据

    • 和BST一样，首先在叶节点插入数据
    • 若插入导致不平衡，则需对以插入路径上离插入节点最近的平衡因子绝对值大于1的节点为根的树进行调整
       

    LL型不平衡（需右单旋转)

    • 在某个子树的左子树的左子树上插入新节点，导致根节点的平衡因子由1变为2

    右单旋的步骤如下：

    1. 让y的右子树作为x的左子树。
    2. 让x作为y的右子树。
    3. 让y作为整个子树的根。
    4. 更新平衡因子。

    右单旋后满足二叉搜索树的性质：

    1. y的右子树当中结点的值本身就比x的值小，因此可以作为x的左子树。
    2. x及其右子树当中结点的值本身就比y的值大，因此可以作为y的右子树。

     右单选代码实现

    1. void RotateR(Node* pParent)
    2. 	{
    3. 		Node* pSubL = pParent->_pLeft;
    4. 		Node* pSubLR = pSubL->_pRight;
    5.  
    6. 		// 改变pParent和pSubL孩子的指向
    7. 		pParent->_pLeft = pSubLR;
    8. 		if (pSubLR)
    9. 			pSubLR->_pParent = pParent;
    10.  
    11. 		pSubL->_pRight = pParent;
    12.  
    13. 		// 更新pParent和pSubL的双亲
    14. 		Node* pPParent = pParent->_pParent;
    15. 		pParent->_pParent = pSubL;
    16. 		pSubL->_pParent = pPParent;
    17.  
    18. 		// 更新原pParent双亲的左||右指针域指向
    19. 		if (nullptr == pPParent)
    20. 		{
    21. 			_pRoot = pSubL;
    22. 		}
    23. 		else
    24. 		{
    25. 			if (pParent == pPParent->_pLeft)
    26. 				pPParent->_pLeft = pSubL;
    27. 			else
    28. 				pPParent->_pRight = pSubL;
    29. 		}
    30.  
    31. 		pParent->_bf = pSubL->_bf = 0;
    32. 	}

    RR型不平衡（需左单旋转)

    • 在某个子树的右子树的右子树上插入新节点，导致根节点的平衡因子由-1变为-2 


    左单旋的步骤如下：

    1. 让y的左子树作为x的右子树。
    2. 让x作为y的左子树。
    3. 让y作为整个子树的根。
    4. 更新平衡因子。

    左单旋后满足二叉搜索树的性质：

    1. y的左子树当中结点的值本身就比x的值大，因此可以作为x的右子树。
    2. x及其左子树当中结点的值本身就比y的值小，因此可以作为y的左子树。

     左单旋代码实现

    1.  
    2. 	void RotateL(Node* pParent)
    3. 	{
    4. 		Node* pSubR = pParent->_pRight;
    5. 		Node* pSubRL = pSubR->_pLeft;
    6.  
    7. 		pParent->_pRight = pSubRL;
    8. 		if (pSubRL)
    9. 			pSubRL->_pParent = pParent;
    10.  
    11. 		pSubR->_pLeft = pParent;
    12. 		Node* pPParent = pParent->_pParent;
    13. 		pParent->_pParent = pSubR;
    14. 		pSubR->_pParent = pPParent;
    15.  
    16. 		if (nullptr == pPParent)
    17. 		{
    18. 			_pRoot = pSubR;
    19. 		}
    20. 		else
    21. 		{
    22. 			if (pParent == pPParent->_pLeft)
    23. 				pPParent->_pLeft = pSubR;
    24. 			else
    25. 				pPParent->_pRight = pSubR;
    26. 		}
    27.  
    28. 		pParent->_bf = pSubR->_bf = 0;
    29. 	}

    LR型不平衡（需左右双旋转)

    • 在某个子树的左子树的右子树上插入新节点，导致根节点的平衡因子由1变为2

    左右双旋的步骤如下：

    1. 以y为旋转点进行左单旋。
    2. 以x为旋转点进行右单旋。
    3. 更新平衡因子。

    左右双旋后满足二叉搜索树的性质：
    左右双旋后，实际上就是让z的左子树和右子树，分别作为y和x的右子树和左子树，再让y和x分别作为z的左右子树，最后让z作为整个子树的根（结合图理解）。

    1. z的左子树当中的结点本身就比y的值大，因此可以作为y的右子树。
    2. z的右子树当中的结点本身就比x的值小，因此可以作为x的左子树。
    3. 经过步骤1/2后，y及其子树当中结点的值都就比z的值小，而x及其子树当中结点的值都就比z的值大，因此它们可以分别作为z的左右子树。

     左右双旋转代码实现

    1. void RotateRL(Node* pParent)
    2. 	{
    3. 		Node* pSubR = pParent->_pRight;
    4. 		Node* pSubRL = pSubR->_pLeft;
    5. 		int bf = pSubRL->_bf;
    6.  
    7. 		RotateR(pParent->_pRight);
    8. 		RotateL(pParent);
    9.  
    10. 		// 更新部分节点的平衡因子
    11. 		if (bf == -1)
    12. 			pSubR->_bf = 1;
    13. 		else if (bf == 1)
    14. 			pParent->_bf = -1;
    15. 	}

    RL型不平衡（需右左双旋转)

    • 在某个子树的右子树的左子树上插入新节点，导致根节点的平衡因子由-1变为-2

    右左双旋的步骤如下：

    1. 以y为旋转点进行右单旋。
    2. 以x为旋转点进行左单旋。
    3. 更新平衡因子。

    右左双旋后满足二叉搜索树的性质：
    右左双旋后，实际上就是让z的左子树和右子树，分别作为x和y的右子树和左子树，再让x和y分别作为x的左右子树，最后让z作为整个子树的根（结合图理解）。

    1. z的左子树当中的结点本身就比x的值大，因此可以作为x的右子树。
    2. z的右子树当中的结点本身就比y的值小，因此可以作为y的左子树。
    3. 经过步骤1/2后，x及其子树当中结点的值都就比z的值小，而y及其子树当中结点的值都就比z的值大，因此它们可以分别作为z的左右子树。

    右左双旋转代码实现

    1. void RotateLR(Node* pParent)
    2. 	{
    3. 		Node* pSubL = pParent->_pLeft;
    4. 		Node* pSubLR = pSubL->_pRight;
    5. 		int bf = pSubLR->_bf;
    6.  
    7. 		RotateL(pParent->_pLeft);
    8. 		RotateR(pParent);
    9. 		if (-1 == bf)
    10. 			pParent->_bf = 1;
    11. 		else if (1 == bf)
    12. 			pSubL->_bf = -1;
    13. 	}

    AVL树简单实现以及验证-插入

    函数接口

    1. template<class T>
    2. struct AVLTreeNode
    3. {
    4. 	AVLTreeNode(const T& data = T())
    5. 	: _pLeft(nullptr)
    6. 	, _pRight(nullptr)
    7. 	, _pParent(nullptr)
    8. 	, _data(data)
    9. 	, _bf(0)
    10. 	{}
    11.  
    12. 	AVLTreeNode* _pLeft;
    13. 	AVLTreeNode* _pRight;
    14. 	AVLTreeNode* _pParent;
    15. 	T _data;
    16. 	int _bf;   // 节点的平衡因子
    17. };
    18.  
    19.  
    20. // AVL: 二叉搜索树 + 平衡因子的限制
    21. template<class T>
    22. class AVLTree
    23. {
    24. 	typedef AVLTreeNode Node;
    25. public:
    26. 	AVLTree()
    27. 		: _pRoot(nullptr)
    28. 	{}
    29.  
    30.     // 在AVL树中插入值为data的节点
    31. 	bool Insert(const T& data);
    32.     
    33.     // AVL树的验证
    34. 	bool IsAVLTree()
    35. 	{
    36. 		return _IsAVLTree(_pRoot);
    37. 	}
    38.  
    39. private:
    40.     // 根据AVL树的概念验证pRoot是否为有效的AVL树
    41. 	bool _IsAVLTree(Node* pRoot);
    42. 	size_t _Height(Node* pRoot);
    43.     // 右单旋
    44. 	void RotateR(Node* pParent);
    45.     // 左单旋
    46. 	void RotateL(Node* pParent);
    47.     // 右左双旋
    48. 	void RotateRL(Node* pParent);
    49.     // 左右双旋
    50. 	void RotateLR(Node* pParent);
    51.  
    52. private:
    53. 	Node* _pRoot;
    54. };

     完整代码实现：

    1. template<class T>
    2. struct AVLTreeNode
    3. {
    4. 	AVLTreeNode(const T& data = T())
    5. 	: _pLeft(nullptr)
    6. 	, _pRight(nullptr)
    7. 	, _pParent(nullptr)
    8. 	, _data(data)
    9. 	, _bf(0)
    10. 	{}
    11.  
    12. 	AVLTreeNode* _pLeft;
    13. 	AVLTreeNode* _pRight;
    14. 	AVLTreeNode* _pParent;
    15. 	T _data;
    16. 	int _bf;   // 节点的平衡因子
    17. };
    18.  
    19.  
    20.  
    21. // AVL: 二叉搜索树 + 平衡因子的限制
    22. template<class T>
    23. class AVLTree
    24. {
    25. 	typedef AVLTreeNode Node;
    26. public:
    27. 	AVLTree()
    28. 		: _pRoot(nullptr)
    29. 	{}
    30.  
    31. 	bool Insert(const T& data)
    32. 	{
    33. 		// 先按照二叉搜索树的方式进行插入
    34. 		if (nullptr == _pRoot)
    35. 		{
    36. 			_pRoot = new Node(data);
    37. 			return true;
    38. 		}
    39.  
    40. 		// 按照二叉搜索树特性：找待插入节点在树中的位置
    41. 		// 并保存其双亲
    42. 		Node* pCur = _pRoot;
    43. 		Node* pParent = nullptr;
    44. 		while (pCur)
    45. 		{
    46. 			pParent = pCur;
    47. 			if (data < pCur->_data)
    48. 				pCur = pCur->_pLeft;
    49. 			else if (data > pCur->_data)
    50. 				pCur = pCur->_pRight;
    51. 			else
    52. 				return false;
    53. 		}
    54.  
    55. 		// 插入新节点
    56. 		pCur = new Node(data);
    57. 		if (data < pParent->_data)
    58. 			pParent->_pLeft = pCur;
    59. 		else
    60. 			pParent->_pRight = pCur;
    61. 		pCur->_pParent = pParent;
    62.  
    63. 		while (pParent)
    64. 		{
    65. 			// 更新pParent的平衡因子
    66. 			if (pCur == pParent->_pLeft)
    67. 				pParent->_bf--;
    68. 			else
    69. 				pParent->_bf++;
    70.  
    71. 			if (0 == pParent->_bf)
    72. 				break;
    73. 			else if (-1 == pParent->_bf || 1 == pParent->_bf)
    74. 			{
    75. 				pCur = pParent;
    76. 				pParent = pCur->_pParent;
    77. 			}
    78. 			else
    79. 			{
    80. 				// pParent->_bf: 2 || -2
    81. 				// pParent的节点失去平衡
    82. 				if (2 == pParent->_bf)
    83. 				{
    84. 					// 右子树高-->最后必须左单旋
    85. 					if (1 == pCur->_bf)
    86. 						RotateL(pParent);
    87. 					else
    88. 						RotateRL(pParent);
    89. 				}
    90. 				else
    91. 				{
    92. 					if (-1 == pCur->_bf)
    93. 						RotateR(pParent);
    94. 					else
    95. 						RotateLR(pParent);
    96. 				}
    97.  
    98. 				break;
    99. 			}
    100. 		}
    101. 		
    102. 		return true;
    103. 	}
    104.  
    105. 	void InOrder()
    106. 	{
    107. 		_InOrder(_pRoot);
    108. 	}
    109.  
    110. 	Node* LeftMost()
    111. 	{
    112. 		if (nullptr == _pRoot)
    113. 			return nullptr;
    114.  
    115. 		Node* pCur = _pRoot;
    116. 		while (pCur->_pLeft)
    117. 			pCur = pCur->_pLeft;
    118.  
    119. 		return pCur;
    120. 	}
    121.  
    122. 	Node* RightMost()
    123. 	{
    124. 		if (nullptr == _pRoot)
    125. 			return nullptr;
    126.  
    127. 		Node* pCur = _pRoot;
    128. 		while (pCur->_pRight)
    129. 			pCur = pCur->_pRight;
    130.  
    131. 		return pCur;
    132. 	}
    133.  
    134. 	bool IsAVLTree()
    135. 	{
    136. 		return _IsAVLTree(_pRoot);
    137. 	}
    138.  
    139. private:
    140.     // 验证二叉搜索树是否为有效的
    141. 	bool _IsAVLTree(Node* pRoot)
    142. 	{
    143. 		if (nullptr == pRoot)
    144. 			return true;
    145.  
    146. 		int leftHeight = _Height(pRoot->_pLeft);
    147. 		int rightHeight = _Height(pRoot->_pRight);
    148.  
    149. 		if (abs(rightHeight - leftHeight) > 1 ||
    150. 			rightHeight - leftHeight != pRoot->_bf)
    151. 			return false;
    152.  
    153. 		return _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
    154. 	}
    155.  
    156. 	size_t _Height(Node* pRoot)
    157. 	{
    158. 		if (nullptr == pRoot)
    159. 			return 0;
    160.  
    161. 		size_t leftHeight = _Height(pRoot->_pLeft);
    162. 		size_t rightHeight = _Height(pRoot->_pRight);
    163.  
    164. 		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    165. 	}
    166.  
    167.  
    168. 	void RotateR(Node* pParent)
    169. 	{
    170. 		Node* pSubL = pParent->_pLeft;
    171. 		Node* pSubLR = pSubL->_pRight;
    172.  
    173. 		// 改变pParent和pSubL孩子的指向
    174. 		pParent->_pLeft = pSubLR;
    175. 		if (pSubLR)
    176. 			pSubLR->_pParent = pParent;
    177.  
    178. 		pSubL->_pRight = pParent;
    179.  
    180. 		// 更新pParent和pSubL的双亲
    181. 		Node* pPParent = pParent->_pParent;
    182. 		pParent->_pParent = pSubL;
    183. 		pSubL->_pParent = pPParent;
    184.  
    185. 		// 更新原pParent双亲的左||右指针域指向
    186. 		if (nullptr == pPParent)
    187. 		{
    188. 			_pRoot = pSubL;
    189. 		}
    190. 		else
    191. 		{
    192. 			if (pParent == pPParent->_pLeft)
    193. 				pPParent->_pLeft = pSubL;
    194. 			else
    195. 				pPParent->_pRight = pSubL;
    196. 		}
    197.  
    198. 		pParent->_bf = pSubL->_bf = 0;
    199. 	}
    200.  
    201. 	void RotateL(Node* pParent)
    202. 	{
    203. 		Node* pSubR = pParent->_pRight;
    204. 		Node* pSubRL = pSubR->_pLeft;
    205.  
    206. 		pParent->_pRight = pSubRL;
    207. 		if (pSubRL)
    208. 			pSubRL->_pParent = pParent;
    209.  
    210. 		pSubR->_pLeft = pParent;
    211. 		Node* pPParent = pParent->_pParent;
    212. 		pParent->_pParent = pSubR;
    213. 		pSubR->_pParent = pPParent;
    214.  
    215. 		if (nullptr == pPParent)
    216. 		{
    217. 			_pRoot = pSubR;
    218. 		}
    219. 		else
    220. 		{
    221. 			if (pParent == pPParent->_pLeft)
    222. 				pPParent->_pLeft = pSubR;
    223. 			else
    224. 				pPParent->_pRight = pSubR;
    225. 		}
    226.  
    227. 		pParent->_bf = pSubR->_bf = 0;
    228. 	}
    229.  
    230. 	void RotateRL(Node* pParent)
    231. 	{
    232. 		Node* pSubR = pParent->_pRight;
    233. 		Node* pSubRL = pSubR->_pLeft;
    234. 		int bf = pSubRL->_bf;
    235.  
    236. 		RotateR(pParent->_pRight);
    237. 		RotateL(pParent);
    238.  
    239. 		// 更新部分节点的平衡因子
    240. 		if (bf == -1)
    241. 			pSubR->_bf = 1;
    242. 		else if (bf == 1)
    243. 			pParent->_bf = -1;
    244. 	}
    245.  
    246. 	void RotateLR(Node* pParent)
    247. 	{
    248. 		Node* pSubL = pParent->_pLeft;
    249. 		Node* pSubLR = pSubL->_pRight;
    250. 		int bf = pSubLR->_bf;
    251.  
    252. 		RotateL(pParent->_pLeft);
    253. 		RotateR(pParent);
    254. 		if (-1 == bf)
    255. 			pParent->_bf = 1;
    256. 		else if (1 == bf)
    257. 			pSubL->_bf = -1;
    258. 	}
    259.  
    260. 	void _InOrder(Node* pRoot)
    261. 	{
    262. 		if (pRoot)
    263. 		{
    264. 			_InOrder(pRoot->_pLeft);
    265. 			cout << pRoot->_data << " ";
    266. 			_InOrder(pRoot->_pRight);
    267. 		}
    268. 	}
    269.  
    270. private:
    271. 	Node* _pRoot;
    272. };

  • 相关阅读:
    Hadoop如何启动HttpFS服务？
    LeetCode-662-二叉树最大宽度
    liunx 搭建 zookeeper
    商城免费搭建之java商城 开源java电子商务Spring Cloud+Spring Boot+mybatis+MQ+VR全景+b2b2c
    Go重写Redis中间件 - Go实现内存数据库
    常用脚本学习手册——Bat脚本
    eventlet 协程
    el-table相同的值合并单元格+多级表头
    wx:for-item wx:for-index wx:for-key
    【论文笔记】Perception, Planning, Control, and Coordination for Autonomous Vehicles
  • 原文地址：https://blog.csdn.net/qq_61386381/article/details/126409881