AVL树

朱雀 2022-07-14 23:38 164阅读 0赞

# AVL树> #

在之前我实现了二叉搜索树，但是二叉搜索树存在问题，就是当输入单调增或者单调减的结点数据后，二叉树就退化成类似链表的结构了，为了解决二叉搜索树的这种弊端就引入了AVL树.

AVL树的性质>

1).左子树和右子树的高度之差的绝对值不超过1.

2).树中的每个左子树和右子树都是AVL树.

3).每个结点都有一个平衡因子，任一结点的平衡因子都是\{-1,0,1\},(每个结点的平衡因子等于右子树的高度-左子树的高度).

AVL树是一种高度平衡的二叉搜索树，它要求所有节点所在的二叉树都满足一个条件就是：平衡因子不大于2，此时搜索二叉树也就近似于满二叉树了，但是要实现这样的一棵树就需要不停的旋转.

下面就让我们来旋转不平衡的AVL树吧,我总结了以下四种可能出现的旋转>

![Center][]

1.左单旋>

![Center 1][]

2.右单旋>

![Center 2][]

3.右左双旋>

![Center 3][]

4.左右双旋>

![Center 4][]

细心的童鞋就会发现了，我在右左双旋和左右双旋的的情况中我画了两种不同的插入插入位置，这并不是无聊，而是在双旋的时候插入位置的不同就会对平衡因子造成影响.

构造了这样的一颗AVL树之后如何判断这棵树是否是平衡树呢？

最简单也就是最容易想到的就是对这颗树的每一个节点进行遍历，得到这个结点的平衡因子进行判断，看是否合法.我们知道一颗树满足平衡树的条件就是>平衡因子的绝对值不大于2.这种想法虽然可以实现但是毕竟太费时间了，从时间复杂度上来说，我们需要求深度也需要遍历每个结点，时间复杂度是O(N\*N).

有没有可能优化呢？我们是每次都要求子树的深度，这就是时间复杂度高的原因，假设这样一种情况>在计算深度的同时也进行每个结点的判断,这样是不是就优化了呢？当然是啦，我们先判断左结点，如果左结点的左右都合法我们就+1并向上一层返；然后进行右结点的判断，最后再进行当前结点的判断.这种想法有点类似后序遍历的思路.它的时间复杂度为O(N).

代码实现区>

