AVL的代码剖析(c++)

目录

1.什么是AVL树

2.平衡因子的引入

3.旋转

3.1左旋

3.2右旋

3.3左右双旋

3.4右左双旋

4.插入 

5.AVL树的判平衡

---

1.什么是AVL树

AVL树是一棵二叉平衡搜索树。当向二叉搜索树中插入新的结点，如果能保证每个结点的左右子树高度之差的绝对值不超过1，那么此时就是二叉平衡搜索树。

2.平衡因子的引入

由于AVL是二叉平衡搜索树，所以AVL树的底层还是二叉搜索树，为了保证每个结点的左右子树高度之差的绝对值不超过1，我们在AVLNode中加入新的成员变量平衡因子——_bf

template<class T, class V >
struct AVLNode
{
 
	pair _kv;
	AVLNode* left;
	AVLNode* right;
	AVLNode* parent;
	int _bf;
 
	AVLNode(const pair& kv)
		:_kv(kv)
		, right(nullptr)
		, left(nullptr)
		, parent(nullptr)
		, _bf(0)
	{}
};

pair _kv;  是库里的类模版，可以用来储存数据，这里不重要只需要了解pair的使用就行

3.旋转

为什么要旋转，因为每次插入数据的时候都会改变树某些节点的平衡因子，当树的两边的高度差超过1时，我们就需要通过旋转改变高度差，使得高度差<1。这里我们以右树的高度减去左树的高度为平衡因子的大小来衡量。旋转只有四种，左旋，右旋，左右旋，右左旋。首先我们来看左旋

3.1左旋

此时就是一种典型的左旋的情况。这里4节点的平衡因子是2，而5节点的平衡因子是1。此时4节点以及不平衡了。左旋，将5旋上去。我们就需要将平衡因子为2的节点传入函数中，我们称|_bf|>1的为parent节点，|_bf|<1的节点为cur节点。

此时树就再一次平衡了用图来旋转是这样，那么我们看图写代码。我们可以知道，抽象的来说就是首先是将5的左边指向5的父亲4，而后将4的右边指向5的左边（这里5的左边是空，但有时5的左边是有节点的），将5的父亲指向4的父亲，4的父亲指向5.最后将5和4的平衡因子变成0就行了。

具体代码如下

void RotateL(Node* parent)//左单旋
{
	Node* pcurR = parent->right;
	Node* curL = pcurR->left;
	Node* parent_parent = parent->parent;
	
	parent->parent = pcurR;
	pcurR->left = parent;
	parent->right = curL;
	pcurR->parent = parent_parent;
	if (curL)
		curL->parent = parent;
 
	if (parent_parent == nullptr)
		_root = pcurR;
	else
	{
		if (parent_parent->left == parent)
			parent_parent->left = pcurR;
		else
			parent_parent->right = pcurR;
	}
	parent->_bf = pcurR->_bf = 0;
}

3.2右旋

右旋就是将左旋镜像一下。

4的平衡因子变成-2,5的平衡因子变成-1。代码与左旋类似

void RotateR(Node* parent)
{
	Node* pcurR = parent->left;
	Node* curL = pcurR->right;
	Node* parent_parent = parent->parent;
 
	parent->parent = pcurR;
	pcurR->right = parent;
	parent->left = curL;
	pcurR->parent = parent_parent;
	if (curL)
		curL->parent = parent;
 
	if (parent_parent == nullptr)
		_root = pcurR;
	else
	{
		if (parent_parent->left == parent)
			parent_parent->left = pcurR;
		else
			parent_parent->right = pcurR;
	}
	parent->_bf = pcurR->_bf = 0;
}

3.3左右双旋

有时候插入新的节点后单旋是不够的，此时就需要旋两次。具体看图

无论怎么旋转都是通过单旋去实现平衡的。此时4的平衡因子是-2,3的平衡因子是-1。但是左右双旋不只是简单的直接复用左单旋和右单旋函数，上图情况没问题可以简单的复用，那下面这种情况就不能简单的复用了

对比两图同样是左右双旋但是最后cur与parent的平衡因子却不一样，所以这里还需要讨论插入节点是左边还是右边，这里我们可以以curR为参考，插入左边时curR->_bf=-1。插入右边时curR->_bf=1。总的来看左右双旋只需要考虑3种情况。代码如下。

void RotateLR(Node* parent)
{
 
	Node* cur = parent->left;
	Node* curR = cur->right;
	int curR_bf = curR->_bf;
 
 
	RotateL(parent->left);
	RotateR(parent);
 
 
	if (curR_bf == 1)
	{
		cur->_bf = -1;
		parent->_bf = 0;
		curR->_bf = 0;
	}
	else if (curR_bf == -1)
	{
		cur->_bf = 0;
		parent->_bf = 1;
		curR->_bf = 0;
	}
	else if (curR_bf == 0)
	{
		cur->_bf = 0;
		parent->_bf = 0;
		curR->_bf = 0;
	}
}

