【C++】“旋转！跳跃！我闭着眼！”—— 从零开始构建AVL树

template<class K, class V>
struct AVLtreeNode
{	
	typedef AVLtreeNode<K, V> Node;
	//三叉树结构
	Node* _parent;
	Node* _left;
	Node* _right;
	//键值对
	pair<K, V> _kv;
	//平衡因子
	int _bf;

	AVLtreeNode(pair<K, V> kv)
		:_parent(nullptr)
		,_right(nullptr)
		,_left(nullptr)
/*
* 提示：该行代码过长，系统自动注释不进行高亮。一键复制会移除系统注释 
* ,_kv(kv)
*/
		,_bf(0)
	{
	}
};

bool Insert(pair<K, V> kv)
{
	Node* node = new Node(kv);
	//如果为空直接赋值
	if (_root == nullptr)
	{
		_root = node;
		return true;
	}
	//反之寻找插入位置（按照 key 比较大小）
	else
	{
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur != nullptr)
		{
			parent = cur;
			if (cur->_kv.first > kv.first)
			{
				cur = cur->_left;
			}
			else if(cur->_kv.first < kv.first)
			{
				cur = cur->_right;
			}
			else
			{
				//二叉搜索树默认不重复数据
				return false;
			}
		}
		//按照大小插入节点
		if (kv.first > parent->_kv.first)
		{
			parent->_right = node;
		}
		else
		{
			parent->_left = node;
		}
		//记得要处理父指针！！！
		node->_parent = parent;
		cur = node;
		//更新平衡因子
		//...
	}
}

//...
//处理平衡因子
//更新平衡因子
while (parent != nullptr)
{
	if (cur == parent->_left)
	{
		//左子树增加 父节点平衡因子--
		parent->_bf--;
	}
	else
	{
		//右子树增加 父节点平衡因子++
		parent->_bf++;
	}

	//为零直接退出
	if (parent->_bf == 0)
	{
		break;
	}
	//为 1 或 -1 继续向上进行
	else if (parent->_bf == 1 || parent->_bf == -1)
	{
		cur = parent;
		parent = cur->_parent;
	}
	//旋转来哩！！！
	else if (parent->_bf == 2 || parent->_bf == -2)
	{
		//分类旋转
		
		//旋转之后二叉树平衡！
		break;
	}
	//特殊情况处理 因为未来不知道会出什么bug ,在这里截断一下
	else
	{
		cout << "错误！！！" << endl;
		assert(false);
	}
}

void RotateR(Node* parent)
{
	Node* subL  = parent->_left;   //左子节点
	Node* subLR = subL->_right;  //左节点的右节点
	Node* ppNode = parent->_parent;//爷爷节点

	subL->_right = parent;
	parent->_parent = subL;

	parent->_left = subLR;
	if (subLR != nullptr)
		subLR->_parent = parent;

	//处理爷爷节点
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		//保证爷爷节点的指向正确
		if (parent == ppNode->_left)
		{
			ppNode->_left = subL;
		}
		else
		{
			ppNode->_right = subL;
		}

		subL->_parent = ppNode;
	}
	//处理平衡因子 因为已经平衡了 所以都为 0 
	parent->_bf = 0;
	subL->_bf = 0;
}