#pragma once
    
    template<class K,class V>
    struct AVLTreeNode
    {
    	K _key;
    	V _value;
    	AVLTreeNode<K,V>* _left;
    	AVLTreeNode<K,V>* _right;
    	AVLTreeNode<K,V>* _parent;
    	int _bf;       //平衡因子  --右子树的高度减左子树
    	AVLTreeNode(const K& key,const V& value)
    		:_key(key)
    		,_value(value)
    		,_left(NULL)
    		,_right(NULL)
    		,_parent(NULL)
    		,_bf(0)
    	{}
    };
    
    template<class K,class V>
    class AVLTree
    {
    	typedef AVLTreeNode<K,V> Node;
    public:
    	AVLTree()
    		:_root(NULL)
    	{}
    	~AVLTree()
    	{
    		_Destroy(_root);
    	}
    	bool Insert(const K& key,const V& value)
    	{
    		if(_root == NULL)     //空
    		{
    			_root=new Node(key,value);
    			return true;
    		}
    		Node *cur=_root;
    		Node *parent=NULL;
    		while (cur)
    		{
    			if(cur->_key < key)
    			{
    				parent=cur;
    				cur=cur->_right;
    			}
    			else if (cur->_key > key)
    			{
    				parent=cur;
    				cur=cur->_left;
    			}
    			else               //找到相同的结点
    				return false;
    		}
    		cur=new Node(key,value);
    		cur->_parent=parent;
    		if(parent->_key < key)
    			parent->_right=cur;
    		else                   //parent->_key > key
    			parent->_left=cur;
    
    		while (parent)
    		{
    			if(parent->_left == cur)
    				--parent->_bf;
    			else if(parent->_right == cur)
    				++parent->_bf;
    			if(parent->_bf == 0)      //满足AVL树
    				return true;
    			else if(parent->_bf == 1 || parent->_bf == -1)
    			{
    				//继续向上调整
    				cur=parent;
    				parent=parent->_parent;
    			}
    			else     //2 -2   旋转
    			{
    				if(parent->_bf == 2)
    				{
    					if(cur->_bf == 1)         //左单旋
    						_RotateL(parent);
    					else if(cur->_bf == -1)
    						_RotateRL(parent);    //右左双旋
    				}
    				else   //-2
    				{
    					if(cur->_bf == 1)
    						_RotateLR(parent);    //左右双旋
    					else if(cur->_bf == -1)
    						_RotateR(parent);     //右单旋
    				}
    			}
    		}
    		return true;
    	}
    	void InOrder()
    	{
    		_InOrder(_root);
    		cout<<endl;
    	}
    	bool IsBalance()
    	{
    		return _IsBalance(_root);
    	}
    	bool IsBalanceOP()
    	{
    		int height=0;
    		return _IsBalanceOP(_root,height);
    	}
    protected:
    	bool _IsBalanceOP(Node *root,int &height)   
    	{
    		if(root == NULL)
    		{
    			height=0;
    			return true;
    		}
    		int left=0;
    		_IsBalanceOP(root->_left,height);
    		int right=0;
    		_IsBalanceOP(root->_right,height);
    		int bf=right-left;
    		if(abs(bf) < 2)             //平衡因子合法
    		{
    			height=1 + left > right ? left : right;
    			return true;
    		}
    		return false;
    	}
    	void _InOrder(Node *root)
    	{
    		if(root == NULL)
    			return ;
    		_InOrder(root->_left);
    		cout<<root->_key<<" ";
    		_InOrder(root->_right);
    	}
    	bool _IsBalance(Node *root)
    	{
    		if(root == NULL)
    			return true;
    		int left=_HeightTree(root->_left);
    		int right=_HeightTree(root->_right);
    		int bf=right-left;
    		if(root->_bf != bf)
    		{
    			cout<<"Is UnBalance:"<<root->_key<<endl;
    			return false;
    		}
    		return abs(bf) < 2 && _IsBalance(root->_left) 
    			&& _IsBalance(root->_right);
    	}
    	int _HeightTree(Node *root)
    	{
    		if(root == NULL)
    			return 0;
    		int leftsize=1+_HeightTree(root->_left);
    		int rightsize=1+_HeightTree(root->_right);
    		return leftsize > rightsize ? leftsize : rightsize;
    	}
    	void _RotateL(Node *parent)
    	{
    		Node *subR=parent->_right;
    		Node *subRL=subR->_left;
    		parent->_right=subRL;
    		if(subRL)
    			subRL->_parent=parent;
    		subR->_left=parent;
    		Node *tmp=parent->_parent;
    		parent->_parent=subR;
    		if(tmp == NULL)         //parent是根结点
    		{
    			_root=subR;
    			subR->_parent=NULL;
    		}
    		else                   //parent不是根结点
    		{
    			if(tmp->_left == parent)
    				tmp->_left=subR;
    			else
    				tmp->_right=subR;
    			subR->_parent=tmp;
    		}
    		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;
    		subL->_right=parent;
    		Node *tmp=parent->_parent;
    		parent->_parent=subL;
    		if(tmp == NULL)         //parent是根结点
    		{
    			_root=subL;
    			subL->_parent=NULL;
    		}
    		else                    //parent不是根结点
    		{
    			if(tmp->_left == parent)
    				tmp->_left=subL;
    			else
    				tmp->_right=subL;
    			subL->_parent=tmp;
    		}
    		subL->_bf=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 == 0)
    			subLR->_bf=subL->_bf=parent->_bf=0;
    		else if(bf == 1)
    		{
    			subL->_bf=-1;
    			subLR->_bf=1;
    			parent->_bf=0;
    		}
    		else         //-1
    		{
    			subL->_bf=0;
    			subLR->_bf=-1;
    			parent->_bf=1;
    		}
    	}
    	void _RotateRL(Node *parent)
    	{
    		Node *subR=parent->_right;
    		Node *subRL=subR->_left;
    		int bf=subRL->_bf;
    		_RotateR(parent->_right);
    		_RotateL(parent);
    		if(bf == 0)
    			parent->_bf=subR->_bf=subRL->_bf=0;
    		else if(bf == 1)
    		{
    			subR->_bf=0;
    			subRL->_bf=1;
    			parent->_bf=-1;
    		}
    		else       //-1
    		{
    			subR->_bf=1;
    			subRL->_bf=-1;
    			parent->_bf=0;
    		}
    	}
    	void _Destroy(Node *&root)
    	{
    		if(root == NULL)
    			return ;
    		Node *cur=root;
    		if(cur)
    		{
    			_Destroy(root->_left);
    			_Destroy(root->_right);
    			delete cur;
    			cur=NULL;
    		}
    	}
    protected:
    	Node *_root;
    };
    
    void testAVLTree()
    {
    	int array1[]={16, 3, 7, 11, 9, 26, 18, 14, 15};
    	size_t size=sizeof(array1)/sizeof(array1[0]);
    	AVLTree<int,int> tree;
    	for (size_t i=0;i<size;++i)
    	{
    		tree.Insert(array1[i],i);
    	}
    	tree.InOrder();
    	cout<<"tree IsBalance?"<<tree.IsBalance()<<endl;   //1
    
    	int array2[]={4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
    	size_t len=sizeof(array2)/sizeof(array2[0]);
    	AVLTree<int,int> tree2;
    	for(size_t i=0;i<len;++i)
    	{
    		tree2.Insert(array2[i],i);
    	}
    	tree2.InOrder();
    	cout<<"tree2 IsBalance?"<<tree2.IsBalance()<<endl;  //1
    }

![Center 5][]

[Center]: /images/20220715/77947f5e4c0e48d48076421360ea2dd0.png
[Center 1]: /images/20220715/150b918f69534bc39ab44e8d710c1515.png
[Center 2]: /images/20220715/6bf0e9a0d9714fc2add7a385d5f6f9c2.png
[Center 3]: /images/20220715/d368f3ae7e2e43208e2eb2074c615c3f.png
[Center 4]: /images/20220715/87a219e90a5c4882880cfba5feadd94f.png
[Center 5]: /images/20220715/b61ec5fda5534262bb2aff5b0e78decf.png