数据结构备忘录：保证avl树删除插入操作正确性的原理的讨论及插入删除操作的实现

#include <vector>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <random>
#include <ctime>
using namespace std;

#define TYPE int
template <typename T>
struct   //AVL树节点类
{
	int bf;  
	T data;  //节点数据域
	AVLNode* left;
	AVLNode* right;
	AVLNode(int b, T d) :bf(b), data(d), left(nullptr), right(nullptr) {}
};

template <typename T>
void RotateLR(AVLNode<T>*& ptr)  //对以ptr为根的子树执行先左后右双旋转,ptr成为旋转后新树根节点指针
{
	AVLNode<T>* p = ptr->left;
	AVLNode<T>* q = p->right;
	p->right = q->left;
	q->left = p;
	ptr->left = q->right;
	q->right = ptr;
	if (q->bf == 0)
	{
		p->bf = ptr->bf = 0;
	}
	else
	{
		if (q->bf == -1)
		{
			p->bf = 0;
			ptr->bf = 1;
		}
		else
		{
			p->bf = -1;
			ptr->bf = 0;
		}
		q->bf = 0;
	}
	ptr = q;
}

template <typename T>
void RotateRL(AVLNode<T>*& ptr)  //对以ptr为根的子树执行先右后左双旋转,ptr成为旋转后新树根节点指针
{
	AVLNode<T>* p = ptr->right;
	AVLNode<T>* q = p->left;
	p->left = q->right;
	q->right = p;
	ptr->right = q->left;
	q->left = ptr;
	if (q->bf == 0)
	{
		p->bf = ptr->bf = 0;
	}
	else
	{
		if (q->bf == -1)
		{
			p->bf = 1;
			ptr->bf = 0;
		}
		else
		{
			p->bf = 0;
			ptr->bf = -1;
		}
		q->bf = 0;
	}
	ptr = q;
}

template <typename T>
void RotateR(AVLNode<T>*& ptr)  //对以ptr为根的子树执行右单旋转,ptr成为旋转后新树根节点指针
{
	AVLNode<T>* p = ptr->left;
	ptr->left = p->right;
	p->right = ptr;
	if (p->bf == -1)
	{
		p->bf = ptr->bf = 0;
	}
	else
	{
		p->bf = 1;
	}
	ptr = p;
}

template <typename T>
void RotateL(AVLNode<T>*& ptr)  ////对以ptr为根的子树执行左单旋转,ptr成为旋转后新树根节点指针
{
	AVLNode<T>* p = ptr->right;
	ptr->right = p->left;
	p->left = ptr;
	if (p->bf == 0)
	{
		p->bf = -1;
		ptr->bf = 1;
	}
	else
	{
		ptr->bf = p->bf = 0;
	}
	ptr = p;
}

