AVL树的实现

目录

概念

实现

节点结构

插入

旋转

右单旋

左单旋 

 左右双旋​编辑

 右左双旋

 判断是否平衡

 遍历

附录（完整代码）

概念

• AVL树是最先发明的⾃平衡⼆叉查找树，AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：它的左右⼦树都是AVL树，且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树， 通过控制⾼度差去控制平衡。
• AVL树实现这⾥我们引⼊⼀个平衡因⼦(balance factor)的概念，每个结点都有⼀个平衡因⼦，任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度，也就是说任何结点的平衡因⼦等于0/1/-1，AVL树并不是必须要平衡因⼦，但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡，就像⼀个⻛向标⼀样。
• AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在 ，那么增删查改的效率也可 以控制在O()，相⽐⼆叉搜索树有了本质的提升。

实现

节点结构

struct AVLNode
{
	K _data;
	AVLNode* _left;
	AVLNode* _right;
	AVLNode* _parent;
	int _bf;

	AVLNode(K data)
		:_data(data),
		 _left(nullptr),
		 _right(nullptr),
		 _parent(nullptr),
		 _bf(0)
	{}
};

插入

• 首先我们要找到插入数据的位置，这一步与二叉搜索树的插入没有区别。

• 然后我们就需要更新bf，我们不能只是更新插入节点的父节点的bf，而是需要一步一步的向上更新才可以，这样就需要思考什么情况下进行什么样的更新：

  • 如果某节点更新后bf变为-2或者2时，已经是不满足平衡条件了，需要进行相应的操作来进行调整。

  • 如果某节点更新后bf变为-1或者1，则它一定是从0变来的，以它为根节点的二叉树的高度一定增加了1，就要根据它是其父节点的左孩子还是右孩子来更新父节点的bf。

  • 如果某节点更新后bf变为0，则它一定是从-1或者1更新来的，而且左右子树高度都一致了，那么以它为根节点的二叉树的高度没有发生变化，不需要向上更新了。

  • 还有就是如果已经更新到根节点了，就不需要更新了。

代码结构：

	bool Insert(K key)
	{
		Node* newnode = new Node(key);
		if (_root == nullptr) _root = newnode;
		else
		{
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				parent = cur;
				if (cur->_data == key) return false;
				else if (cur->_data < key) cur = cur->_right;
				else cur = cur->_left;
			}
			newnode->_parent = parent;
			if (parent->_data > key)
			{
				parent->_left = newnode;
				parent->_bf -= 1;
			}
			else
			{
				parent->_right = newnode;
				parent->_bf += 1;
			}
			while (parent)
			{
				if (parent->_bf == 0)
				{
					break;
				}
				else if (parent->_bf == -1 || parent->_bf == 1)
				{
					if (parent->_parent)
					{
						if (parent == parent->_parent->_left)
							parent->_parent->_bf -= 1;
						else
							parent->_parent->_bf += 1;
					}
					parent = parent->_parent;
				}
				else if (parent->_bf == -2 || parent->_bf == 2)
				{
					if (parent->_bf == -2 && parent->_left->_bf == -1)
					{
						RotateR(parent);
					}
					else if (parent->_bf == 2 && parent->_right->_bf == 1)
					{
						RotateL(parent);
					}
					else if (parent->_bf == -2 && parent->_left->_bf == 1)
					{
						RotateLR(parent);
					}
					else if (parent->_bf == 2 && parent->_right->_bf == -1)
					{
						RotateRL(parent);
					}
					else
					{
						assert(false);
					}
					break;
				}
				else
				{
					assert(false);
				}
			}
		}
		return true;
	}

旋转

        如果出现了不平衡的情况，就要进行相应操作进行调整，下面我们会讲解一下不同情况下采取的旋转调整操作：

右单旋

        如果出现上图中的这种情况，parent已经不平衡了，而且是左子树过高，而且对于左子树来说，左边比右边高，就可以用到右单旋的方法来进行调整：

• 将subl向右旋转替代parent的位置。
• 让parent变为subl的右节点，将sublr变为parent的左节点。
• 个人理解：就是将a抬高一个高度，通过旋转后，自然c会下降一个高度，a，b，c就会保持在同一个高度上，达到平衡，且旋转后的subl与parent的bf一定为0，也不需要向上更新bf了。