3.4右左双旋

同理右左双旋与左右双旋是镜像，代码逻辑还是一样，分3种情况，代码如下。

	void RotateRL(Node* parent)
	{
		Node* cur = parent->right;
		Node* curL = cur->left;
		int curL_bf = curL->_bf;
		RotateR(parent->right);
		RotateL(parent);
		
		if (curL_bf == 1)
		{
			cur->_bf = 0;
			parent->_bf = -1;
			curL->_bf = 0;
		}
		else if (curL_bf == -1)
		{
			cur->_bf = 1;
			parent->_bf = 0;
			curL->_bf = 0;
		}
		else if (curL_bf == 0)
		{
			cur->_bf = 0;
			parent->_bf = 0;
			curL->_bf = 0;
		}
	}

4.插入 

知道插入时调整平衡树的旋转逻辑后，插入就简单了，只需要根据parent和cur的平衡因子判断是哪一种情况就行。

	bool Insert(const pair& kv)
	{
		//插入肯定是从空开始插入的
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		//首先先找到要插入的位置
		Node* root = _root;
		Node* parent = nullptr;
		while (root)
		{
			if (root->_kv.first < kv.first)
			{
				parent = root;
				root = root->right;
			}
			else if (root->_kv.first > kv.first)
			{
				parent = root;
				root = root->left;
			}
			else
			{
				return false;
			}
		}
		Node* cur = new Node(kv);
		//右树-左树=平衡因子
		//先插入节点再去进行节点的更新
		if (kv.first > parent->_kv.first)//right
		{
			parent->right = cur;
			cur->parent = parent;
		}
		else//left
		{
			parent->left = cur;
			cur->parent = parent;
		}
 
		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)//左单旋
				{
					RotateL(parent);
				}
 
				else if (parent->_bf == -2 && cur->_bf == -1)//右单旋
				{
					RotateR(parent);
				}
 
				else if (parent->_bf == 2 && cur->_bf == -1)//先右单旋，再左单旋
				{
					RotateRL(parent);
				}
 
				else if (parent->_bf == -2 && cur->_bf == 1)//先左单旋，再右单旋
				{
					RotateLR(parent);
 
				}
				break;
			}
			else//判断树的逻辑是否正确，如果进入了这个else代表树的逻辑错了
				assert(false);
	    }
	
	}

5.AVL树的判平衡

写完插入后我们需要判断是否AVL树平衡了。既然是二叉树，那么我们就可以用递归的方式去检查。使用分治的方式去写代码。

bool _Is_BalanceTree(Node* root)
{
 
	if (root == nullptr)
		return true;
 
	int left_hight = _Hight(root->left);
	int right_hight = _Hight(root->right);
	int hight = right_hight-left_hight;
	if (abs(hight) > 2 || hight != root->_bf)
		return false;
 
	return _Is_BalanceTree(root->left) && _Is_BalanceTree(root->right);
}

我们用分治的方式，考虑放回情况。当root为空时代表到某一条路径的尽头或者AVL树为空我们返回true，我们利用AVL树的定义去判断，我们要拿到root两边的子树高度差hight，进行判断hight的绝对值是否小于2，小于2返回true，大于2返回false，同时我们还需要看AVL树的平衡因子对了吗。然后我们再去递归判断左子树和右子树就行。这里我们需要再main函数中去调用bool _Is_BalanceTree（）函数但是root是私有的不能再main函数中访问所以我们将_Is_BalanceTree函数作为子函数用一个bool Is_BalanceTree（）函数去套用_Is_BalanceTree（）函数，而且_Is_BalanceTree函数是我们不想被调用的我们就将其作为私有 这样就解决了。

	bool Is_BalanceTree()
	{
		return _Is_BalanceTree(_root);
	}

最后我们还需要去写一个_hight函数去拿到树的高度，同意我们用递归的方式，用分治的思想去拿。

int _Hight(Node* root)
{
	if (root == nullptr)
		return 0;
	int left_hight = _Hight(root->left);
	int right_hight = _Hight(root->right);
 
 
	return (left_hight > right_hight ? left_hight +1: right_hight + 1);
}

最后return (left_hight > right_hight ? left_hight +1: right_hight + 1);的原因是树的高度是指最长的那一条路径，所以我们需要拿到左右中大的那一个，最后还要+1为什么呢，因为拿到的只是子树的高度还要算上自己的高度，自己作为树的“根”肯定是占一格高度的。

至此AVL树的实现就结束了，希望能帮助到你，有错误的或者疑问的可以私信我。