template <typename T>
bool isAVL(AVLNode<T>* root)  //判断以root为根节点的二叉树是否为AVL树
{
	struct temp
	{
		T lmin;  //节点左子树中最小节点值
		T lmax;  //节点左子树中最大节点值
		T rmin;  //节点右子树中最小节点值
		T rmax;  //节点右子树中最大节点值
	};
	struct memory
	{
		AVLNode<T>* p;
		int direction;
		temp minmax;
		int lh = 0;   //节点左子树高度
		int rh = 0;   //节点右子树高度
		memory(AVLNode<T>* p, int d) :p(p), direction(d) {}
	};
	int d = 0;
	AVLNode<T>* ptr = root;
	AVLNode<T>* const dest = ptr;
	stack<memory> arrange;
	bool TF = false;
	while (true)
	{
		if (Searchd(ptr, d) == 0)
		{
			if (ptr == dest)
			{
				if (d == 0)
					return true;
				else
				{
					if (ptr->left == nullptr || ptr->right != nullptr)
					{
						if (ptr->data < arrange.top().minmax.rmin)
						{
							if (abs(arrange.top().rh - arrange.top().lh) > 1)
							{
								cout << "存在左右子树高度差绝对值大于一的子树,原树非AVL树" << endl;
								return false;
							}
							arrange.pop();
						}
						else
						{
							cout << "当前树非二叉搜索树,也非AVL树" << endl;
							return false;
						}
					}
					else
					{
						if (ptr->data > arrange.top().minmax.lmax)
						{
							if (abs(arrange.top().rh - arrange.top().lh) > 1)
							{
								cout << "存在左右子树高度差绝对值大于一的子树,原树非AVL树" << endl;
								return false;
							}
							arrange.pop();
						}
						else
						{
							cout << "当前树非二叉搜索树,也非AVL树" << endl;
							return false;
						}
					}
					return true;
				}
			}
			else
			{
				if (d == 0)
				{
					if (arrange.top().direction == 1)
					{
						arrange.top().lh = 1;
						arrange.top().minmax.lmin = ptr->data;
						arrange.top().minmax.lmax = ptr->data;
					}
					else
					{
						arrange.top().rh = 1;
						arrange.top().minmax.rmin = ptr->data;
						arrange.top().minmax.rmax = ptr->data;
					}
				}
				else
				{
					if (ptr->left == nullptr || ptr->right != nullptr)
					{
						if (ptr->data < arrange.top().minmax.rmin)
						{
							temp temp1 = arrange.top().minmax;
							int leftheight = arrange.top().lh;
							int rightheight = arrange.top().rh;
							arrange.pop();

							if (arrange.top().direction == 1)
							{
								if (ptr->left == nullptr)
								{
									arrange.top().minmax.lmin = ptr->data;
								}
								else
								{
									arrange.top().minmax.lmin = temp1.lmin;
								}
								arrange.top().minmax.lmax = temp1.rmax;

								if (abs(rightheight - leftheight) > 1)
								{
									cout << "存在左右子树高度差绝对值大于一的子树,原树非AVL树" << endl;
									return false;
								}
								else
								{
									arrange.top().lh = max(leftheight, rightheight) + 1;
								}
							}
							else
							{
								if (ptr->left == nullptr)
								{
									arrange.top().minmax.rmin = ptr->data;
								}
								else
								{
									arrange.top().minmax.rmin = temp1.lmin;
								}
								arrange.top().minmax.rmax = temp1.rmax;

								if (abs(rightheight - leftheight) > 1)
								{
									cout << "存在左右子树高度差绝对值大于一的子树,原树非AVL树" << endl;
									return false;
								}
								else
								{
									arrange.top().rh = max(leftheight, rightheight) + 1;
								}
							}
						}
						else
						{
							cout << "当前树非二叉搜索树,也非AVL树" << endl;
							return false;
						}
					}
					else
					{
						if (ptr->data > arrange.top().minmax.lmax)
						{
							temp temp1 = arrange.top().minmax;
							int leftheight = arrange.top().lh;
							int rightheight = arrange.top().rh;
							arrange.pop();
							if (arrange.top().direction == 1)
							{
								arrange.top().minmax.lmin = temp1.lmin;
								arrange.top().minmax.lmax = ptr->data;

								if (abs(rightheight - leftheight) > 1)
								{
									cout << "存在左右子树高度差绝对值大于一的子树,原树非AVL树" << endl;
									return false;
								}
								else
								{
									arrange.top().lh = max(leftheight, rightheight) + 1;
								}
							}
							else
							{
								arrange.top().minmax.rmin = temp1.lmin;
								arrange.top().minmax.rmax = ptr->data;

								if (abs(rightheight - leftheight) > 1)
								{
									cout << "存在左右子树高度差绝对值大于一的子树,原树非AVL树" << endl;
									return false;
								}
								else
								{
									arrange.top().rh = max(leftheight, rightheight) + 1;
								}
							}
						}
						else
						{
							cout << "当前树非二叉搜索树,也非AVL树" << endl;
							return false;
						}
					}
				}
				ptr = arrange.top().p;
				d = arrange.top().direction;
			}
		}
		else
		{
			AVLNode<T>* interval = nullptr;
			if (d == 0)
			{
				arrange.push(memory(ptr, Searchd(ptr, d)));
				if (arrange.top().direction == 1)
					interval = ptr->left;
				else
					interval = ptr->right;
			}
			else
			{
				if (!(ptr->data > arrange.top().minmax.lmax))
				{
					cout << "当前树非二叉搜索树,也非AVL树" << endl;
					return false;
				}
				arrange.top().direction = 2;
				interval = ptr->right;
			}
			d = 0;
			ptr = interval;
		}
	}
}