代码实现：

	void RotateR(Node* parent)
	{
		Node* subl = parent->_left;
		Node* sublr = subl->_right;
		Node* pparent = parent->_parent;

		if (parent == _root) _root = subl;
		else if (pparent->_left == parent)
			pparent->_left = subl;
		else
			pparent->_right = subl;

		subl->_parent = pparent;
		subl->_right = parent;
		parent->_parent = subl;
		parent->_left = sublr;

		subl->_bf = 0;
		parent->_bf = 0;
	}

左单旋 

         左单旋其实与右单旋特别相似，差不多就是一个对称的情况，我们不多做解释了，应该是可以理解的。

代码实现：

	void RotateL(Node* parent)
	{
		Node* subr = parent->_right;
		Node* subrl = subr->_left;
		Node* pparent = parent->_parent;
		
		if (parent == _root) _root = subr;
		else if (pparent->_left == parent)
			pparent->_left = subr;
		else
			pparent->_right = subr;

		subr->_parent = pparent;
		subr->_left = parent;
		parent->_parent = subr;
		parent->_right = subrl;

		subr->_bf = 0;
		parent->_bf = 0;
	}

 左右双旋

        当出现上面这种情况时，采取右单旋是不可靠的（左单旋转一眼看上去就不可靠），因为右单旋会将a抬高一个高度，为b高度不变，这样会导致旋转后的subl的右子树比左子树高两个高度。

那么我们采取以下措施：

        上图中的三种情况旋转操作是一样的，先对5（subl）这个节点进行左旋转，与前面说到的左单旋操作一直，这样之后对于10（parent）就变成了右单旋转的情况，对其右旋即可。

        上面三种情况不同的就是旋转后的平衡因子不同，但是sublr的bf都为0，也就不需要再向上更新bf了。

代码实现：

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

		RotateL(subl);
		RotateR(parent);

		sublr->_bf = 0;
		if(bf == 1)
		{ 
			subl->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == -1)
		{
			subl->_bf = 0;
			parent->_bf = 1;
		}
		else
		{
			subl->_bf = 0;
			parent->_bf = 0;
		}
	}

 右左双旋

        与左右双旋成对称关系，可以根据图片与代码进行理解：

代码实现：

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

		RotateR(subr);
		RotateL(parent);

		subrl->_bf = 0;
		if (bf == 1)
		{
			subr->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			subr->_bf = 1;
			parent->_bf = 0;
		}
		else
		{
			subr->_bf = 0;
			parent->_bf = 0;
		}
	}

 判断是否平衡

        我们再提供一个接口来测试我们的AVL树是否可以保持平衡：

• 首先我们要需要一个获取一个节点的左右子树的高度的接口，一是来判断其高度差与其bf是否一致，一是来判断是否平衡。
• 如果不一致或者不平衡就直接返回false。
• 否则检查左右子树。
• 关于获取二叉树高度的接口，只需要递归的计算左右子树高度的最大值并加1即可，不是重点。

代码实现：

	bool IsBalanceTree()
	{
		return _IsBalanceTree(_root);
	}

private:

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

		int heightl = _Height(root->_left);
		int heightr = _Height(root->_right);
		return  heightl > heightr ? heightl + 1 : heightr + 1;
	}

	bool _IsBalanceTree(Node* root)
	{
		if (root == nullptr)
			return true;

		int heightL = _Height(root->_left);
		int heightR = _Height(root->_right);
		int diff = heightR - heightL;

		if (diff != root->_bf)
		{
			return false;
		}
		else if (abs(diff) >= 2)
		{
			return false;
		}
		else
		{
			return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
		}
	}

 遍历

        关于遍历，采取和二叉树的中序遍历即可。

附录（完整代码）

#pragma once

#include <iostream>
#include <cassert>

using namespace std;

template <class K>
struct AVLNode
{
	K _data;
	AVLNode* _left;
	AVLNode* _right;
	AVLNode* _parent;
	int _bf;

	AVLNode(K data)
		:_data(data),
		 _left(nullptr),
		 _right(nullptr),
		 _parent(nullptr),
		 _bf(0)
	{}
};

template <class K>
class AVLTree
{
public:
	using Node = AVLNode<K>;

