大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

数据结构--平衡二叉树AVL-创新互联

一、平衡二叉树( AVL树 )

网站建设哪家好,找创新互联!专注于网页设计、网站建设、微信开发、成都小程序开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了汉南免费建站欢迎大家使用!

 1、定义:AVL树又称为高度平衡的二叉搜索树,是1962年有俄罗斯的数学家G.M.Adel'son-Vel'skii和E.M.Landis提出来的。它能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度。

 2、出现原因:搜索二叉树若出现严重退化,查找或使用时会造成资源浪费。

 3、特性:

  • AVL树是一个三叉链;

  • 左、右子树的 | 高度之差| 不超过 1;

  • 左右子树都是AVL树;

  • 每个节点的平衡因子 = 右子树高度 - 左子树高度;(平衡因子:-1,1,0)

 4、效率:

    一棵AVL树有N个节点,其高度可以保持在log2N,插入/删除/查找的时间复杂度:log2N,即 O(lgN)。

二、AVL相关

1、右单旋

数据结构 -- 平衡二叉树AVL

2、左单旋

数据结构 -- 平衡二叉树AVL

3、右左单旋及左右单旋

    根据左单旋、右单旋及树的情况进行选择,旋转后需要更新平衡因子,以防失误。

数据结构 -- 平衡二叉树AVL

4、节点平衡因子的更新:

    (1)插入节点的右孩子,及平衡因子bf++;左孩子,bf--;

    (2)若插入节点后,计算得bf==0,则平衡,不需更新平衡因子;bf==1或-1,则需向上查看是否需要平衡因子;bf==2或-2,则根据情况进行旋转,并更新平衡因子。

5、判断AVL树:

    (1)计算左、右子树高度,平衡因子;

    (2)若平衡因子 < 2,即其子树为AVL树;

三、源代码

1、节点

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

	K _key;//权值
	V _value;
	int _bf;//平衡因子

	AVLTreeNode(const K& key,const V& value)
		:_key(key)
		,_value(value)
		,_left(NULL)
		,_right(NULL)
		,_parent(NULL)
	{}
};

2、AVL树及相关实现

template
class AVLTree
{
	typedef AVLTreeNode Node;
public:
	AVLTree()
		:_root(NULL)
	{}
	
	void InOrder()
	{
		_InOrder(_root);
		cout<_left;
		Node *subLR=subL->_right;
		parent->_left=subLR;
		if(subLR)
			subLR->_parent=parent;
		subL->_right=parent;
		Node *ppNode=parent->_parent;
		parent->_parent=subL;
		if(ppNode == NULL)
		{
			_root=subL;
			subL->_parent=NULL;
		}
		else
		{
			if(ppNode->_left == parent)
				ppNode->_left=subL;
			else
				ppNode->_right=subL;
			subL->_parent=ppNode;
		}
	}
	void RotateL(Node *parent)//左旋转
	{
		Node *subR=parent->_right;
		Node *subRL=subR->_left;
		parent->_right=subR;
		if(subRL)
			subRL->_parent=parent;
		subRL->_left=parent;
		Node *ppNode=parent->_parent;
		parent->_parent=subR;
		if(ppNode == NULL)
		{
			_root=subR;
			subR->_parent=NULL;
		}
		else
		{
			if(ppNode->_left == parent)
				ppNode->_left=subR;
			else
				ppNode->_right=subR;
			subR->_parent=ppNode;
		}
	}
	void RotateRL(Node *parent)//右左旋转
	{
		Node *subR=parent->_right;
		Node *subRL=subR->_left;
		int bf=subR->_bf;

		RotateR(parent->_right);
		RotateL(parent);
		//更正平衡因子
		if(bf == 1)
		{
			parent->_bf=-1;
			subR->_bf=0;
		}
		else if(bf == -1)
		{
			parent->_bf=0;
			subR->_bf=1;
		}
		else // 0
		{
			subR->_bf=parent->_bf=0;
			subRL->_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=-1;
			subL->_bf=0;
		}
		else if(bf == -1)
		{
			parent->_bf=0;
			subL->_bf=1;
		}
		else // 0
		{
			subL->_bf=parent->_bf=0;
			subLR=0;
		}
	}

	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->_left;
			}
			else if(cur->_key < key)
			{
				parent=cur;
				cur=cur->_right;
			}
			else
				return false;
		}
		cur=new Node(key,value);
		if(parent->_key < key)
			parent->_right=new Node(key,value);
		else
			parent->_left=new Node(key,value);

		//更新平衡因子
		while(parent)
		{
			if(cur == parent->_right)
				parent->_bf++;
			else
				parent->_bf--;
			if(parent->_bf == 0) break; // 树平衡
			else if(parent->_bf == 1 || parent->_bf == -1)
			{
				cur=parent;
				parent=cur->_parent;
			}
			else // -2或2
			{
				//旋转
				if(parent->_bf == -2)
				{
					if(cur->_bf == -1)
						RotateR(parent);//右旋转
					else // -2
						RotateLR(parent);//左右旋转
				}
				else // 2
				{
					if(cur->_bf == 1)
						RotateL(parent);//左旋转
					else
						RotateRL(parent);//右左旋转
				}
				break;
			}
		}
		return false;
	}

protected:
	void _InOrder(Node *root)
	{
		if(_root == NULL) return;
		_InOrder(_root->_left);
		cout<<_root->_key<<" ";
		_InOrder(_root->_right);
	}
	int _Height(Node *root)
	{
		if(root == NULL) return 0;
		int left=_Height(root->_left);
		int right=_Height(root->_right);
		return left > right ? left+1 : right+1;
	}
protected:
	Node *_root;
};

3、总结:

    AVL树是对搜索二叉树的进一步优化,根据平衡因子使搜索二叉树高度平衡。其的插入、删除、查找都和搜索二叉树类似,只是需要注意平衡因子的问题。

    AVL树解决了搜索二叉树的退化问题,需要注意树的旋转问题及平衡因子的更新问题。

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


网页名称:数据结构--平衡二叉树AVL-创新互联
网页URL:http://dzwzjz.com/article/dehsdg.html
在线咨询
服务热线
服务热线:028-86922220
TOP