【数据结构】AVL树的旋转和插入

数据结构 前端之家
前端之家收集整理的这篇文章主要介绍了【数据结构】AVL树的旋转和插入，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

AVL树

左单旋


代码实现

void _RotateL(Node* parent)
	{
		Node* subR=parent->_right;
		Node* subRL=subR->_left;
		Node* ppNode=parent->_parent;
		subR->_left=parent;
		parent->_right=subRL;
		if(subRL)
			subRL->_parent=parent;
		if(ppNode==NULL)
		{
			_root=subR;
		    subR->_parent=NULL;
		}
		else if(ppNode->_left==parent)
		{
			ppNode->_left=subR;
			subR->_parent=ppNode;
		}
		else//(ppNode->_right==parent)
		{
			ppNode->_right=subR;
			subR->_parent=ppNode;
		}
	    subR->_bf=parent->_bf=0;
	}


右单旋


实现

void _RotateR(Node* parent)
	{
		Node* subL=parent->_left;
		Node* subLR=subL->_right;
		Node* ppNode=parent->_parent;
		subL->_right=parent;
		parent->_left=subLR;
		if(subLR)
         subLR->_parent=parent;
		if(ppNode==NULL)
		{
			_root=subL;
			subL->_parent==NULL;
		}
		else if(ppNode->_left==parent)
		{
			subL->_parent=ppNode;
			ppNode->_left=subL;
		}
		else if (ppNode->_right==parent)
		{
			subL->_parent=ppNode;
			ppNode->_right=subL;
		}
		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)
		{
			subL->_bf=subLR->_bf=parent->_bf=0;
		}
		else if (bf==-1)
		{
			parent->_bf=1;
			subLR->_bf=subL->_bf=0;
		}
		else
		{
			subL->_bf=-1;
			subLR->_bf=parent->_bf=0;
		}
		
	}


右左旋


实现

void _RotateRL(Node* parent)
	{
		Node* subR=parent->_right;
		Node* subRL=subR->_left;
		int bf=subRL->_bf;
		_RotateR(parent->_right);
		_RotateRL(parent);
		if(bf==0)
		{
			subR->_bf=parent->_bf=0;
		}
		else if(bf==-1)
		{
			parent->_bf=subR->_bf=0;
			subRL->_bf=1;
		}
		else
		{
			parent->_bf=-1;
			subR->_bf=subRL->_bf=0;
		}
	}

两个特殊测试用例



解决这两个特殊用例的部分代码（具体实现在插入函数）

 else
		  {
			if(parent->_bf == 2)
			{
				if(cur->_bf == 1)
				{
					_RotateL(parent);
				}
				else if(cur->_bf==-2)
				{
					_RotateRL(parent);
				}
			}
			else if(parent->_bf==-2)
			{ 
				if(cur->_bf == -1)
				{
					_RotateR(parent);
				}
				else if(cur->_bf==2)
				{
					_RotateLR(parent);
				}
			}

插入函数 
	bool Insert(const K& key,const V& value)
	{
		Node* newNode=new Node(key,value);
		if(_root==NULL)
		{
			_root=newNode;
			return true;
		}
      Node* parent=NULL;
	  Node* cur=_root;
      
	  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);
	  cur->_parent=parent;
	  if(parent->_key>key)
		  parent->_left=cur;
	  else if(parent->_key<key)
		  parent->_right=cur;
	  while (parent)
	  {
		  if(parent->_left==cur)
		  {
			  --parent->_bf;
		  }
		  else if(parent->_right==cur)
		  {
			  ++parent->_bf;
		  }
		  if(parent->_bf==0)
		  {
			  return true;
		  }
		  if(abs(parent->_bf)==1)
		  {
			  cur=parent;
			  parent=parent->_parent;
		  }

		 else
		  {
			if(parent->_bf == 2)
			{
				if(cur->_bf == 1)
				{
					_RotateL(parent);
				}
				else if(cur->_bf==-2)
				{
					_RotateRL(parent);
				}
			}
			else if(parent->_bf==-2)
			{ 
				if(cur->_bf == -1)
				{
					_RotateR(parent);
				}
				else if(cur->_bf==2)
				{
					_RotateLR(parent);
				}
			}
			else
			return true;
		}
	}
	return true;
}

全部代码

AVLtree.h