	bool Insert(K key)
	{
		Node* newnode = new Node(key);
		if (_root == nullptr) _root = newnode;
		else
		{
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				parent = cur;
				if (cur->_data == key) return false;
				else if (cur->_data < key) cur = cur->_right;
				else cur = cur->_left;
			}
			newnode->_parent = parent;
			if (parent->_data > key)
			{
				parent->_left = newnode;
				parent->_bf -= 1;
			}
			else
			{
				parent->_right = newnode;
				parent->_bf += 1;
			}
			while (parent)
			{
				if (parent->_bf == 0)
				{
					break;
				}
				else if (parent->_bf == -1 || parent->_bf == 1)
				{
					if (parent->_parent)
					{
						if (parent == parent->_parent->_left)
							parent->_parent->_bf -= 1;
						else
							parent->_parent->_bf += 1;
					}
					parent = parent->_parent;
				}
				else if (parent->_bf == -2 || parent->_bf == 2)
				{
					if (parent->_bf == -2 && parent->_left->_bf == -1)
					{
						RotateR(parent);
					}
					else if (parent->_bf == 2 && parent->_right->_bf == 1)
					{
						RotateL(parent);
					}
					else if (parent->_bf == -2 && parent->_left->_bf == 1)
					{
						RotateLR(parent);
					}
					else if (parent->_bf == 2 && parent->_right->_bf == -1)
					{
						RotateRL(parent);
					}
					else
					{
						assert(false);
					}
					break;
				}
				else
				{
					assert(false);
				}
			}
		}
		return true;
	}

	Node* Find(K key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_data == key) return cur;
			else if (cur->_data < key) cur = cur->_right;
			else cur = cur->_left;
		}
		return nullptr;
	}

	bool IsBalanceTree()
	{
		return _IsBalanceTree(_root);
	}

	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}

private:

	void _Inorder(Node* root)
	{
		if (root == nullptr) return;
		_Inorder(root->_left);
		cout << root->_data << " ";
		_Inorder(root->_right);
	}

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

		int heightl = _Height(root->_left);
		int heightr = _Height(root->_right);
		return  heightl > heightr ? heightl + 1 : heightr + 1;
	}

	bool _IsBalanceTree(Node* root)
	{
		if (root == nullptr)
			return true;

		int heightL = _Height(root->_left);
		int heightR = _Height(root->_right);
		int diff = heightR - heightL;

		if (diff != root->_bf)
		{
			return false;
		}
		else if (abs(diff) >= 2)
		{
			return false;
		}
		else
		{
			return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
		}
	}

private:
	void RotateR(Node* parent)
	{
		Node* subl = parent->_left;
		Node* sublr = subl->_right;
		Node* pparent = parent->_parent;

		if (parent == _root) _root = subl;
		else if (pparent->_left == parent)
			pparent->_left = subl;
		else
			pparent->_right = subl;

		subl->_parent = pparent;
		subl->_right = parent;
		parent->_parent = subl;
		parent->_left = sublr;

		subl->_bf = 0;
		parent->_bf = 0;
	}

	void RotateL(Node* parent)
	{
		Node* subr = parent->_right;
		Node* subrl = subr->_left;
		Node* pparent = parent->_parent;
		
		if (parent == _root) _root = subr;
		else if (pparent->_left == parent)
			pparent->_left = subr;
		else
			pparent->_right = subr;

		subr->_parent = pparent;
		subr->_left = parent;
		parent->_parent = subr;
		parent->_right = subrl;

		subr->_bf = 0;
		parent->_bf = 0;
	}

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

		RotateL(subl);
		RotateR(parent);

		sublr->_bf = 0;
		if(bf == 1)
		{ 
			subl->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == -1)
		{
			subl->_bf = 0;
			parent->_bf = 1;
		}
		else
		{
			subl->_bf = 0;
			parent->_bf = 0;
		}
	}

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

		RotateR(subr);
		RotateL(parent);

		subrl->_bf = 0;
		if (bf == 1)
		{
			subr->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			subr->_bf = 1;
			parent->_bf = 0;
		}
		else
		{
			subr->_bf = 0;
			parent->_bf = 0;
		}
	}
private:
	Node* _root = nullptr;
};