【C++ AVL树】

文章目录

- AVL树
- - AVL树的概念
  - AVL树节点的定义
  - AVL树的插入
  - AVL树的旋转
  - - 右单旋
    - 左单旋
    - 左右双旋
    - 右左双旋
  - 代码实现
- 总结

AVL树

AVL树的概念

二叉搜索树在顺序有序或接近有序的情况下，而插入搜索树将退化为单叉树，此时查找的时间复杂度为O(n)，效率低下。
两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新节点后，保证每个节点的左右子树高度差的绝对值不超过1，即可降低树的高度，减少平均搜索长度。因此，AVL树也被叫做高度平衡二叉搜索树，插入，查找，删除在平均和最坏情况下的时间复杂度都是O( $log_2 n$ )。

AVL树节点的定义

	template<class K, class V>
	struct AVLTreeNode
	{
		AVLTreeNode<K, V>* _left;
		AVLTreeNode<K, V>* _right;
		AVLTreeNode<K, V>* _parent;
		pair<K, V> _kv;
		int _bf; //balance factor 平衡因子
		AVLTreeNode(const pair<K, V>& kv)
			:_left(nullptr)
			,_right(nullptr)
			,_parent(nullptr)
			,_kv(kv)
			,_bf(0)
		{}
	};

注意：实现AVL树平衡因子不是必须的，只不过有了平衡因子帮助我们更便捷地控制整棵树。

AVL树的插入

根据二叉搜索树的规则插入新节点

bool Insert(const pair<K, V> & kv)
		{
			root为空，特殊处理
			if (_root == nullptr)
			{
				_root = new Node(kv);
				return true;
			}
			Node* curr = _root;
			Node* parent = nullptr;
			while (curr)
			{
				if (curr->_kv.first < kv.first)
				{
					parent = curr;
					curr = curr->_right;
				}
				else if (curr->_kv.first > kv.first)
				{
					parent = curr;
					curr = curr->_left;
				}
				else
				{
					return false;
				}
			}
			将新节点和其父亲节点链接起来
			Node* newnode = new Node(kv);
			if (parent->_kv.first < kv.first)
				parent->_right = newnode;
			else
				parent->_left = newnode;

			newnode->_parent = parent;
			
			......
		}

不断向上更新平衡因子
1. 当前平衡因子为0，说明插入之前平衡因子为1 / -1，插入之后不改变树的高度，不会影响其他祖先节点，此时更新结束。
2. 当前平衡因子为1 / -1，说明插入之前平衡因子为0，插入之后当前节点地高度发生变化，会影响其他祖先节点，但是不违反规则，需要向上对祖先节点进行更新，直至当前节点为root。
3. 当前平衡因子为 2 / -2，此时当前节点所在地子树违反了平衡规则，需要进行处理–>旋转。

while (parent)
{
		if (parent->_left == newnode)
		{
			parent->_bf--;
		}
		else
		{
			parent->_bf++;
		}
		if (parent->_bf == 0)
			break;
		else if (parent->_bf == -1 || parent->_bf == 1)
		{
			newnode = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == -2 || parent->_bf == 2)
		{
			旋转处理
		}
		else
		{
			assert(false);
		}
}

AVL树的旋转

右单旋

在这里插入图片描述

void RotatoR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;
	subL->_right = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = subL;
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
			ppnode->_left = subL;
		else
			ppnode->_right = subL;
		subL->_parent = ppnode;
	}
	parent->_bf = 0;
	subL->_bf = 0;
}

左单旋

在这里插入图片描述

void RotatoL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;
	subR->_left = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = subR;
	if (parent == _root)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
			ppnode->_left = subR;
		else
			ppnode->_right = subR;
		subR->_parent = ppnode;
	}
	parent->_bf = 0;
	subR->_bf = 0;
}

左右双旋

在这里插入图片描述
旋转之前，45的平衡因子可能是-1/0/1，旋转完成之后，根据情况对其他节点的平衡因子进行调整

void RotatoLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;
	RotatoL(subL);
	RotatoR(parent);
	subLR->_bf = 0;
	if (bf == 0)
	{
		subL->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 1)
	{
		subL->_bf = -1;
		parent->_bf = 0;
	}
	else if (bf == -1)
	{
		subL->_bf = 0;
		parent->_bf = 1;
	}
}

右左双旋

在这里插入图片描述

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

	RotatoR(subR);
	RotatoL(parent);
	if (bf == 0)
	{
		subR->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 1)
	{
		subR->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1)
	{
		subR->_bf = 1;
		parent->_bf = 0;
	}
}

代码实现