template <typename T>
void linkWithUpper(AVLNode<T>* parent, AVLNode<T>* original, AVLNode<T>* _new)
{
	if (original == parent->left)
	{
		parent->left = _new;
	}
	else
	{
		parent->right = _new;
	}
}

template <typename T>
AVLNode<T>* DelAVL(AVLNode<T>* root, T key)  //在以root为根节点的AVL树中删除关键码key
{
	//AVL树的删除
	AVLNode<T>* p = root;
	stack<AVLNode<T>*> stackforflashback;
	while (p != nullptr)         //搜索被删除节点,同时将回溯路径记录在栈中
	{
		if (p->data == key)
			break;
		else
		{
			stackforflashback.push(p);
			if (key < p->data)
			{
				p = p->left;
			}
			else
			{
				p = p->right;
			}
		}
	}

	if (p != nullptr)  //被删除节点存在,被p指向
	{
		AVLNode<T>* parent = nullptr;
		AVLNode<T>* q = nullptr;
		if (p->left != nullptr && p->right != nullptr)   //被删节点左右子树均存在
		{
			q = p->right;
			if (q->left != nullptr)   //被删节点右子树根节点有左子树
			{
				parent = p;
				stackforflashback.push(parent);
				while (q->left != nullptr)  //在被删节点右子树根节点左子树中搜索中序遍历的第一个节点,同时用栈记录回溯路径
				{
					parent = q;
					q = q->left;
					if (q->left != nullptr)
						stackforflashback.push(parent);
				}
				parent->left = q->right;  //用该节点数据域替换被删节点数据域,将其右子树链接至其父节点左链指针,随后删除该节点
				p->data = q->data;
				delete q;
				q = parent->left; //parent为需要做或不做平衡化旋转的第一棵子树根节点指针,q为该子树左子树根节点指针

			}
			else
			{
				p->right = q->right;   //用被删节点右子女数据域替换被删节点指针域,将右子女右子树链接至被删节点右链指针,并删除右子女
				p->data = q->data;
				delete q;
				parent = p;
				q = p->right;  //parent为需要做或不做平衡化旋转的第一棵子树根节点指针,q为该子树左子树根节点指针
			}
		}
		else
		{
			if (p->left != nullptr)  //被删节点左子树不空,右子树空
			{
				if (stackforflashback.empty() == false)  //被删节点有父节点
				{
					parent = stackforflashback.top();
					stackforflashback.pop();
					if (parent->left == p)
					{
						parent->left = p->left;
						delete p;
						q = parent->left;
					}                     //将被删节点左子树链接至被删节点父节点相应链指针，并删除被删节点
					else
					{
						parent->right = p->left;
						delete p;
						q = parent->right;
					}                          //parent为需要做或不做平衡化旋转的第一棵子树根节点指针,q为该子树左子树根节点指针
				}
				else
				{
					parent = p->left;
					delete p;         //删除被删节点后原AVL树恢复平衡,parent为根节点结束
					return parent;
				}
			}
			else if (p->right != nullptr)  //处理过程和以上情形完全对称
			{
				if (stackforflashback.empty() == false)
				{
					parent = stackforflashback.top();
					stackforflashback.pop();
					if (parent->left == p)
					{
						parent->left = p->right;
						delete p;
						q = parent->left;
					}
					else
					{
						parent->right = p->right;
						delete p;
						q = parent->right;
					}               //parent为需要做或不做平衡化旋转的第一棵子树根节点指针,q为该子树左子树根节点指针
				}
				else
				{
					parent = p->right;
					delete p;   //删除被删节点后原AVL树恢复平衡,parent为根节点结束
					return parent;
				}
			}
			else        //被删节点为叶节点
			{
				if (stackforflashback.empty() == false)   //被删叶节点有父节点
				{
					parent = stackforflashback.top();
					stackforflashback.pop();
					if (parent->left == p)
					{
						parent->left = nullptr;
						delete p;
						q = parent->left;
					}
					else                          //删除叶节点并将其父节点对应指针域置空
					{
						parent->right = nullptr;
						delete p;
						q = parent->right;
					}                        //parent为需要做或不做平衡化旋转的第一棵子树根节点指针,q为该子树左子树根节点指针
				}
				else
				{
					parent = nullptr;
					delete p;       //删除被删节点后原AVL树恢复平衡,parent为根节点结束
					return parent;
				}
			}
		}
		bool TF = false;
		do
		{
			if (TF == true)
				stackforflashback.pop();
			else
				TF = true;

			if ((parent->bf == 1 || parent->bf == -1) && q == nullptr && parent->right == nullptr && parent->left == nullptr)
			{
				parent->bf = 0;
				if (stackforflashback.empty() == false)
				{
					q = parent;
					parent = stackforflashback.top();
					continue;
				}
				else
				{
					return root;
				}

			}

			if (parent->left == q)
			{
				if (parent->bf == 0)
				{
					parent->bf = 1;   //情形a
					return root;
				}
				else if (parent->bf == -1)
				{
					parent->bf = 0;
					q = parent;
					if (stackforflashback.empty() == false)
					{
						parent = stackforflashback.top();   //情形b                           
					}
				}
				else
				{
					p = parent->right;
					q = parent;
					if (p->bf == 0)
					{                            //情形c
						if (stackforflashback.empty() == false)
						{
							RotateL(parent);//对以parent为根的子树执行左单旋转
							linkWithUpper(stackforflashback.top(), q, parent);
						}
						else
						{
							RotateL(parent);//对以parent为根的子树执行左单旋转
						}
						if (q == root)
						{
							return parent;
						}
						else
						{
							return root;
						}
					}
					else if (p->bf == 1)   //情形d
					{
						RotateL(parent);//对以parent为根的子树执行左单旋转
					}
					else            //情形e
					{
						RotateRL(parent);//对以parent为根的子树执行先右后左双旋转
					}

					if (stackforflashback.empty() == false)
					{
						linkWithUpper(stackforflashback.top(), q, parent);
						q = parent;
						parent = stackforflashback.top();
					}
					else
					{
						q = parent;
					}
				}
			}
			else
			{
				if (parent->bf == 0)  //情形a*
				{
					parent->bf = -1;
					return root;
				}
				else if (parent->bf == 1)   //情形b*
				{
					parent->bf = 0;
					q = parent;
					if (stackforflashback.empty() == false)
					{
						parent = stackforflashback.top();   //情形b                        
					}
				}
				else
				{
					p = parent->left;
					q = parent;
					if (p->bf == 0)          //情形c*
					{
						if (stackforflashback.empty() == false)
						{
							RotateR(parent);//对以parent为根的子树执行右单旋转
							linkWithUpper(stackforflashback.top(), q, parent);
						}
						else
						{
							RotateR(parent);//对以parent为根的子树执行右单旋转
						}
						if (q == root)
						{
							return parent;
						}
						else
						{
							return root;
						}
					}
					else if (p->bf == -1)    //情形d*
					{
						RotateR(parent);//对以parent为根的子树执行右单旋转
					}
					else    //情形e*
					{
						RotateLR(parent);//对以parent为根的子树执行先左后右双旋转
					}

					if (stackforflashback.empty() == false)
					{
						linkWithUpper(stackforflashback.top(), q, parent);
						q = parent;
						parent = stackforflashback.top();
					}
					else
					{
						q = parent;
					}
				}
			}
		} while (stackforflashback.empty() == false);
		return q;   //原AVL树已恢复平衡,返回根节点
	}
	else
	{
		cout << "AVL树中不存在要删除的数据元素,删除失败" << endl;
		return nullptr;
	}
}

