• Day12：AVL树--平衡二叉树

    目录

    一、基础知识

     二、代码实现     

                        1.插入操作

                    ①三步走：

                    ②代码框架:

                    ③旋转操作详解

       2.删除操作

                            ①补充知识点：前驱节点&&后驱节点​

                            ②如何处理待删除的结点？​

                            ③删除的大致步骤

     test:​

    一、基础知识

    平衡二叉树：AVL-tree
        树中每一个节点左右子树高度差不超过1有序二叉树BST

    高度的定义为：从结点x向下到某个叶结点最长简单路径中边的条数

    其他基础知识点参见：

    数据结构 --- c语言实现AVL平衡二叉搜索树

     二、代码实现     

        1.插入操作

                    ①三步走：

                            step1:以有序二叉树的方式进行插入

                            step2:需要判断是否平衡

                            step3:设置高度(利用递归的特性,会从叶子结点逐项累加)

                    ②代码框架:

    1. template<class T>
    2. inline void AVLTree::_insertNode(Node*& root, const T& data)
    3. {
    4. 	//step1:以有序二叉树的方式进行插入
    5. 	if (root == nullptr)
    6. 	{
    7. 		root = new Node(data);
    8. 	}
    9. 	else if (data > root->data)//往右边插入
    10. 	{
    11. 		_insertNode(root->pRight, data);
    12. 		//step2:需要判断是否平衡
    13. 		if (_getH(root->pRight) - _getH(root->pLeft) > 1)//不平衡了,不能直接访问(用->height，防止为NULL)
    14. 		{
    15. 			if (root->pRight->data < data)
    16. 			{//需要左旋
    17. 				root = LL(root);
    18. 			}
    19. 			else
    20. 			{//需要右旋，再左旋
    21. 				root = RL(root);
    22. 			}
    23. 		}
    24. 		
    25. 	}
    26. 	else//data小于等于当前节点的值，均往左边插入
    27. 	{
    28. 		_insertNode(root->pLeft, data);
    29. 		if (_getH(root->pLeft) - _getH(root->pRight) > 1)
    30. 		{
    31. 			if (root->pLeft->data >= data)//注意是>=因为等于的值也是放在左边的！！！
    32. 			{//需要右旋
    33. 				root = RR(root);
    34. 			}
    35. 			else
    36. 			{//需要左旋+右旋
    37. 				root = LR(root);
    38. 			}
    39. 		}
    40. 	}
    41. 	//step3:设置高度
    42. 	int LeftHeight = _getH(root->pLeft);
    43. 	int RightHeight = _getH(root->pRight);
    44. 	root->height = 1 + ((LeftHeight > RightHeight) ? LeftHeight : RightHeight);
    45. }

                    ③旋转操作详解：

    抽象出来，共四个原始情况如下：

                            （i）右旋(轴->传入的参数)

                    五步走

     

    1. template<class T>
    2. inline Node* AVLTree::RR(Node*& root)
    3. {
    4. 	Node* pTemp = root->pLeft;	//1.暂存中间的结点
    5. 	root->pLeft = pTemp->pRight;//2.管理ptemp的右孩子成为root的左孩子
    6. 	pTemp->pRight = root;		//3.root成为temp的右孩子
    7. 	//4.设置高度(高度可能会变的两个点①root②ptemp(因为其右孩子给root，root成为了其右孩子))
    8. 	root->height = 1 + (_getH(root->pLeft) > _getH(root->pRight) ? _getH(root->pLeft) : _getH(root->pRight));
    9. 	pTemp->height = 1 + (_getH(pTemp->pLeft) > _getH(pTemp->pRight) ? _getH(pTemp->pLeft) : _getH(pTemp->pRight));
    10. 	return pTemp;				//5.返回ptemp,成为新的root（赋值
    11. }

                    （ii）左右旋 

    步骤：

        ①先让root->pLeft成为轴进行一次左旋

        ②再让root正常右旋即可。

    1. template<class T>
    2. inline Node* AVLTree::LR(Node*& root)
    3. {
    4. 	root->pLeft = LL(root->pLeft);
    5. 	return RR(root);
    6. }

    左旋和右左旋类似，代码如下

    1. template<class T>
    2. inline Node* AVLTree::LL(Node*& root)
    3. {
    4. 	Node* pTemp = root->pRight;		//1.暂存temp
    5. 	root->pRight = pTemp->pLeft;	//2.temp的左孩子当root的右孩子(断开了temp的连接)
    6. 	pTemp->pLeft = root;			//3.pTemp的左孩子变成左孩子
    7. 	//4.设置高度
    8. 	root->height = 1 + (_getH(root->pLeft) > _getH(root->pRight) ? _getH(root->pLeft) : _getH(root->pRight));
    9. 	pTemp->height = 1 + (_getH(pTemp->pLeft) > _getH(pTemp->pRight) ? _getH(pTemp->pLeft) : _getH(pTemp->pRight));
    10. 	return pTemp;//5.返回temp
    11. }
    1. template<class T>
    2. inline Node* AVLTree::RL(Node*& root)
    3. {
    4. 	root->pRight = RR(root->pRight);
    5. 	return LL(root);
    6. }

    测试：

            2.删除操作

                    ①补充知识点：前驱节点&&后驱节点

     predecessor->找到前驱节点   successor->找到后驱节点

    1. template<class T>
    2. inline Node* AVLTree::Get_predecessor(Node* root)//传入的是parent的left孩子
    3. {
    4. 	Node* pMove = root;
    5. 	while (pMove->pRight)
    6. 	{
    7. 		pMove = pMove->pRight;
    8. 	}
    9. 	return pMove;
    10. }
    11.  
    12. template<class T>
    13. inline Node* AVLTree::Get_successor(Node* root)
    14. {//传入的是parent的Right孩子
    15. 	Node* pMove = root;
    16. 	while (pMove->pLeft)
    17. 	{
    18. 		pMove = pMove->pLeft;
    19. 	}
    20. 	return pMove;
    21. }

                            ②如何处理待删除的结点？

    左右孩子都有的情况下->在选择前驱节点or后驱节点覆盖之后，就开始递归调用。

                            ③删除的大致步骤

                    step1:利用二叉树二分特性，传入待删data，递归搜索

                             在递归回溯的时候，紧接着就会判断：是否需要rotate(自下而上,高度差一旦达到2，就会调整,不会出现3)

                         ---->若需要rotate也需要看情况rotate见上图(LL\RR\RL\LR)      

                    step2:当posdata找到之后（pMove->data==posdata)        

                            ①若有左右子树->看左右子树的高度(找到高度较大的那个:左树高->前驱节点，右树高->后驱节点),然后进行覆盖操作->然后递归将下面原先的结点删除掉(转化为单边树进行处理)。

                            ②叶子结点or仅一边树：让孩子上来覆盖即可(叶子结点->就是让nullptr上来覆盖)

    1. void deleteNode(const T& data) {_deleteNode(pRoot, data); }
    2.  
    3. template<class T>
    4. inline Node* AVLTree::_deleteNode(Node* root, const T& data)
    5. {
    6. 	if (root == nullptr)return nullptr;//空树无法删除	
    7. 	//Step one:利用二分特性递归删除,回溯到上一层之后就开始调整rotate
    8. 	if (data < root->data)
    9. 	{//需要往左边边删除
    10. 		root->pLeft=_deleteNode(root->pLeft, data);//注意返回值是用来更新当前节点的！！！
    11. 		if (_getH(root->pRight) - _getH(root->pLeft) == 2)//由于删除的是左边->故若不平衡,也必定是右边大于左边
    12. 		{//下面看是哪一种类型的(RLorLL)
    13. 			Node* rightNode = root->pRight;
    14. 			if (_getH(rightNode->pRight) > _getH(rightNode->pLeft))
    15. 			{//本处if->显然放在了右边
    16. 				root = LL(root);
    17. 			}
    18. 			else
    19. 			{
    20. 				root = RL(root);
    21. 			}
    22. 		}
    23. 	}
    24. 	else if (data>root->data)
    25. 	{
    26. 		root->pRight=_deleteNode(root->pRight, data);
    27.         //注意:返回值是用来更新当前节点的！！！
    28. 		if (_getH(root->pLeft) - _getH(root->pRight) == 2)//由于删除的是right->故若不平衡,也必定left>right
    29. 		{//下面看是哪一种类型的(LRorRR)
    30. 			Node* rightNode = root->pLeft;
    31. 			if (_getH(rightNode->pRight) > _getH(rightNode->pLeft))
    32. 			{//本处if->显然放在了左边
    33. 				root = LR(root);
    34. 			}
    35. 			else
    36. 			{
    37. 				root =RR(root);
    38. 			}
    39. 		}
    40. 	}
    41. 	else//找到了->分为四种情况,将左右子树孩子都有的情况下,转化为其余三种情况即可
    42. 	{
    43. 		if (root->pLeft && root->pRight)//左右孩子都有的情况->递归转化成单边or叶子结点
    44. 		{
    45. 			if (_getH(root->pLeft) > _getH(root->pRight))//左子树高度更高->取前驱节点进行覆盖
    46. 			{
    47. 				Node* pMax = Get_predecessor(root->pLeft);
    48. 				root->data = pMax->data;			//覆盖
    49. 				root->pLeft=_deleteNode(root->pLeft,pMax->data);//往下递归删除即可
    50. 			}
    51. 			else
    52. 			{				//右子树高度更高
    53. 				Node* pMin = Get_successor(root->pRight);
    54. 				root->data = pMin->data;
    55. 				root->pRight=_deleteNode(root->pRight, pMin->data);
    56. 			}
    57. 		}
    58. 		else//单边or叶子结点
    59. 		{
    60. 			Node* pTemp = root;//暂存需要删除的结点
    61. 			root = (root->pLeft) ? root->pLeft : root->pRight;//让单支孩子上来继承(优先判断是哪一支)------>更新了root,所以最后返回值一定赋值给原来的root(以更新!!!!)
    62. 			delete pTemp;
    63. 			pTemp = nullptr;
    64. 		}
    65. 	}
    66. 	return root;
    67. }

     代码细节:通过返回值，进行修改root(返回新的根节点)

                    test:

    1. #include"AVLTree.h"
    2. using namespace std;
    3. int main()
    4. {
    5. 	AVLTree<int> tree;
    6. 	int arr[] = {1,4,2,9,6,5,8,10,7};
    7. 	for (auto v : arr)
    8. 	{
    9. 		tree.insertNode(v);
    10. 	}
    11. 	tree.deleteNode(10);
    12. 	tree.deleteNode(9);
    13. 	tree.midtravel();
    14. 	return 0;
    15. }

     

  • 相关阅读:
    一文教你在 centos7 下安装 Oracle19 C(完整版)
    条件生成对抗网络（cGAN）在AI去衣技术中的应用探索
    Flink学习之旅：（四）Flink转换算子（Transformation）
    深入理解Nginx日志级别
    安卓打开第三方应用失败
    Vue 高级特性总结
    Jmeter常用参数化技巧总结！
    1、skywalking-介绍
    Lua学习笔记：debug.sethook函数
    【Spring Boot】自定义启动器starter
  • 原文地址：https://blog.csdn.net/zjjaibc/article/details/126168281