AVL部分功能实现和了解

我先前写过一篇二叉搜索树的博客，在那篇博客中我介绍了二叉搜索树的k结构和kv结构实现法，当时也留了个问题，就是普通的二叉搜索树是有缺陷的，可能会退化为链表，从而使得搜索效率降低为O(n)，解决方法是对二叉搜索树调平衡，下面实现的AVL树以及后面提及红黑树的实现都将二叉搜索树调平衡了。

一 节点类

  大家可以看到我们在节点类中增加了一个变量_v1，_v1存的是平衡因子，这个平衡因子是用右子树的高度减去左子树高度得到的, 这个树还是一个三叉链(除了_left和_right指针，还有_parent指针指向父节点)的结构，三叉链结构对于后续平衡因子的更新有十分大的作用。

template<class T,class k> kv结构二叉树
struct AVLTreeNode
{
	
	AVLTreeNode(const pair& p1)
		:_p1(p1)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		, _v1(0)
	{
		;
	}
	pair _p1; 用一个pair存放key和val，方便一起把key和val返回，使用要包含头文件
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	int _v1;//存放平衡因子
};

 二 AVL树类

这个类是通过管理_root来达到管理，描述整棵树，其实用一个类也可以起作用，在节点类多加一个_root指针不就OK了，至于为什么要将管理树的管理节点的分成两个类，感觉是一种玄妙的设计思想，每个节点都加上_root指针，实际上每个节点却用不上_root指针，这就使得每个节点都会存一个无用信息，有些场景旋转是会改变根的，你想想每个节点都存_root，维护起来太麻烦了，为了树的封装性，用类封装_root，使其不被外界随意访问也是非常有意义的，而insert，find函数都要获取根，所以注定了树的成员函数和_root指针一起封装。

   AVL本质还是个二叉搜索树，只是它规定左右子树的高度差必须小与等于1，这时候肯定有人想问，为什么不能是零呢，这样不就绝对完美平衡吗，因为太难了，你想想高度差为零只有在满二叉树才会出现，而现实中几乎很难遇到这样的树。接下来我们一步步实现AVL树，首先实现insert功能。

1 插入新节点

