从零开始的C++（十八）

avl树中insert的模拟实现

avl树特点：

1.是搜索二叉树

2.每个结点的左右子树高度差的绝对值不超过2

inser模拟实现：

	// 右单旋
	void RotateR(Node* pParent)
	{
		Node* parent = pParent;
		Node* pr = parent->_pRight;
		Node* prl = pr->_pLeft;
		//记录父节点
		Node* pp = parent->_pParent;

		//更新指针
		parent->_pRight = prl;
		if(prl)//判断prl是否存在
		prl->_pParent = parent;

		pr->_pLeft = parent;
		parent->_pParent = pr;

		if (pp == nullptr)
		{
			//若parent是根节点
			_pRoot = pr;
			pr->_pParent = nullptr;
		}
		else
		{   //父节点连接
			if (pp->_data < parent->_data)
			{
				pp->_pRight = pr;
				pr->_pParent = pp;
			}
			else
			{
				pp->_pLeft = pr;
				pr->_pParent = pp;
			}
		}

		//更新平衡因子
		parent->_bf = 0;
		pr->_bf = 0;

	}
	// 左单旋
	void RotateL(Node* pParent)
	{
		Node* parent = pParent;
		Node* pl = parent->_pLeft;
		Node* plr = pl->_pRight;
		//记录父节点
		Node* pp = parent->_pParent;

		//更新指针
		parent->_pLeft = plr;
		if (plr)//判断prl是否存在
			plr->_pParent = parent;

		pl->_pRight = parent;
		parent->_pParent = pl;

		if (pp == nullptr)
		{
			//若parent是根节点
			_pRoot = pl;
			pl->_pParent = nullptr;
		}
		else
		{   //父节点连接
			if (pp->_data < parent->_data)
			{
				pp->_pRight = pl;
				pl->_pParent = pp;
			}
			else
			{
				pp->_pLeft = pl;
				pl->_pParent = pp;
			}
		}

		//更新平衡因子
		parent->_bf = 0;
		pl->_bf = 0;



	}
	// 右左双旋
	void RotateRL(Node* pParent)
	{  
		Node* parent = pParent;
		Node* pr = parent->_pRight;
		Node* prl = pr->_pLeft;
		int bf = prl->_bf;

		RotateL(pParent->_pRight);
		RotateR(pParent);

		//更新平衡因子

		if (bf == 0)
		{
			parent->_bf = pr->_bf = prl->_bf = 0;
		}
		else
		{
			parent->_bf = -1;
			pr->_bf = prl->_bf = 0;
		}


	}
	// 左右双旋
	void RotateLR(Node* pParent)
	{
		Node* parent = pParent;
		Node* pl= parent->_pLeft;
		Node* plr = pl->_pRight;
		int bf = plr->_bf;

	
		RotateR(pParent->_pLeft);
		RotateL(pParent);
		//更新平衡因子

		if (bf == 0)
		{
			parent->_bf = pl->_bf = plr->_bf = 0;
		}
		else
		{
			parent->_bf = 0;
			pl->_bf = 1;
			plr->_bf = 0;
		}
	}



	// 在AVL树中插入值为data的节点
	bool Insert(const T& data)
	{
		if (_pRoot == nullptr)
		{
			_pRoot = new Node(data);
			return true;
		}

		Node* cur = _pRoot;
		Node* parent = nullptr;
		//查看插入位置
		while (cur)
		{
			if (cur->_data < data)
			{   
				parent = cur;
				cur = cur->_pRight;
			}
			else if (cur->_data > data)
			{  
				parent = cur;

				cur = cur->_pLeft;
			}
			else
			{
				//有重复值，插入失败
				return false;
			}


		}

		//此时parent的子树就是存放data的结点
		if (parent->_data < data)
		{
			cur = new Node(data);
			parent->_pRight = cur;
			cur->_pParent = parent;
			parent->_bf++;

		}
		else
		{
			cur = new Node(data);
			parent->_pLeft = cur;
			cur->_pParent = parent;
			parent->_bf--;
		}



		//开始旋转
		while (parent)
		{
			if (parent->_bf == 0)
			{
				//代表插入前后高度不变
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//插入后高度改变，但仍保持平衡条件
				cur = parent;
				parent = parent->_pParent;
				if (parent == nullptr)
				{
					break;
				}
				if (cur == parent->_pLeft)
				{
					parent->_bf--;
				}
				else
				{
					parent->_bf++;
				}

			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//此时不满足平衡条件，需要旋转
				//旋转分四种情况
				//1.右右
				if(parent->_bf==2&&cur->_bf==1)
				RotateR(parent);
				//2。左左
				else if(parent->_bf == -2 && cur->_bf == -1)
				RotateL(parent);
				//3.右左
				else if(parent->_bf == 2 && cur->_bf == -1)
				RotateRL(parent);
				//4.左右
				else if(parent->_bf == -2 && cur->_bf == 1)
				RotateLR(parent);

				//旋转后高度和插入前高度相同，因此结束
				break;

			}
			else
			{
				//此时平衡因子异常，发出中断请求
				assert(false);
			}




		}



	}

对于一个结点的插入，其影响其父节点的平衡因子（_bf）的值，因此每次插入都需要修改其父节点的平衡因子，而父节点的平衡因子的修改又可能会影响父节点的父节点的平衡因子的值，因此可能会出现连锁修改的情况。以下是所有可能的情况：

1.插入结点后父节点的平衡因子的值变为0，在该情况下父节点的高度在插入前后未发生改变，因此不会继续影响父节点的父节点，因此可以直接退出循环。

2.插入结点后父节点的平衡因子的值变为1或-1，在该情况下父节点的高度插入前后发生修改，增加1，此处通过判断父节点是其父节点的左右子树，来影响父节点的父节点的平衡因子，并继续进入循环进行判断。

3。插入后父节点平衡因子变成大于2的情况，此时抛出异常，因为父节点的平衡因子应符合不超过2，即使在插入新节点后，其平衡因子最大只能增加1，最小只能减小1，因此只能变成绝对值小于等于2的情况，不应该出现绝对值大于2的情况。

3.插入结点后父节点平衡因子变成2或-2，此时不在符合平衡因子绝对值不超过2的情况，因此需要对以父节点为根结点的子树进行旋转修改。此时又分成四种情况。

情况1：