template <typename T>
AVLNode<T>* InsertAVL(AVLNode<T>* root, T key)
{
	//AVL树的插入
	if (root == nullptr)
		return new AVLNode<T>(0, key);
	else
	{
		stack<AVLNode<T>*> stackforflashback;
		AVLNode<T>* p = root;
		while (p != nullptr)   //搜索插入位置
		{
			stackforflashback.push(p);
			if (key < p->data)
				p = p->left;
			else if (key > p->data)
				p = p->right;
			else
			{
				cout << "要插入的关键字在AVL树中已存在,插入失败" << endl;
				return nullptr;
			}
		}

		p = new AVLNode<T>(0, key);
		if (key < stackforflashback.top()->data)
		{
			stackforflashback.top()->left = p;   //新节点插入并调整父节点平衡因子
		}
		else
		{
			stackforflashback.top()->right = p;
		}

		AVLNode<T>* parent = nullptr;
		while (stackforflashback.empty() == false)
		{
			parent = stackforflashback.top();
			stackforflashback.pop();
			if (parent->left == p)
			{
				--parent->bf;
				if (parent->bf == 0)
				{
					return root;//已平衡,返回根节点
				}
				else if (parent->bf == -2)
				{
					AVLNode<T>* q = parent;
					if (p->bf == 1)
					{
						RotateLR(parent);//对parent为根的子树执行先左后右双旋转
									  //已平衡
					}
					else
					{
						RotateR(parent);//对以parent为根子树执行右单旋转
									 //已平衡
					}

					if (stackforflashback.empty() == false)
					{
						linkWithUpper(stackforflashback.top(), q, parent);
					}

					if (q == root)   //返回恢复平衡的AVL树根节点
						return parent;
					else
						return root;
				}
				else
				{
					p = parent;  //以parent为根的子树已平衡其高度加一回溯至父节点
				}
			}
			else
			{
				++parent->bf;
				if (parent->bf == 0)
				{
					//已平衡,返回根节点
					return root;
				}
				else if (parent->bf == 2)
				{
					AVLNode<T>* q = parent;
					if (p->bf == -1)
					{
						RotateRL(parent);//对parent为根的子树执行先右后左双旋转
										 //已平衡
					}
					else
					{
						RotateL(parent);//对以parent为根的子树执行左单旋转
										//已平衡
					}

					if (stackforflashback.empty() == false)
					{
						linkWithUpper(stackforflashback.top(), q, parent);
					}
					if (q == root)     //返回恢复平衡的AVL树根节点
						return parent;
					else
						return root;
				}
				else
				{
					p = parent;  //以parent为根的子树已平衡其高度加一回溯至父节点
				}
			}
		}
		return p;   //原AVL树已平衡,返回根节点
	}
}