由于AVL树本质就是二叉搜索树，所以在插入节点时还是比大小来判断是插入在根节点的左边还是右边插入。如果之前我们就实现了一下二叉搜索树，找插入位置插入节点的代码还是很简单的。麻烦的是更新平衡因子。要分多种情况，我们将插入节点称为newnode，其双亲节点为parent，

 
template<class T, class k>
class AVLTree
{
public:
	typedef AVLTreeNode Node;
	bool Insert(const pair& p1)
	{
		if (_root == nullptr)
		{
			_root = new Node(p1);
			return true;
		}
		Node* cur = _root;
		Node* parent = _root;
		while (cur)//按照搜索二叉树规则插入节点
		{
			if (cur->_p1.first
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_p1.first > p1.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		当cur等于nullptr时,
		插入节点
		cur = new Node(p1);
		if (parent->_p1.first>p1.first)//小于parent的key,插入到左边
		{
			 parent->_left = cur;
		}
		else //大于parent的key,插入到右边
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
 
		
		return true;
	}
	
	
	Node* _root=nullptr;  根节点指针,要初始化为nullptr
};

2 平衡因子的更新

下面代码都在while循环内，不好分离开，只能将解析放在里面了。

更新平衡因子
		while (parent)
		{
			if (parent->_left == cur)  插入节点在parent的左侧，平衡因子--
			{
				parent->_v1--;
			}
			else 
			{
				parent->_v1++;   插入节点在parent的左侧，平衡因子++
			}
 
 
重点来了，当更新后parent的平衡因子为-1/1,这说明先前为0，不可能是2,-2，
因为后面会对这两种情况做处理，
先前_v1==0,说明两边高度一致，现在变为-1,1，说明parent所在树高度变了，要更新parent的双亲节点的平衡因子。
 
			if (parent->_v1 == -1 || parent->_v1 == 1)
			{
				cur = parent;
				parent=parent->_parent;
				
			}
			else if (parent->_v1 == 0)  
                                     先前是-1/1，是一边高的，现在变成0,变成两边一样高
                                     parent所在子树最大高度不变，无需更新
			{
				break;
			}
 
           else if (parent->_v1 == -2||parent->_v1==2)//旋转
			{
				if (parent->_v1 == 2 && cur->_v1 == 1)
					RotateL(parent);
				else if (parent->_v1 == -2 && cur->_v1 == -1)
					RotateR(parent);
				else if (parent->_v1 == 2 && cur->_v1 == -1)
					RotateRL(parent);
				else if (parent->_v1 == -2 && cur->_v1 == 1)
					RotateLR(parent);
				else
					assert(false);
				return true;
			}
			else
			{
				assert(false);
			}
			
		}

旋转大家只要先知道平衡因子为-2/2时要用旋转解决就好，原理会在下面旋转示意图中解析。

3 旋转示意图

为了更好理解旋转，我画了几个图来说明不同的旋转。

1 左单旋

  上图是所有左单旋的场景，我们假设节点5是要进行左旋转的点，插入前平衡因子就必须是1(那我们就假设节点5的左树高n，右树高n+1)，插入节点后变为2，那节点就是在5的右树插入的，而且也必须是在6节点的右树，如果是在6节点的左树，这种在双旋会再提及。那6节点，7节点先前的平衡因子很明显也就只能是0，只有这样平衡因子的更新才会波及到节点5(-1会停止，1则是在节点6进行旋转，不符合假设在节点5进行旋转)，那6节点的左树，右树高都是n，7节点的左树，右树高都是n-1。

对5进行左单旋: 如果节点6的左树不为空，就把节点6的左树给节点5的_right指针，节点5整颗树做节点的左树。(只有这样能保证二叉搜索树中左树小于根，右子树大于根的特性)

void RotateL(Node* parent)//左旋转
	{
		Node* cur = parent->_right;
		Node* Curleft = cur->_left;
		//旋转
		Node* pparent = parent->_parent;
		cur->_left = parent;
		parent->_right = Curleft;
		parent->_parent = cur;
		cur->_parent = pparent;
 
		if (Curleft)   cur的左子树不为空时
		{
			Curleft->_parent = parent;
		}
 
		平衡因子修改
 
		parent->_v1 = 0;
		cur->_v1 = 0;
		if (parent == _root)//改变根
		{
			_root = cur;
		}
		else//和上一层链接
		{
			if (pparent->_left == parent)
				pparent->_left = cur;
			else
				pparent->_right = cur;
		}
	}

旋转结果，代码要画图结合旋转过程才好理解，毕竟涉及到多个节点的链接。

此时我们可以肯定的把节点5，6的平衡因子改为0，因为我们把6的左树(高为h)给了节点5，那节点5左右树高度相同，因子为零没毛病，而6的因子在更新中变成了1，但是由于左树高度变成n+1了，也为零，而7的平衡因子在插入的时候就会被更新成1或者-1，不用处理。(最后提一下就是当树高n=0时，节点7就是新插入节点)

2 右单旋

再来看看右单旋，还是假设节点5为旋转点，5的平衡因子必是-1，那节点4和节点3的平衡因子都是0，道理如上。此时插入节点必须是4的左树，在右树是双旋的另一个场景。还有就是插入节点可以是3的左树，也可以是右树，甚至可能就是节点3本身，但是都可以用右单旋搞定。

对5进行右单旋: 如果节点4的右树不为空，就把节点4的右树给节点5的_left指针，节点5整颗树做4节点的右树。如下图，还是一颗二叉搜索树。

	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* Curright = cur->_right;
		//旋转
		Node* pparent = parent->_parent;//记录该树parent节点的父节点
		cur->_right = parent;
		parent->_left = Curright;
		parent->_parent = cur;
		cur->_parent = pparent;
 
		if (Curright)//cur的右子树不为空时
		{
			Curright->_parent=parent;
		}
 
		//平衡因子修改
		parent->_v1= 0;
		cur->_v1 = 0;
 
		if (parent == _root)//改变根
		{
			_root = cur;
		}
		else//和上一层链接
		{
			if (pparent->_left == parent)
				pparent->_left = cur;
			else
				pparent->_right = cur;
		}
	}

3 右左双旋

之前说左单旋的插入节点必须是节点7(当时这个节点位置数据是6，我们要对应位置，而不是对应值)这个位置的右树才发生右单旋，如果是7的左树则是双旋，我们举个例子，当n=0时，节点6就是插入节点，这个时候如果还是用右单旋，大家可以试试结果会是平衡的吗?

 

结果如下,我都不用画平衡因子来验证了。这说明这种情况无法用单旋保持平衡。

好，我们再来看一般情况。

还是假设节点5是是更新后平衡因子为2的节点，那一开始必然是1，那就设左树高为n，右树高为n+1，而节点6，7因子均为0，那7的右树就为n，6的左右树均为n-1(也可能一边高，但我们为了简化，使得在六的左树和右树插入一定导致节点6这颗树高度增大)。

右左双旋:先对节点7做右旋，结果如下，下一步是对5进行左旋，那就不会影响节点7的平衡因子了，此时是0。下图为情况(1)：在6的右树插入节点

可是如果新插入节点是6节点的左树，此时节点7的平衡因子就应该是1，也就是说7的平衡因子是要分情况讨论的。下图为情况(2)：在6的左树插入节点

再对节点5做左旋，

下图为情况(1)的左旋：在6的右树插入节点

下图为情况(2)的左旋图：在6的左树插入节点

这时候有两个有意思的点，双旋就是把节点6的右树给节点7，然后把左树给了节点5，节点6做了根，而bf=1或者为-1，就会对节点5和节点7的平衡因子有影响，我们惊奇的发现，最后平衡因子结果是可以知道的。(这里是需要画图慢慢理解的，这里就已经是比较复杂的，相信自己一定可以弄明白的)

void RotateRL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
        int bf=cur->_left->_v1;  保存图中节点6的平衡因子
		RotateR(cur);
		RotateL(parent);
 
