目录

一、基础知识

 二、代码实现     

                    1.插入操作

                ①三步走：

                ②代码框架:

                ③旋转操作详解

   2.删除操作

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

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

                        ③删除的大致步骤

 test:​

一、基础知识

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

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

其他基础知识点参见：

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

 二、代码实现     

    1.插入操作

                ①三步走：

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

                        step2:需要判断是否平衡

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

                ②代码框架:

template
inline void AVLTree::_insertNode(Node*& root, const T& data)
{
	//step1:以有序二叉树的方式进行插入
	if (root == nullptr)
	{
		root = new Node(data);
	}
	else if (data > root->data)//往右边插入
	{
		_insertNode(root->pRight, data);
		//step2:需要判断是否平衡
		if (_getH(root->pRight) - _getH(root->pLeft) > 1)//不平衡了,不能直接访问(用->height，防止为NULL)
		{
			if (root->pRight->data < data)
			{//需要左旋
				root = LL(root);
			}
			else
			{//需要右旋，再左旋
				root = RL(root);
			}
		}
		
	}
	else//data小于等于当前节点的值，均往左边插入
	{
		_insertNode(root->pLeft, data);
		if (_getH(root->pLeft) - _getH(root->pRight) > 1)
		{
			if (root->pLeft->data >= data)//注意是>=因为等于的值也是放在左边的！！！
			{//需要右旋
				root = RR(root);
			}
			else
			{//需要左旋+右旋
				root = LR(root);
			}
		}
	}
	//step3:设置高度
	int LeftHeight = _getH(root->pLeft);
	int RightHeight = _getH(root->pRight);
	root->height = 1 + ((LeftHeight > RightHeight) ? LeftHeight : RightHeight);
}

                ③旋转操作详解：

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

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

                五步走

 

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

                （ii）左右旋 

步骤：

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

    ②再让root正常右旋即可。

template
inline Node* AVLTree::LR(Node*& root)
{
	root->pLeft = LL(root->pLeft);
	return RR(root);
}

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

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

template
inline Node* AVLTree::RL(Node*& root)
{
	root->pRight = RR(root->pRight);
	return LL(root);
}

测试：

        2.删除操作

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

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

template
inline Node* AVLTree::Get_predecessor(Node* root)//传入的是parent的left孩子
{
	Node* pMove = root;
	while (pMove->pRight)
	{
		pMove = pMove->pRight;
	}
	return pMove;
}

template
inline Node* AVLTree::Get_successor(Node* root)
{//传入的是parent的Right孩子
	Node* pMove = root;
	while (pMove->pLeft)
	{
		pMove = pMove->pLeft;
	}
	return pMove;
}

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

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

                        ③删除的大致步骤

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

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

                     ---->若需要rotate也需要看情况rotate见上图(LLRRRLLR)      

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

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

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

void deleteNode(const T& data) {_deleteNode(pRoot, data); }

template
inline Node* AVLTree::_deleteNode(Node* root, const T& data)
{
	if (root == nullptr)return nullptr;//空树无法删除	
	//Step one:利用二分特性递归删除,回溯到上一层之后就开始调整rotate
	if (data < root->data)
	{//需要往左边边删除
		root->pLeft=_deleteNode(root->pLeft, data);//注意返回值是用来更新当前节点的！！！
		if (_getH(root->pRight) - _getH(root->pLeft) == 2)//由于删除的是左边->故若不平衡,也必定是右边大于左边
		{//下面看是哪一种类型的(RLorLL)
			Node* rightNode = root->pRight;
			if (_getH(rightNode->pRight) > _getH(rightNode->pLeft))
			{//本处if->显然放在了右边
				root = LL(root);
			}
			else
			{
				root = RL(root);
			}
		}
	}
	else if (data>root->data)
	{
		root->pRight=_deleteNode(root->pRight, data);
        //注意:返回值是用来更新当前节点的！！！
		if (_getH(root->pLeft) - _getH(root->pRight) == 2)//由于删除的是right->故若不平衡,也必定left>right
		{//下面看是哪一种类型的(LRorRR)
			Node* rightNode = root->pLeft;
			if (_getH(rightNode->pRight) > _getH(rightNode->pLeft))
			{//本处if->显然放在了左边
				root = LR(root);
			}
			else
			{
				root =RR(root);
			}
		}
	}
	else//找到了->分为四种情况,将左右子树孩子都有的情况下,转化为其余三种情况即可
	{
		if (root->pLeft && root->pRight)//左右孩子都有的情况->递归转化成单边or叶子结点
		{
			if (_getH(root->pLeft) > _getH(root->pRight))//左子树高度更高->取前驱节点进行覆盖
			{
				Node* pMax = Get_predecessor(root->pLeft);
				root->data = pMax->data;			//覆盖
				root->pLeft=_deleteNode(root->pLeft,pMax->data);//往下递归删除即可
			}
			else
			{				//右子树高度更高
				Node* pMin = Get_successor(root->pRight);
				root->data = pMin->data;
				root->pRight=_deleteNode(root->pRight, pMin->data);
			}
		}
		else//单边or叶子结点
		{
			Node* pTemp = root;//暂存需要删除的结点
			root = (root->pLeft) ? root->pLeft : root->pRight;//让单支孩子上来继承(优先判断是哪一支)------>更新了root,所以最后返回值一定赋值给原来的root(以更新!!!!)
			delete pTemp;
			pTemp = nullptr;
		}
	}
	return root;
}

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

                test:

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