//左右双旋
void RotateLR(Node* parent)
{
	//先记录相关信息
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	//需要通过subLR来确定平衡因子
	int bf = subLR->_bf;
	//进行旋转
	//左单旋 subL
	RotateL(subL);
	//右单旋 parent
	RotateR(parent);
	//平衡因子需要调整！！！
	//在subLR的左子树插入 
	if (bf == -1)
	{
		//右单旋 parent 会将subLR的右子树给parent的左边 ，parent左边比右边低
		parent->_bf = 1;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	//在subLR的右子树插入 
	else if (bf == 1)
	{
		parent->_bf = 0;
		//左单旋 subL 会将subLR的左子树给subL的右边 ，subL左边比右边高
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	//如果subLR自身是插入的节点
	else if (bf == 0)
	{
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else
	{
		//出错了
		assert(false);
	}

}

//插入节点
bool Insert(pair<K, V> kv)
{
	Node* node = new Node(kv);
	//如果为空直接赋值
	if (_root == nullptr)
	{
		_root = node;
		return true;
	}
	//反之寻找插入位置（按照 key 比较大小）
	else
	{
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur != nullptr)
		{
			parent = cur;
			if (cur->_kv.first > kv.first)
			{
				cur = cur->_left;
			}
			else if(cur->_kv.first < kv.first)
			{
				cur = cur->_right;
			}
			else
			{
				//二叉搜索树默认不重复数据
				return false;
			}
		}
		//cur = node;

		if (kv.first > parent->_kv.first)
		{
			parent->_right = node;
		}
		else
		{
			parent->_left = node;
		}

		node->_parent = parent;
		cur = node;
		//更新平衡因子
		while (parent != nullptr)
		{
			if (cur == parent->_left)
			{
				//左子树增加 父节点平衡因子--
				parent->_bf--;
			}
			else
			{
				//右子树增加 父节点平衡因子++
				parent->_bf++;
			}

			//为零直接退出
			if (parent->_bf == 0)
			{
				break;
			}
			//为 1 或 -1 继续向上进行
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = cur->_parent;
			}
			//旋转来哩
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//分类旋转
				
				if (parent->_bf == -2 && cur->_bf == -1)
				{
					//右单旋
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					//左单旋
					RotateL(parent);
				}
				//需要双旋的情况
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				//旋转之后二叉树平衡！
				break;
			}
			//特殊情况处理
			else
			{
				cout << "错误！！！" << endl;
				assert(false);
			}
		}
	}
}

	//寻找节点
	bool Find(K key)
	{
		Node* cur = _root;
		while (cur != nullptr)
		{
			if (key == cur->_kv.first)
			{
				return true;
			}
			else if (key < cur->_kv.first)
			{
				cur = cur->_left;
			}
			else
			{
				cur = cur->_right;
			}
		}
		return false;
	}

//删除节点
bool Erase(K key)
{
	Node* cur = _root;
	Node* parent = nullptr;

	//记录需要删除的节点
	Node* DelParentPos = nullptr;
	Node* DelPos = nullptr;
	//寻找替换值

	//寻找需要被删除的节点
	while (cur != nullptr)
	{
		
		if (key > cur->_kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (key < cur->_kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			//现在找到了需要被删除的节点
			// 
			//删除需要涉及平衡因子的改变
			//父指针的修正
			// 根据需要删除节点的状态分出以下4种状态：
			//a.要删除的结点无孩子结点
			//b.要删除的结点只有左孩子结点
			//c.要删除的结点只有右孩子结点
			//d.要删除的结点有左、右孩子结点

			//平衡因子的修正比较复杂 所以不能直接删除的情况要进行虚拟删除
			if (cur->_left == nullptr || cur->_right == nullptr)
			{
				if (cur->_left == nullptr)
				{
					//如果删除的的是根节点，单独处理
					if (cur == _root)
					{
						_root = cur->_right;
						if(cur->_right)
							cur->_right->_parent = nullptr;
						delete cur;
					}
					//只要有祖先节点就要进行平衡因子的处理！！！ 先虚拟删除
					else
					{
						DelParentPos = parent; //标记实际删除结点的父结点
						DelPos = cur; //标记实际删除的结点
					}
				}
				else
				{
					//如果删除的的是根节点，单独处理
					if (cur == _root)
					{
						_root = cur->_left;
						cur->_left->_parent = nullptr;
						delete cur;
					}
					else
					{
						DelParentPos = parent; //标记实际删除结点的父结点
						DelPos = cur; //标记实际删除的结点
					}
				}
				break;
			}
			//d.要删除的结点有左、右孩子结点
			//替换法 + 虚拟删除
			else
			{
				Node* rightMin = nullptr;
				Node* rightMinParent = cur;
				//寻找右子树最小值
				rightMin = cur->_right;
				rightMinParent = cur;
				while (rightMin->_left != nullptr)
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;
				}
				//找到可以替换的节点
				//交换键值对
				swap(cur->_kv, rightMin->_kv);
				//把要删除的节点记录下来，模拟删除
				DelParentPos = rightMinParent;
				DelPos = rightMin;
				break;
			}
		}
	}
	//没有找到的情况
	if (DelParentPos == nullptr) return false;
	parent = DelParentPos;
	cur = DelPos;

	//然后更新平衡因子
	while (cur != _root)
	{
		if (cur == parent->_left)
		{
			parent->_bf++;
		}
		else
		{
			parent->_bf--;
		}
		//根据不同结果来处理
		// 为0说明该子树的高度改变 高度变低了 继续向上处理
		if (parent->_bf == 0)
		{
			cur = parent;
			parent = cur->_parent;
		}
		//为正负 1 说明该子树的高度没有改变 
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			break;
		}
		//出现 正负 2 说明需要进行旋转修正！
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			//分类讨论
			if (parent->_left->_bf == -1 && parent->_bf == -2)
			{
				//注意要及时更新parent根节点，不然无法顺利向上推进
				//cur 节点经过旋转 指向依然正确，是parnet的子树
				Node* tmp = parent->_left;
				RotateR(parent);
				parent = tmp;
			}
			else if (parent->_left->_bf == 1 && parent->_bf == -2)
			{
				Node* tmp = parent->_left->_right;
				RotateLR(parent);
				parent = tmp;
			}
			else if (parent->_left->_bf == 0 && parent->_bf == -2)
			{
				Node* tmp = parent->_left;
				RotateR(parent);
				parent = tmp;

				parent->_bf = 1;
				parent->_right->_bf = -1;
				//此时 parent 的平衡因子为 1 说明该树删除后高度没有改变，所以不在需要向上更新
				break;
			}
			else if (parent->_right->_bf == -1 && parent->_bf == 2)
			{
				Node* tmp = parent->_right->_left;
				RotateRL(parent);
				parent = tmp;
			}
			else if (parent->_right->_bf == 1 && parent->_bf == 2)
			{
				Node* tmp = parent->_right;
				RotateL(parent);
				parent = tmp;
			}
			else if (parent->_right->_bf == 0 && parent->_bf == 2)
			{
				Node* tmp = parent->_right;
				RotateL(parent);
				parent = tmp;
				parent->_bf = -1;
				parent->_left->_bf = 1;
				//此时 parent 的平衡因子为 -1 说明该树删除后高度没有改变，所以不在需要向上更新
				break;
			}
			//旋转的本质是将树的高度变低，所以parent树的高度一定会发生改变！
			//parent树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子！
			cur = parent;
			parent = cur->_parent;
		}
		else
		{
			cout << "旋转出现错误！" << endl;
			assert(false);
		}
	}
	//处理完平衡因子，现在可以开始删除节点了
	if (DelPos->_left == nullptr)
	{
		if (DelPos == DelParentPos->_left)
		{
			DelParentPos->_left = DelPos->_right;
			if (DelPos->_right)
				DelPos->_right->_parent = DelParentPos;
		}
		if (DelPos == DelParentPos->_right)
		{
			DelParentPos->_right = DelPos->_right;
			if (DelPos->_right)
				DelPos->_right->_parent = DelParentPos;
		}
	}
	else//右为空
	{
		if (DelPos == DelParentPos->_left)
		{
			DelParentPos->_left = DelPos->_left;
			if (DelPos->_left)
				DelPos->_left->_parent = DelParentPos;
		}
		if (DelPos == DelParentPos->_right)
		{
			DelParentPos->_right = DelPos->_left;
			if (DelPos->_left)
				DelPos->_left->_parent = DelParentPos;
		}
	}
	delete DelPos;//删除！！！
	return true;
}