template <typename T>
int Searchd(AVLNode<T>* ptr, int d)
{
	if (d == 2)
		return 0;
	else
	{
		if (d == 1)
		{
			if (ptr->right == nullptr)
				return 0;
			else
				return 2;
		}
		else
		{
			if (ptr->left != nullptr)
				return 1;
			else
			{
				if (ptr->right != nullptr)
					return 2;
				else
					return 0;
			}
		}
	}
}

template <typename T>
void output(AVLNode<T>* ptr)  //输出以ptr为根的AVL树对应的广义表形式
{
	struct memory
	{
		AVLNode<T>* p;
		int direction;
		int last;
		memory(AVLNode<T>* p, int d, int l) :p(p), direction(d), last(l) {}
	};
	int d = 0;
	AVLNode<T>* const dest = ptr;
	stack<memory> arrange;
	while (true)
	{
		if (Searchd(ptr, d) == 0)
		{
			if (ptr == dest)
			{
				if (d == 0)
					cout << ptr->data << "(";
				else
				{
					if (arrange.top().last == 1)
						cout << ", ";
				}
				cout << ")";
				break;
			}
			else
			{
				if (d == 0)
				{
					if (arrange.top().last == 0)
					{
						if (arrange.top().direction == 1)
						{
							cout << ptr->data;
							arrange.top().last = 1;
						}
						else
						{
							cout << " ," << ptr->data;
							arrange.top().last = 2;
						}
					}
					else
					{
						cout << ",";
						cout << ptr->data;
						arrange.top().last = 2;
					}
				}
				else
				{
					if (arrange.top().last == 2)
						cout << ")";
					else
					{
						cout << ", )";
					}
					arrange.pop();
				}
				ptr = arrange.top().p;
				d = arrange.top().direction;
			}
		}
		else
		{
			AVLNode<T>* interval = nullptr;
			if (d == 0)
			{
				if (arrange.empty() == false)
				{
					if (arrange.top().last == 0)
					{
						if (arrange.top().direction == 1)
						{
							cout << ptr->data << "(";
							arrange.top().last = 1;
						}
						else
						{
							cout << " ," << ptr->data << "(";
							arrange.top().last = 2;
						}
					}
					else
					{
						cout << ",";
						cout << ptr->data << "(";
						arrange.top().last = 2;
					}
				}
				else
				{
					cout << ptr->data << "(";
				}
				arrange.push(memory(ptr, Searchd(ptr, d), 0));
				if (arrange.top().direction == 1)
					interval = ptr->left;
				else
					interval = ptr->right;
			}
			else
			{
				arrange.top().direction = 2;
				interval = ptr->right;
			}
			d = 0;
			ptr = interval;
		}
	}
}
int main()
{
	const int N = 20;
	//vector<TYPE> insertvalue{ 13, 5, 3, 2, 1, 4, 10, 8, 7, 6, 9, 11, 12, 16, 14, 15, 18, 17, 20, 19 };
	vector<TYPE> insertvalue;
	for (int i = 1; i <= N; ++i)
	{
		insertvalue.push_back(i);
	}

	shuffle(insertvalue.begin(), insertvalue.end(), default_random_engine(time(nullptr)));
	AVLNode<TYPE>* root = nullptr;
	for (vector<TYPE>::const_iterator p = insertvalue.cbegin(); p != insertvalue.cend(); ++p)
	{
		cout << "插入节点" << *p << endl;
		root = InsertAVL(root, *p);
		output(root);
		cout << endl;
		if (isAVL(root) == true)
		{
			cout << "当前树是AVL树";
			cout << endl;
		}
		else
		{
			cerr << "错误当前树不是AVL树!" << endl;
			exit(0);
		}
	}
	cout << endl;
	cout << "插入完成后删除前AVL树对应的广义表形式为:" << endl;
	output(root);
	cout << endl;
	cout << endl;
	for (vector<TYPE>::const_iterator p = insertvalue.cbegin(); p != insertvalue.cend(); ++p)
	{
		cout << "删除节点" << *p << endl;
		root = DelAVL(root, *p);
		if (root != nullptr)
		{
			output(root);
			cout << endl;
			if (isAVL(root) == true)
			{
				cout << "当前树是AVL树";
				cout << endl;
			}
			else
			{
				cerr << "错误当前树不是AVL树!" << endl;
				exit(0);
			}
		}
		else
			cout << "NULL";
		cout << endl;
	}
	return 0;
}