namespace xxx
{
	template<class K, class V>
	struct AVLTreeNode
	{
		AVLTreeNode<K, V>* _left;
		AVLTreeNode<K, V>* _right;
		AVLTreeNode<K, V>* _parent;
		pair<K, V> _kv;
		int _bf; //balance factor 平衡因子
		AVLTreeNode(const pair<K, V>& kv)
			:_left(nullptr)
			,_right(nullptr)
			,_parent(nullptr)
			,_kv(kv)
			,_bf(0)
		{}
	};
	template<class K, class V>
	class AVLTree
	{
		typedef AVLTreeNode<K, V> Node;
	public:
		bool Insert(const pair<K, V> & kv)
		{
			if (_root == nullptr)
			{
				_root = new Node(kv);
				return true;
			}
			Node* curr = _root;
			Node* parent = nullptr;
			while (curr)
			{
				if (curr->_kv.first < kv.first)
				{
					parent = curr;
					curr = curr->_right;
				}
				else if (curr->_kv.first > kv.first)
				{
					parent = curr;
					curr = curr->_left;
				}
				else
				{
					return false;
				}
			}
			Node* newnode = new Node(kv);
			if (parent->_kv.first < kv.first)
				parent->_right = newnode;
			else
				parent->_left = newnode;
			newnode->_parent = parent;
			while (parent)
			{
				if (parent->_left == newnode)
				{
					parent->_bf--;
				}
				else
				{
					parent->_bf++;
				}
				if (parent->_bf == 0)
					break;
				else if (parent->_bf == -1 || parent->_bf == 1)
				{
					newnode = parent;
					parent = parent->_parent;
				}
				else if (parent->_bf == -2 || parent->_bf == 2)
				{
					if (parent->_bf == 2 && newnode->_bf == 1)
					{
						RotatoL(parent);
					}
					else if (parent->_bf == -2 && newnode->_bf == -1)
					{
						RotatoR(parent);
					}
					else if (parent->_bf == -2 && newnode->_bf == 1)
					{
						RotatoLR(parent);
					}
					else if (parent->_bf == 2 && newnode->_bf == -1)
					{
						RotatoRL(parent);
					}
					else
					{
						assert(false);
					}
					break;
				}
				else
				{
					assert(false);
				}
			}
			return true;
		}
		void RotatoL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			parent->_right = subRL;
			if (subRL)
				subRL->_parent = parent;
			subR->_left = parent;
			Node* ppnode = parent->_parent;
			parent->_parent = subR;
			if (parent == _root)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			else
			{
				if (ppnode->_left == parent)
					ppnode->_left = subR;
				else
					ppnode->_right = subR;
				subR->_parent = ppnode;
			}
			parent->_bf = 0;
			subR->_bf = 0;
		}
		void RotatoR(Node* parent)
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;
			parent->_left = subLR;
			if (subLR)
				subLR->_parent = parent;
			subL->_right = parent;
			Node* ppnode = parent->_parent;
			parent->_parent = subL;
			if (parent == _root)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			else
			{
				if (ppnode->_left == parent)
					ppnode->_left = subL;
				else
					ppnode->_right = subL;
				subL->_parent = ppnode;
			}
			parent->_bf = 0;
			subL->_bf = 0;
		}
		void RotatoLR(Node* parent)
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;
			int bf = subLR->_bf;
			RotatoL(subL);
			RotatoR(parent);
			subLR->_bf = 0;
			if (bf == 0)
			{
				subL->_bf = 0;
				parent->_bf = 0;
			}
			else if (bf == 1)
			{
				subL->_bf = -1;
				parent->_bf = 0;
			}
			else if (bf == -1)
			{
				subL->_bf = 0;
				parent->_bf = 1;
			}
		}
		void RotatoRL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			int bf = subRL->_bf;
			subRL->_bf = 0;

			RotatoR(subR);
			RotatoL(parent);
			if (bf == 0)
			{
				subR->_bf = 0;
				parent->_bf = 0;
			}
			else if (bf == 1)
			{
				subR->_bf = 0;
				parent->_bf = -1;
			}
			else if (bf == -1)
			{
				subR->_bf = 1;
				parent->_bf = 0;
			}
		}
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
		bool IsAVLTree()
		{
			return _IsAVLTree(_root);
		}
	private:
		bool _IsAVLTree(Node* root)
		{
			if (root == nullptr)
				return true;
			int leftH = Height(root->_left);
			int rightH = Height(root->_right);
			return abs(leftH - rightH) <= 1
				&& _IsAVLTree(root->_left)
				&& _IsAVLTree(root->_right);
		}
		int Height(Node* node)
		{
			if (node == nullptr)
				return 0;
			int leftH = Height(node->_left);
			int rightH = Height(node->_right);
			return 1 + max(leftH, rightH);
		}
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_kv.second << ' ';
			_InOrder(root->_right);
		}
		Node* _root = nullptr;
	};
}

总结

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 $log_2 (N)$ 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。