        if (bf == 0)  等于0说明节点6本身是新插入节点，此时5,6，7节点因子归零即可
		{
			cur->_v1 = 0;
			parent->_v1 = 0;
			Curright->_v1 = 0;   在左单旋和右单旋中我们都粗暴地对旋转节点和它的子节点的
                                 平衡因子归零，为什么出来还要再写一遍呢?
                                 这是为了解耦，防止单旋代码影响了双旋代码
		}
		else if (bf == 1)
		{
            cur->_v1 = 0;
			curleft->_v1 = 0;
			parent->_v1 = -1;
		}
		else if (bf == -1)
		{
            cur->_v1 = 1;
            curleft->_v1 = 0;
			parent->_v1 = 0;
		}
		else
			;
	}

4 左右双旋

从前面介绍的右左双旋我们知道双旋实质上是由单旋构成的，也就是说我们可以复用单旋的代码。

先前在介绍右单旋的时候提到，如果插入节点是节点4的右树，那就要双旋，如下例子。

此时可以用这个图试试用右单旋，结果就是这样。

好，我们再来看左右双旋的一般情况。

再次强调，当n=0时,节点4就是新插入节点。

我就直接开始介绍左右双旋如何旋吧，先以节点3作为旋转点做左单旋；

然后就是对节点五进行右单旋。结果如下

节点3的左树和节点5的右树就是原来节点4的子树，如果我们是在节点4的左子树插入一个节点，此时节点3的平衡因子就应该是0，节点5就应该是1。相反，如果插入在节点4的右子树，那5的平衡因子就应该是0, 3的平衡因子就应该是1。代码如下

 
	void RotateLR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* Curright = cur->_right;
		int bf = cur->_right->_v1;
		RotateL(cur);
		RotateR(parent);
		if (bf == 0)//解耦
		{
			cur->_v1 = 0;
			parent->_v1 = 0;
			Curright->_v1 = 0;
		}
		else if (bf == 1)
		{
			parent->_v1 = 0;
			cur->_v1 = -1;
			Curright -> _v1 = 0;
		}
		else if (bf == -1)
		{
			cur->_v1 = 0;
			parent->_v1 = 1;
			Curright -> _v1 = 0;
		}
	
	}
 

三 AVL树检验

这一步很重要，很多时候我们运行成功了，不能说明代码没问题，随便弄一个测试用例也不足以说明代码没问题，最好的办法就是用大量的随机数产生的序列来测试，大量，越多越好，亲身经历，有时候十几个随机数没问题，二十几个就出问题了，这时候真的很坑，这个时候我是打印了一串出错的序列，然后一步步画图调试，才找到问题。接下来就看看如何检验的吧。

AVL树首先是二叉搜索树，而且每个节点的左右子树高度差小于1，所以我们只要检查这两个特性就好了。

二叉搜索树我没检验，因为我直接copy我上篇博客写的二叉搜索树代码，之前没问题，应该可以直接用，嘻嘻。

int Height(Node*root)
{
	if (root == nullptr)
		return 0;
	int left = Height(root->_left);
	int right = Height(root->_right);
	return right > left ? right + 1 : left + 1;
}
 
bool isBlanceTree()
{
	return isBlanceTree(_root);
}
 
 
前序遍历,反复求高度
bool isBlanceTree(Node* root)
{
	if (root == nullptr)//根为空,返回true
		return true;
 
	int left = Height(root->_left);//去计算左子树高度
 
	int right = Height(root->_right);//去计算又子树高度
 
	int bf = (right - left);//这是我们算的平衡因子
 
	if (bf != root->_v1 || bf > 1 || bf < -1)//如果和_v1不同或者，_v1的值不合规，就不是AVL
		return false;
 
   去看看根的左子树和右子树的根是否合理
	return isBlanceTree(root->_left) && isBlanceTree(root->_right);
}

前序遍历求每个节点的平衡因子的效率是偏低的，因为我们做了大量的重复计算。比如一开始计算的是_root的平衡因子是否符合要求，那就要算每个节点的左右子树高，而_root-left和_root-right的平衡因子计算又要再求这些节点高度。

所以我们可以优化一下。

优化，合并为后序
 
   int isBlanceTree3(Node* root,bool& a)用参数a记录子树是否合格
	{
		if (root == nullptr)
		{
			a = true;
			return  0;
		}
		//去子树确认平衡因子是否正确
 
		int left = isBlanceTree3(root->_left,a);
		bool lefta = a;
 
		int right = isBlanceTree3(root->_right,a);
		bool righta = a;
 
		//计算根的平衡因子
		int bf = (right- left);
 
		//计算root子树最大高度
		int Max = left > right ? left: right;
 
		//确认根的平衡因子是否和bf相同,以及bf是否合法
 
		if (bf != root->_v1 || bf > 1 || bf < -1)
		{
			a = false;
			return Max;
		}
		//左右子树合格,根合格,返回树高度加1
 
		if (lefta && righta)
		{
			return Max + 1;
		}
		else
			return 0;
		
	}

当我们遇到难的知识点，说明我们在爬坡，过去了就成长了。