#include<iostream>
using namespace std;
template<class K,class V>
struct AVLtreeNode
{
	AVLtreeNode<K,V>* _left;
	AVLtreeNode<K,V>* _right;
	AVLtreeNode<K,V>* _parent;
	K _key;
	V _value;
	int _bf;
	AVLtreeNode(const K& key,const V& value)
		:_left(NULL),_right(NULL),_parent(NULL),_key(key),_value(value),_bf(0)
	{}
};
template<class K,class V>
class AVLtree
{
	typedef AVLtreeNode<K,V> Node;
public:
	AVLtree()
		:_root(NULL)
	{}
	~AVLtree()
	{}
	bool Insert(const K& key,value);
	  cur->_parent=parent;
	  if(parent->_key>key)
		  parent->_left=cur;
	  else if(parent->_key<key)
		  parent->_right=cur;
	  while (parent)
	  {
		  if(parent->_left==cur)
		  {
			  --parent->_bf;
		  }
		  else if(parent->_right==cur)
		  {
			  ++parent->_bf;
		  }
		  if(parent->_bf==0)
		  {
			  return true;
		  }
		  if(abs(parent->_bf)==1)
		  {
			  cur=parent;
			  parent=parent->_parent;
		  }

		 else
		  {
			if(parent->_bf == 2)
			{
				if(cur->_bf == 1)
				{
					_RotateL(parent);
				}
				else if(cur->_bf==-2)
				{
					_RotateRL(parent);
				}
			}
			else if(parent->_bf==-2)
			{ 
				if(cur->_bf == -1)
				{
					_RotateR(parent);
				}
				else if(cur->_bf==2)
				{
					_RotateLR(parent);
				}
			}
			else
			return true;
		}
	}
	return true;
}
	void Inorder()
	{
		_Inorder(_root);
		cout<<endl;
	}
	int Height()
	{
	return	_Height(_root);
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	bool IsBalanceOP()
	{
		int Height=0;
		
         return _IsBalanceOP(_root,Height);
	}

protected:
	void _Inorder(Node* root)
	{
		if(root==NULL)
			return;
		_Inorder(root->_left);
		cout<<" KEY:  "<<root->_key<<" VALUE:  "<<root->_value<<" BF:  "<<root->_bf<<endl;
		_Inorder(root->_right);
	}
	int _Height(Node* root)
	{
		if(root==NULL)
			return 0;
	    int left=_Height(root->_left)+1;
		int right=_Height(root->_right)+1;
		return left>right ? left:right;
	}
	bool _IsBalance(Node* parent)
	{
		if(parent==NULL)
			return true;
		int bf=_Height(parent->_right)-_Height(parent->_left);
		if(parent->_bf!=bf)
		{
			cout<<"不是平衡树"<<parent->_key<<endl;
			return false;
		}
		return _IsBalance(parent->_left);
		return _IsBalance(parent->_right);
	}
	bool _IsBalanceOP(Node* root,int height)
	{
		if (root==NULL)
		{
			height=0;
			return true;
		}
		int leftHeight=0;
		if(_IsBalanceOP(root->_left,leftHeight)==false)
			return false;
		int rightHeigt=0;
		if(_IsBalanceOP(root->_right,rightHeigt)==false)
			return false;
		return true;
	}
	void _RotateL(Node* parent)
	{
		Node* subR=parent->_right;
		Node* subRL=subR->_left;
		Node* ppNode=parent->_parent;
		subR->_left=parent;
		parent->_right=subRL;
		if(subRL)
			subRL->_parent=parent;
		if(ppNode==NULL)
		{
			_root=subR;
		    subR->_parent=NULL;
		}
		else if(ppNode->_left==parent)
		{
			ppNode->_left=subR;
			subR->_parent=ppNode;
		}
		else//(ppNode->_right==parent)
		{
			ppNode->_right=subR;
			subR->_parent=ppNode;
		}
	    subR->_bf=parent->_bf=0;
	}
	void _RotateR(Node* parent)
	{
		Node* subL=parent->_left;
		Node* subLR=subL->_right;
		Node* ppNode=parent->_parent;
		subL->_right=parent;
		parent->_left=subLR;
		if(subLR)
         subLR->_parent=parent;
		if(ppNode==NULL)
		{
			_root=subL;
			subL->_parent==NULL;
		}
		else if(ppNode->_left==parent)
		{
			subL->_parent=ppNode;
			ppNode->_left=subL;
		}
		else if (ppNode->_right==parent)
		{
			subL->_parent=ppNode;
			ppNode->_right=subL;
		}
		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)
		{
			subL->_bf=subLR->_bf=parent->_bf=0;
		}
		else if (bf==-1)
		{
			parent->_bf=1;
			subLR->_bf=subL->_bf=0;
		}
		else
		{
			subL->_bf=-1;
			subLR->_bf=parent->_bf=0;
		}
		
	}
	void _RotateRL(Node* parent)
	{
		Node* subR=parent->_right;
		Node* subRL=subR->_left;
		int bf=subRL->_bf;
		_RotateR(parent->_right);
		_RotateRL(parent);
		if(bf==0)
		{
			subR->_bf=parent->_bf=0;
		}
		else if(bf==-1)
		{
			parent->_bf=subR->_bf=0;
			subRL->_bf=1;
		}
		else
		{
			parent->_bf=-1;
			subR->_bf=subRL->_bf=0;
		}
	}
private:
	Node* _root;
};
void TestAVLtree1()
{
	AVLtree<int,int> At;
	At.Insert(0,1);
	At.Insert(1,1);
	At.Insert(2,1);
	At.Insert(3,1);
	At.Insert(4,1);
	At.Insert(5,1);
	At.Insert(6,1);
	At.Insert(7,1);
	At.Insert(8,1);
	At.Insert(9,1);
    At.Insert(10,1);
	At.Insert(11,1);
	At.Inorder();
	cout<<At.IsBalance()<<endl;

}
void TestAVLtree2()
{
	
	AVLtree<int,int> At;
	At.Insert(4,1);
	At.Insert(15,1);
	At.Insert(16,1);
	At.Inorder();
	cout<<At.IsBalance()<<endl;

}
void TestAVLtree3()
{

	AVLtree<int,int> At;
	At.Insert(16,1);
	At.Insert(26,1);
	At.Insert(18,1);
	At.Insert(14,1);
	At.Inorder();
	cout<<At.IsBalanceOP()<<endl;

}

main.cpp 
#include "AVLtree.h"
#include <cstdlib>
int main()
{
	TestAVLtree1();
	TestAVLtree2();
	TestAVLtree3();
	system("pause");
	return 0;
}
原文链接：https://www.f2er.com/datastructure/382422.html

猜你在找的数据结构相关文章

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test