C++中“AVL”树的模拟实现以及实现中遇见的问题

1. insert
2. 如何判断你的AVL树符合规则
- 高度平衡
- 平衡因子是否正确
- 开始检查
3.最终代码

高度平衡二叉搜索树

1. insert

一、先按照搜索树的规则找到插入点
二、插入数据
三、此时的树会发生变化
但是：
（1）在没有插入这个节点的时候，这个树还是高度平衡的，也就是说这个树的所有节点的平衡因子都是0或者1
（2）因为这个节点的插入，这个节点的所有父节点都会发生变化，我们按照规则将其（这些父节点的bf）重新赋值
1.curparent->left parent->bf–;
2.curparent->right parent->bf++:
3.更新以后，parent->bf0,更新结束。
说明：更新前parent->bf 是1或者-1，现在变成0，说明填上矮的那边，parent所在的子树高度不变
4.更新之后，parent->bf1/-1 继续往上更新。
说明：更新前，parent->bf 是0，现在变成1或者-1，我有一边变高了，parent所在的子树高度变了
5.更新以后，parent->bf==2/-2,parent所在子树已经不平衡了，需要旋转处理。
四、关于旋转处理

个人对这个旋转处理的理解：

一共四种情况，如果出现第五种情况，那么只能说明你的上一次旋转处理，处理的有问题，也就是你的代码写的有问题
比较难理解的是第一个和第三个
第一个
需要变动的线，也就只有这两条，建议仔细观看这两条线段的变化，最好自己画一下，（不知道怎么说）
第三个需要变动的只是这三条线段，这三个线段的前世今生我也标记出来了

温馨提醒：这个代码有问题，但是整体思路是符合上述分析的那些点的

	bool Insert(const pair& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while(cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else{
			parent->_left = cur;
			cur->_parent = parent;
		}
		//cur新增，只会影响cur祖先节点的平衡因子
		//控制平衡
		//1.更新平衡因子---新增节点到根节点的祖先路径
		//2.出现异常的平衡因子，就需要旋转平衡处理
		while (parent)
		{
			if (cur == parent->_left)
				parent->_bf--;
			else
				parent->_bf++;

			if (parent->_bf == 0)
				break;
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//继续往上更新
				cur = parent;
				parent = parent->_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);
				}
				else
				{
					assert(false);
				}

				break;

			}
			else
			{
				//说明插入更新平衡因子之前，树中的平衡因子就有问题了
				assert(false);
			}
		}
		return true;
	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		Node* parentParent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		if (_root == parent){
			_root = subR;
			subR->_parent = nullptr;
		}
		else{
			if (parentParent->_left == parent)
				parentParent->_left = subR;
			else
				parentParent->_right = subR;
			subR->_parent = parentParent;
		}
		subR->_bf = parent->_bf = 0;
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if(subLR) subLR->_parent = parent;//subLR可能为空
		Node* parentparent = parent->_parent;

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

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentparent->_left == parent)
				parentparent->_left = subL;
			else
				parentparent->_right = subL;
			subL->_parent = parentparent;
		}
		subL->_bf = 0;
		parent->_bf = 0;
	}
	void RotateLR(Node* parent)
	{
		RotateL(parent->_left);
		RotateR(parent);
	}

	void RotateRL(Node* parent)
	{
		RotateR(parent->_right);
		RotateL(parent);
	}

最终理解草图：

2. 如何判断你的AVL树符合规则高度平衡

1.检查平衡因子？
不行，
因为平衡因子是你规定的，在你的代码中可能会直接设置的“正确”
2.检查高度？

	int Height(Node* root)
	{
		if (root == nullptr) return 0;

		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		return max(leftHeight, rightHeight)+1;
	}

	bool IsBalance()//balance均衡
	{
		return _IsBalance(_root);
	}
	bool _IsBalance(Node* root)
	{
		if (root == NULL) return true;

		//对当前树进行检查
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		return abs(rightHeight - leftHeight) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

平衡因子是否正确

	bool _IsBalance(Node* root)
	{
		if (root == NULL) return true;

		//对当前树进行检查
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		if (rightHeight - leftHeight != root->_bf)
		{
			cout << root->_kv.first << "现在是:" << root->_bf << endl;
			cout << root->_kv.first << "应该是:" << rightHeight - leftHeight << endl;
			return false;
		}

		return abs(rightHeight - leftHeight) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

开始检查

当输入为：int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };

出现问题

解决步骤：

则可以推出是插入14时，出现问题

根据监控可以画出这个二叉树

可以推出是双旋出了问题
双旋分为两种类型，各自三种情况

	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		if (bf == 1)
		{
			parent->_bf = 0;
			subR->_bf = -1;
			subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

3.最终代码

#pragma once

template
struct AVLTreeNode 
{
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	pair _kv;

	int _bf;//balance factor 平衡因子

	AVLTreeNode(const pair& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_kv(kv)
	{}
};

template
class AVLTree
{
	typedef AVLTreeNode Node;
public:
	AVLTree()
		:_root(nullptr)
	{}

	bool Insert(const pair& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while(cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else{
			parent->_left = cur;
			cur->_parent = parent;
		}
		//cur新增，只会影响cur祖先节点的平衡因子
		//控制平衡
		//1.更新平衡因子---新增节点到根节点的祖先路径
		//2.出现异常的平衡因子，就需要旋转平衡处理
		while (parent)
		{
			if (cur == parent->_left)
				parent->_bf--;
			else
				parent->_bf++;

			if (parent->_bf == 0)
				break;
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//继续往上更新
				cur = parent;
				parent = parent->_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);
				}
				else
				{
					assert(false);
				}

				break;

			}
			else
			{
				//说明插入更新平衡因子之前，树中的平衡因子就有问题了
				assert(false);
			}
		}
		return true;
	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		Node* parentParent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		if (_root == parent){
			_root = subR;
			subR->_parent = nullptr;
		}
		else{
			if (parentParent->_left == parent)
				parentParent->_left = subR;
			else
				parentParent->_right = subR;
			subR->_parent = parentParent;
		}
		subR->_bf = parent->_bf = 0;
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if(subLR) subLR->_parent = parent;//subLR可能为空
		Node* parentparent = parent->_parent;

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

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentparent->_left == parent)
				parentparent->_left = subL;
			else
				parentparent->_right = subL;
			subL->_parent = parentparent;
		}
		subL->_bf = 0;
		parent->_bf = 0;
	}
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		if (bf == 1)
		{
			parent->_bf = 0;
			subR->_bf = -1;
			subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	
	void InOder()
	{
		_InOrder(_root);
	}
	void _InOrder(Node* root)
	{
		if (root == NULL) return;
		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}
	 
	int Height(Node* root)
	{
		if (root == nullptr) return 0;

		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		return max(leftHeight, rightHeight)+1;
	}

	bool IsBalance()//balance均衡
	{
		return _IsBalance(_root);
	}
	bool _IsBalance(Node* root)
	{
		if (root == NULL)
			return true;

		// 对当前树进行检查
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		if (rightHeight - leftHeight != root->_bf)
		{
			cout << root->_kv.first << "现在是:" << root->_bf << endl;
			cout << root->_kv.first << "应该是:" << rightHeight - leftHeight << endl;
			return false;
		}

		return abs(rightHeight - leftHeight) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

private:
	Node* _root;
};

void TestAVLTree()
{ 
	AVLTree t;
	int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
		cout << t.IsBalance() << endl;//检查代码
	}
	t.InOder();
	cout << t.IsBalance() << endl;
}

C++中“AVL”树的模拟实现以及实现中遇见的问题

C/C++/C#相关栏目本月热门文章