• 【无标题】

    目录

    模拟插入节点

    左单旋

    右单旋

    右左双旋

    左右双旋

    总结

    实现

    插入实现

     左单旋实现

    右单旋实现

    右左双旋实现

    左右双旋实现

    AVL树 模拟实现（插入）

    AVL 树，是高度平衡二叉搜索树，其主要通过旋转来控制其左右子树的高度不超过1，这样就能达到搜索效率基本等同于满二叉树（O(LogN)），所以 AVL 并不会向普通的搜索树一样，在极端情况下退化为单枝。

    首先AVL在平衡的前提下，还要保证其是一颗搜索树，所以在插入的时候还是按照搜索树的插入规则来。

    AVL 树的高度就是右子树减左子树的高度。

    AVL 树的实现有几种，其中一种是借用平衡因子来查看其是否平衡，如果不适用平衡因子，那么就需要使用高度查看是否平衡，但是加入平衡因子会跟简单一些，所以下面我们实现的AVL 树是借用平衡因子来维持平衡的。

    模拟插入节点

    如果是第一次插入，以及第二次插入那么和搜索树是一摸一样的，为什么呢？

    因为如果是第一次插入，那么就是插入到根节点，所以该是是平衡的，无需做其他的操作来保持其平衡，而第二次插入也是不需要我们做其他操作的，同样是因为第二次插入也是平衡的（左右子树的高度不超过1）。

    左单旋

    插入两个节点如图所示：

    这时候，6 节点的高度就为 0，而 2 节点的高度为 1，因为 6 节点的左右子树的高度都为 0，而 2 节点的右子树的高度为 1，而左子树的高度为 0.

    如果是两个节点的话，是无法达到完全平衡的，所以并不是AVL树不想达到完全平衡，而是只有在满二叉树的情况下才能达到完全平衡。

    下面如果在插入一个节点，那么就会引发旋转：

    如果这时候插入节点 8，那么首先我们就能看到这棵树已经不平衡了，但是我们要怎么使用平衡因子来控制？

    插入节点 8，此时节点 8 的平衡因子肯定是 0，那么现在 8 在节点 6 的右边，所以 6 要对它的平衡因子进行+1操作：

    此时节点 6 的平衡因子变为了 1，现在我们想一下，如果平衡因子由 0 变为 1表示的是什么？

    节点刚开始的平衡因子是 0  ，说明刚开始的时候该树是平衡的，变为 1说明该树的右子树多增加了一个节点的高度，所以说明该树的高度发生了变化，所以既然该节点的高度发生了变化，那么该节点的父亲节点的高度可能也会发生变化，所以这时候我们需要向上检查父亲节点的高度：

    这时候父亲节点的高度变为了 2，说明此时已经不平衡了，那么要怎样旋转？

    我们发现这样的不平衡是单纯的右边高，所以我们尽可能向左旋转，将高度压下去，也就是使用左单旋：

    1. 我们需要将父亲节点（2），的右子树连接到，cur（6） 节点的左子树上 

    2. 我们将cur（6）节点的左子树，连接成父亲节点（2）

    所以旋转结束后就是这样：

    但是我们的平衡因子是不正确的，所以如果我们使用左单旋转，旋转之后我们需要将父亲节点（2），和cur节点（6）的平衡因子变为 0.

    上面我们为什么要将cur 节点的左孩子给父亲节点呢？

    因为这里我们只是画了一个节点，我们有可能右多个节点，所以我们还需要处理好其他节点，但是由于我们只是对cur 的左子树进行的调换位置，我们并未使其高度发生变化，所以我们也自然不需要对其的平衡因子进行调整：

    也就是像我们上图这样，cur节点，还有左子树：

    上图就是进行旋转之后的样子，然后进行修正平衡因子（parent 为 0，cur 为 0:

    右单旋

    如果我们的方向不同呢？也就是整个树是单纯的左边高：

    插入节点：

     修正平衡因子：

    这里我们发现节点 6 已经不平衡了，需要旋转来维持平衡，这时候我们发现它是单纯的左边高，也就是我们需要像右旋转，也就是右单旋：

    1. 将节点 4 的右子树连接到节点 6 的左子树上

    2. 将节点 6 连接到节点 4 的右子树上

    旋转结束后就就是这样：

     我们还是将parent节点（6）和 cur节点（4）的平衡因子修改为 0.

    而这里处理cur节点的右子树的原因和处理左单旋时候的 cur 的左子树是一样的原因。

    经过上面的左单旋和右单旋，我们发现：

    1. 如果插入节点到当前节点的左子树：那么就让当前节点的平衡因子进行 ‘减减’ 操作

    2. 如果插入节点到当前节点的右子树：那么就让当前节点的平衡因子进行 ‘加加’ 操作

    3.如果平衡因子由 0 变为 1 或者由 0 变为 -1 ，那么就说明当前节点的左右子树的高度发生的变化，需要对当前节点的父亲节点进行平衡因子的跟新。

    4.如果当前节点的平衡因子被跟新为 2 或者 -2 ，那么说明当前节点的左右子树已经不平衡了，需要旋转来调节平衡。

    5. 什么时候插入结束？

    1）当插入的节点是根节点，那么插入后就可以结束了。

    2）插入的节点已经存在

    3）插入成功并且修正平衡因子后，父亲的平衡因子变为 0 ，变为 0 说明父亲之前的平衡因子不为        0，而变为 0 说明父亲的高度没有发生变化，所以无需在向上调整，插入也就结束。

    4）修正平衡因子后，发现某一节点需要旋转，而旋转并且修正平衡因子后，插入结束。

    上面说的修正平衡因子是一个循环的过程，因为在修正平衡因子的时候，可能将父亲的平衡因子由0 变为 1 或者 -1 ，说明父亲的高度变化了，所以此时就需要将父亲给给 cur 然后继续向上调整，还有一个插入结束的调节，就是父亲为空也插入结束了，父亲为空说明为根节点。

    6. 判断是左单旋还是右单旋：

    1）如果是单纯的左边高，那么就进行右单旋，那么怎么判断是单纯的左边高？单纯的左边高，就是父亲节点的平衡因子为 -2 ，而 cur 节点的平衡因子为 -1.

    2）如果是单纯的右边高，那么就进行右单旋，右单旋的特征是，parent 的平衡因子是 2， cur 的平衡因子是 1

    右左双旋

    上面我们插入后总是一边高，但是我们还是右其他的情况，也就是下面这种：

    我们这种该怎么样旋转呢？我们可以先试一下左单旋，因为这里我们发现是右边高：

    在旋转后，我们发现高度并没有被压缩，而是调了个个，所以如果是这种情况的话，单纯的左或者右是不能完成任务的，而是需要使用双旋。

    我们可以先对cur 节点进行右单旋：

     经过我们前面对 cur 节点进行的右单旋，我们此时已经变为一边高了，所以此时我们在对 parent 节点进行左单旋就可以完成压缩高度任务：

    我们此时经过旋转后的 parent 和 cur 节点的平衡因子变为 0了：

    但是这只是我们节点 4 就是新插入的节点，那么假设是其他情况呢？

     上图是抽象图，可以表示该种情况下所有可能的情况，如果当 h == 0 的时候，就表示的是 4 节点是新增，但是无论 h 是多少，我们都可以使用右左双旋。

    首先对该树的cur 节点使用右单旋：

    旋转后就变为了这样，也就是单纯的右边高，所以我们在使用左单旋对parent节点：

    但是这时候 parent 和 cur 节点的平衡因子都是 0，那么我们要怎么调节平衡因子呢？对于这种情况来说，我们是将parent 的平衡因子调整为 -1 ，cur 的平衡因子为 0，即可，但是我们要是插入的位置不是刚开始插入的位置呢？

    如果插入到该位置，那么金国旋转后的结果是这样的：

    所以此时跟新平衡因子应该是 parent 为 0 ,cur 的平衡因子应该为 1，所以我们插入位置不同的话，我们的平衡因子的跟新策略是不同的，所以我们还要记录插入位置的平衡因子。

    我们为了更好的描述，我们将节点 4 称为 curLeft。

    我们发现我们在旋转结束后，curLeft 的左右子树被parent 和 cur 代替，而他自己的左子树被分给了parent 的 right 子树 ，而它的右子树被分给了cur 的 left 子树，所以我们只需要知道 curRight 的平衡因子，我们也就可以将parent 和 cur 的平衡因子跟新正确。

    上面我们一直都没有说 curLeft 的平衡因子，其实curLeft 的平衡因子在第一次右单旋的时候就被跟新为了 0 ，而旋转结束后，curLeft 的平衡因子也就应该是 0.

    左右双旋

    这里我们就直接使用抽象图来描述了。

    以上图为例，我们要插入一个值：

    现在我们发现是左边高，但是我们知道这种情况下，我们单纯的使用右单旋是解决不了问题的，所以我们还是选哟使用双旋，也就是左右双旋，我们先对cur 节点进行左单旋，然后对parent 进行右单旋：

     旋转后，我们发现现在是单纯的左边高，所以我们对 parent 节点使用右单旋：

    这时候的 parent cur 以及 curRight  的平衡因子都被跟新为 0了 ，但是都是 0 并不正确，而是也像我们前面的右左双一样，需要看 curRight 的平衡因子：

    1. 如果插入到 curRight 的keft，那么 cur 的平衡因子就是 0 ，parent 的平衡因子为 1。

    2. 如果插入到 curRight 的 right ，那么 cur 的平衡因子就是 -1，parent 的平衡因子就是 0。

    总结

    • 如果 parent 的平衡因子为 2 ，cur 的平衡因子为 1，那么使用的是左单旋，将 parent 和 cur 的平衡因子都跟新为 0.
    • 如果 parent 的平衡因子为 -2 ，cur 的平衡因子为 -1，那么使用的是右单，将 parent 和 cur 的平衡因子都跟新为 0.。
    • 如果 parent 的平衡因子为 2 ，cur 的平衡因子为 -1，那么使用的是右左双旋                    平衡因子：                                                                                                                      如果curLeft 的平衡因子为 1 ，那么就将parent 的平衡因子置为 -1，cur 的平衡因子置为 0，curLeft 的平衡因子为 0                                                                                              如果curLeft 的平衡因子为 -1 ，那么就将parent 的平衡因子置为 0，cur 的平衡因子置为 1，curLeft 的平衡因子为 0                                                                                              如果curLeft 的平衡因子为 0 ，那么就将parent 的平衡因子置为 0，cur 的平衡因子置为 0，curLeft 的平衡因子为 0 
    • 如果 parent 的平衡因子为 -2 ，cur 的平衡因子为 1，那么使用的是左右双旋                    平衡因子：                                                                                                                      如果curRight的平衡因子为 1 ，那么就将parent 的平衡因子置为 0，cur 的平衡因子置为 -1，curRight的平衡因子为 0                                                                                           如果curRight的平衡因子为 -1 ，那么就将parent 的平衡因子置为 1，cur 的平衡因子置为 0，curRight的平衡因子为 0                                                                                          如果curRight的平衡因子为 0 ，那么就将parent 的平衡因子置为 0，cur 的平衡因子置为 0，curLeft 的平衡因子为 0        

    实现

    上面大概率是把思路都说明白了，下面开始看一下实现：

    插入实现

    首先我们先看一下AVLTreeNode:

    对于该节点，我们需要一个存储值的变量，我们还需要三个指针，其中一个 left，还有一个 right，还有一个 parent，这里需要parent 是因为我们需要找找到它的父亲节点，还需要一个平衡因子

    1. template<class K, class V>
    2. struct TreeNode
    3. {
    4. 	pair _kv;
    5. 	TreeNode* _left;
    6. 	TreeNode* _right;
    7. 	TreeNode* _parent;
    8. 	int _balance;
    9.  
    10. 	TreeNode(const pair& kv)
    11. 		:_kv(kv)
    12. 		, _left(nullptr)
    13. 		, _right(nullptr)
    14. 		, _parent(nullptr)
    15. 		,_balance(0)
    16. 	{}
    17. };

    这里我们将存储值的变量之间设置为了 kv 结构，因为这样既可以适用于 set，也适用于 map.

    下面就是插入：

    插入的话，先按照搜索树的插入节点，也就是插入插入位置，然后记录其父亲节点：

    1. 		if (_root == nullptr)
    2. 		{
    3. 			_root = new Node(kv);
    4. 			return true;
    5. 		}
    6.  
    7. 		Node* cur = _root;
    8. 		Node* parent = nullptr;
    9. 		while (cur)
    10. 		{
    11. 			if (kv.first < cur->_kv.first)
    12. 			{
    13. 				parent = cur;
    14. 				cur = cur->_left;
    15. 			}
    16. 			else if (kv.first > cur->_kv.first)
    17. 			{
    18. 				parent = cur;
    19. 				cur = cur->_right;
    20. 			}
    21. 			else
    22. 			{
    23. 				// 重复了，插入失败
    24. 				return false;
    25. 			}
    26. 		}
    27.  
    28. 		// 插入数据
    29. 		cur = new Node(kv);
    30. 		if (kv.first < parent->_kv.first)
    31. 		{
    32. 			//维护三叉链
    33. 			parent->_left = cur;
    34. 			cur->_parent = parent;
    35. 		}
    36. 		else
    37. 		{
    38. 			//维护三叉链
    39. 			parent->_right = cur;
    40. 			cur->_parent = parent;
    41. 		}

    等 cur 节点插入后，开始修正并检查平衡：

    1. 		//检查平衡
    2. 		while (parent)
    3. 		{
    4. 			//维护平衡因子
    5. 			// 平衡因子=右子树高度-左子树高度
    6. 			if (cur == parent->_left)
    7. 			{
    8. 				parent->_balance--;
    9. 			}
    10. 			else
    11. 			{
    12. 				parent->_balance++;
    13. 			}
    14. 			// 检查 parent 的平衡因子
    15. 			// 如果为 0 说明parent 这颗树以及平衡，无需检查
    16. 			// 如果为 1/-1 说明 parent 的平衡发生了变化，说明需要检查 parent 的parent 的平衡因子
    17. 			// 如果为 2/-2 说明这棵树已经不平衡了，需要旋转
    18.  
    19. 			if (parent->_balance == 0)
    20. 			{
    21. 				//该树已经平衡
    22. 				break;
    23. 			}
    24. 			else if (parent->_balance == 1 || parent->_balance == -1)
    25. 			{
    26. 				// 说明该树的高度发生变化,需要检查 parent 的 parent 的平衡因子，所以需要向上传递
    27. 				cur = parent;
    28. 				parent = parent->_parent;
    29. 			}
    30. 			else if (parent->_balance == 2 || parent->_balance == -2)
    31. 			{
    32. 				// 说明该树需要旋转保持平衡
    33. 				if (parent->_balance == 2 && cur->_balance == 1)
    34. 				{
    35. 					// 左单旋
    36. 					RotateL(parent);
    37. 					break;
    38. 				}
    39. 				else if (parent->_balance == -2 && cur->_balance == -1)
    40. 				{
    41. 					// 右单旋
    42. 					RotateR(parent);
    43. 					break;
    44. 				}
    45. 				else if (parent->_balance == 2 && cur->_balance == -1)
    46. 				{
    47. 					// 右左双旋
    48. 					RotateRL(parent);
    49. 					break;
    50. 				}
    51. 				else if (parent->_balance == -2 && cur->_balance == 1)
    52. 				{
    53. 					// 左右双旋
    54. 					RotateLR(parent);
    55. 					break;
    56. 				}
    57. 				else
    58. 				{
    59. 					assert(0);
    60. 				}
    61. 			}
    62. 			else
    63. 			{
    64. 				// 不能出现该种情况
    65. 				assert(0);
    66. 			}
    67.  
    68. 		}

    上面就是修正并且检查平衡，那么我们看一下应该怎么样旋转：

     左单旋实现

    实际上，左单旋并不是像我们说的那样，只有我们前面模拟插入的时候的两步

    主要步骤：

    1. 将 parent 的 right 连接成 cur 的 left

    2. 将 cur 的 left 连接成 parent

    3. 维护三叉链

    实际上我们还需要维护三叉链，也就是他们的父亲节点，。

    1. 	// 左单旋
    2. 	void RotateL(Node* parent)
    3. 	{
    4. 		Node* cur = parent->_right;
    5. 		Node* curLeft = cur->_left;
    6.  
    7. 		parent->_right = curLeft;
    8. 		if (curLeft)
    9. 		{
    10. 			curLeft->_parent = parent;
    11. 		}
    12. 		cur->_left = parent;
    13. 		Node* pparent = parent->_parent;
    14. 		parent->_parent = cur;
    15. 		if (pparent == nullptr)
    16. 		{
    17. 			// parent 就是根节点
    18. 			_root = cur;
    19. 			cur->_parent = nullptr;
    20. 		}
    21. 		else
    22. 		{
    23. 			if (parent == pparent->_left)
    24. 			{
    25. 				pparent->_left = cur;
    26. 			}
    27. 			else
    28. 			{
    29. 				pparent->_right = cur;
    30. 			}
    31. 			cur->_parent = pparent;
    32. 		}
    33.  
    34. 		parent->_balance = 0;
    35. 		cur->_balance = 0;
    36. 	}

    右单旋实现

    主要步骤：

    1. 将 parent 的 left 链接到 cur 的 right

    2.将 cur 的 left 链接到 parent

    3. 维护其三叉链

    1. 	//右单旋
    2. 	void RotateR(Node* parent)
    3. 	{
    4. 		Node* cur = parent->_left;
    5. 		Node* curRight = cur->_right;
    6.  
    7. 		parent->_left = curRight;
    8. 		if (curRight)
    9. 		{
    10. 			curRight->_parent = parent;
    11. 		}
    12. 		cur->_right = parent;
    13. 		Node* pparent = parent->_parent;
    14. 		parent->_parent = cur;
    15. 		if (pparent == nullptr)
    16. 		{
    17. 			// 说明 parent 是根节点
    18. 			_root = cur;
    19. 			cur->_parent = nullptr;
    20. 		}
    21. 		else
    22. 		{
    23. 			if (parent == pparent->_left)
    24. 			{
    25. 				pparent->_left = cur;
    26. 			}
    27. 			else
    28. 			{
    29. 				pparent->_right = cur;
    30. 			}
    31. 			cur->_parent = pparent;
    32. 		}
    33.  
    34. 		parent->_balance = 0;
    35. 		cur->_balance = 0;
    36. 	}

    右左双旋实现

    主要步骤：

    1. 对 cur 节点进行右旋

    2. 对 parent 节点进行左旋

    3. 修正平衡因子，这个我们前面总结过了

    1. 	void RotateRL(Node* parent)
    2. 	{
    3. 		//先对 cur 节点进行右单旋
    4. 		//在对 parent 节点进行左单旋
    5. 		Node* cur = parent->_right;
    6. 		Node* curLeft = cur->_left;
    7.  
    8. 		int balance = curLeft->_balance;
    9.  
    10. 		RotateR(cur);
    11. 		RotateL(parent);
    12.  
    13. 		//旋转后维护平衡因子
    14. 		//这里右几种可能：
    15. 		//1. curLeft 节点的平衡因子为 0
    16. 		//2. curLeft 节点的平衡因子为-1
    17. 		//3. curLeft 节点的平衡因子为 1
    18. 		// 这里发现每一次旋转结束后，curRight 节点的左树给了parent，右树给了 cur，
    19. 		// 所以这里需要的以区分新增节点插入到了 curRight 节点的左是右
    20. 		// 记录该平衡因子主要是为了维护旋转后的平衡因子
    21.  
    22. 		if (balance == 0)
    23. 		{
    24. 			// curRight 就是新增节点，所以cur,parent,curRight 的平衡因子都为 0
    25. 			cur->_balance = 0;
    26. 			parent->_balance = 0;
    27. 			curLeft->_balance = 0;
    28. 		}
    29. 		else if (balance == 1)
    30. 		{
    31. 			// 新增在了右边，所以cur,parent,curRight 的平衡因子分别为 0，-1，0
    32. 			cur->_balance = 0;
    33. 			parent->_balance = -1;
    34. 			curLeft->_balance = 0;
    35. 		}
    36. 		else if (balance == -1)
    37. 		{
    38. 			// 新增在了左边，所以cur,parent,curRight 的平衡因子分别为 1，0，0
    39. 			cur->_balance = 1;
    40. 			parent->_balance = 0;
    41. 			curLeft->_balance = 0;
    42. 		}
    43. 		else
    44. 		{
    45. 			assert(0);
    46. 		}
    47. 	}

    左右双旋实现

    主要步骤：

    1. 对 cur 节点进行左旋

    2. 对 parent 节点进行右旋

    3. 修正平衡因子，这个我们前面总结过了

    1. 	// 左右双旋
    2. 	void RotateLR(Node* parent)
    3. 	{
    4. 		Node* cur = parent->_left;
    5. 		Node* curRight = cur->_right;
    6.  
    7. 		int balance = curRight->_balance;
    8.  
    9. 		RotateL(cur);
    10. 		RotateR(parent);
    11.  
    12. 		if (balance == 0)
    13. 		{
    14. 			cur->_balance = 0;
    15. 			parent->_balance = 0;
    16. 			curRight->_balance = 0;
    17. 		}
    18. 		else if (balance == -1)
    19. 		{
    20. 			cur->_balance = 0;
    21. 			parent->_balance = 1;
    22. 			curRight->_balance = 0;
    23. 		}
    24. 		else if (balance == 1)
    25. 		{
    26. 			cur->_balance = -1;
    27. 			parent->_balance = 0;
    28. 			curRight->_balance = 0;
    29. 		}
    30. 	}

  • 相关阅读:
    Python boxplot 详解+用法
    uml简单用例图怎么画（要素，文字形式）
    STM32单片机语音识别MP3播放器音乐播放器TF卡播放器
    Isaac-gym(8):Tensor API
    基于费舍尔判别分析的故障与诊断（lunwen+文献综述+翻译及原文+MATLAB程序）
    Leetcode 701. 二叉搜索树中的插入操作
    vue使用window.location.href 跳转失败
    12_被讨厌的勇气书摘
    Java移除链表元素
    基于粒子群算法优化支持向量机研究(Python代码实现）
  • 原文地址：https://blog.csdn.net/m0_73455775/article/details/132787634