bool IsBalance()
{
	return _IsBalance(_root);
}
int Height()
{
	return _Height(_root);
}
bool _IsBalance(Node* root) 
{
	//按照高度进行检查
	if (root == nullptr) return true;
	if (abs(_Height(root->_left) - _Height(root->_right) ) >= 2) return false;
	return _IsBalance(root->_left) && _IsBalance(root->_right);
}
int _Height(Node* root)
{
	if (root == nullptr) return 0;
	return max(_Height(root->_left) + 1, _Height(root->_right) + 1);
}

void AVLTreeTest3()
{
	const int N = 10000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}

	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
		//验证过程中是否平衡
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	cout << t.IsBalance() << endl;
	size_t end2 = clock();

	cout << "Insert:" << end2 - begin2 << endl;
	cout << t.IsBalance() << endl;

	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;
}

void AVLTreeTest6()
{
	const int N = 100000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}

	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	cout << t.IsBalance() << endl;
	size_t end2 = clock();

	cout << "Insert:" << end2 - begin2 << endl;

	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;

	size_t begin1 = clock();
	// 确定在的值
	for (auto e : v)
	{
		t.Find(e);
	}
	// 随机值
	//for (size_t i = 0; i < N; i++)
	//{
	//	t.Find((rand() + i));
	//}

	size_t end1 = clock();

	cout << "Find:" << end1 - begin1 << endl;
	size_t begin3 = clock();
	for (auto e : v)
	{
		t.Erase(e);
	}
	size_t end3 = clock();
	cout << "Erase:" << end3 - begin3 << endl;
}