AVL树的插入详解

AVL树 

为什么有AVL树的出呢？其实我们用的map/multimap/set/multiset的底层并不是二叉搜索树的结构，因为二叉搜索树有一个很大的缺陷，就是当往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉搜索树进行了平衡处理，即采用平衡树来实现。也就是AVL树和红黑树。这篇内容先介绍AVL的实现。

概念

正是由于二叉搜索树的缺陷所以先有了AVL树，而AVL树的特征如下：

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1

所以说此时就可以保证AVL树的查找效率为：O(n*log2n) 

 

AVL树的节点定义

    template<class K,class V>
	struct AVLTreeNode
	{
		AVLTreeNode(const pair<K, V>& kv)
			:_left(nullptr)
			,_right(nullptr)
			,_parent(nullptr)
			,_kv(kv)//pair内部有实现自己的拷贝构造函数
			,_bf(0)
		{}
 
		AVLTreeNode<K,V>* _left;
		AVLTreeNode<K, V>* _right;
		AVLTreeNode<K, V>* _parent;
 
		pair<K, V> _kv;
		
		int _bf;//每个节点的平衡因子（right-left）
	};
 
    template<class K, class V>
	class AVL
	{
		typedef AVLTreeNode<K,V> Node;
	public:
		AVL()
		{}
 
 
    private:
		Node* _root = nullptr;
 
	};

首先我们要知道AVL树的数据类型一般都是K-V型，具体说也就是pair类型，而且AVL树和一般的树据关联是不同的，属于三叉连，也就是不仅仅要有左右指针还要有父指针，而父指针的目的就是在插入数据的时候可以更方便的处理祖宗节点的平衡因子。平衡因子的计算：右子树的高度—左子树的高度。

AVL树的插入

我们知道AVL树的实质其实也是优化后的的二叉搜索树，所以插入数据是比较容易的，核心也就是比较数据大小然后插入，但是不要忘了记录父节点的位置：

        bool insert(const pair<K,V>& kv)
		{
            //先判断是否为空树
			Node* newroot = new Node(kv);
			if (_root == nullptr)
			{
				_root = newroot;
				return true;
			}
			Node* parent = _root, *cur = _root;
 
			//插入数据
			while(1)
			{
				parent = cur;
				if (cur->_kv.first > kv.first)
				{
					cur = cur->_left;
					if (cur==nullptr)
					{
						parent->_left = newroot;
						newroot->_parent = parent;
						break;
					}
				}
				else if (cur->_kv.first < kv.first)
				{
					cur = cur->_right;
					if (cur==nullptr)
					{
						parent->_right = newroot;
						newroot->_parent = parent;
						break;
					}
				}
				else
				{
					return false;
				}
 
			}
        }

其实就仅仅插入数据来说的话，其实AVL树是挺简单的，但是真正的重头戏其实是处理平衡因子，因为平衡因子的值是有条件的：绝对值小于一，所以一般的数据插入对AVL树而言是行不通的，后续还需要对树的节点进行处理，使其平衡。所以接下来就有两步：

1. 处理平衡因子的值
2. 使不满足条件的二叉树进行调整成符合要求的AVL树        

---

平衡因子的值处理

对于平衡因子的值处理是比较轻松的，就是对于插入节点而言，若在其父节点的右边插入的话，父节点的平衡因子就+1，相反如果在左边插入的话，就将父节点的平衡因子-1，但是还没完，插入节点可能不仅仅只影响其父节点也可能会影响到插入节点的祖先节点。所以我们就要开始对插入数据之后的父节点平衡因子进行分析：

插入数据之后平衡因子只有以上三种可能的情况，因为当平衡因子为2或-2的时候就要进行调整的，而调整之后的平衡因子肯定不再是2或-2，所以如果平衡因子出现其他值的话就证明实现出了问题。

使不满足条件的二叉树进行调整成符合要求的AVL树        

其实我们就以先普通再一般的方式来研究树的半边，而另一半边就相当于这半边翻转过来的，所以此时研究一半就行。

就拿最简单的情况来说，当平衡因子而2时，那么此时就要开始调整树的走向了，使其能够满足AVL树的条件。

• 就拿左边这个图来说，当我们插入数据11时，7节点所在节点的平衡因子就要更新，此时会一直更新到根节点的位置处，但是此时发现根节点的平衡因子不满足条件，所以此时就要对该节点进行处理，使其平衡因子满足条件，此时几乎可以瞬间就想到：将7节点作为新的根节点，4节点作为7节点的左子树，此时不仅仅满足二叉搜索树，而且最主要的是插入之前该树根节点的平衡因子是1，而再插入调整之后，该树的平衡因子还是1，而该树也可能是其他节点的子树，所以调整之后也不用继续调整祖先节点的平衡因子，只需要调整这两个节点的平衡因子即可。而对于这种调整我们称为左单旋。
• 而有了第一种类型树的调整方式，那么对于第二棵树的调整方式就可以以此参考，对于第二种情况下，对于该树的调整方法如果采用和第一种一样的方法话，那就是进行因此左旋，而为了满足搜索二叉树的特性，就将7节点的左子树给4节点的右子树，所以此时会发现然而并没有发挥任何的作用，只不过将根节点的平衡因子从2变成-2了而已。也就是如下图：

 所以我们就可以换一种方式，先观察左右两幅图左图中属于连续一边插入，对应的平衡因子的符号是同号的，也就是说如果都是正的，则采用左单旋，那如果都是负的话就采用右单旋。但是右图的平衡因子的符号是异号的，所以仅仅通过一个单旋是无法解决的，此时我们就可以考虑将右图先进行右单旋，使其结构与左图的结构相同，然后再采用左单旋进行操作即可。而对于三个节点而言各自的平衡因子都是0.

以上皆属于对具体情况的分析，而实际上树的节点为2或-2时的情况是有很多种的，所以还是得进行抽象的分析。

左右单旋

左右单旋的情况其实就是针对直线型插入的情况，所以此时就有两种解决方案：左单旋、右单旋。

以右单旋的情况为例：

 

此时其实就是需要系那个30节点当作新的根，60节点当作30节点的右子树，b这个树给60节点的左边，此时就算是完成了。

而对于平衡因子而言，我们只需要知道一点，一个节点的平衡因子与该节点的左右子树高度差有关，所以说此时我们只需要判断节点的高度差就行了。而且AVL树的插入流程是先判断在哪里插入，然后在一步步的向上移动，直到节点的平衡因子为2或-2的时候进行调整处理，所以此时我们需要处理平衡因子的节点也就只有60和30两个节点，因为这两个节点的左右子树的位置是发生了改变，而且都为0。而且最重要的是插入数据之前该树高度和调整之后该树的高度是没有发生变化的，所以也不用再继续向上去调整节点平衡因子的值。

---

而且最容易忽视的就是将该树调整完了以后就直接跳出循环，其实我们还要判断该树的根节点是否有父节点（一定要提前存好，后面调整完之后指针指向会发生改变），如果有的话就要将该树新的根节点和其原来的父节点链接起来，如果没有的话就要将AVL树的根节点重置成调整后的新根节点。

单旋代码示例 

        void levorotation(Node* parent)//左单旋(_bf=2)
		{
			Node* childr = parent->_right;
			Node* childrl = childr->_left;
			Node* pparent = parent->_parent;//存父节点
 
			//链接起来
			childr->_left = parent;
			parent->_parent = childr;
			parent->_right = childrl;
			if(childrl)//有可能该节点为空
				childrl->_parent = parent;
			
			//链接父节点
			if (parent == _root)//处理父节点指向
			{
				_root = childr;
				childr->_parent = nullptr;
			}
			else
			{
				if (pparent->_right == parent)
					pparent->_right = childr;
				else
					pparent->_left = childr;
 
				childr->_parent = pparent;
			}
 
			//处理平衡因子
			parent->_bf = childr->_bf = 0;//
		}
 
		void dextrorotation(Node* parent)//右单旋(_bf=-2)
		{
			Node* childl = parent->_left;
			Node* childlr = childl->_right;
			Node* pparent = parent->_parent;;
 
			childl->_right = parent;
			parent->_parent = childl;
			parent->_left = childlr;
			if (childlr)
				childlr->_parent = parent;
			
			if (_root == parent)
			{
				_root = childl;
				childl->_parent = nullptr;
			}
			else
			{
				if (pparent->_left == parent)
					pparent->_left = childl;
				else
					pparent->_right = childl;
 
				childl->_parent = pparent;
			}
				
			//处理平衡因子
			parent->_bf = childl->_bf = 0;//
		}

实现代码时，需要我们注意的是：三叉链结构别忘了父指针的调整，以及对于空指针的访问，所以具体实现的过程中还是有很多的细节。

左右双旋

左右双旋相较于单旋而言其实就是double，而需要左右单旋的情况我们一般可以称为折线型插入，所以说我们也是先拿抽象图进行具体分析：

对于双旋的情况其实 真正复杂的点就是平衡因子的变化，就上图而言，我们知道当在60节点的下方插入数据时就需要采用双旋来解决。而对于插入数据又有两种情况：

不同的情况下数据所对应的平衡因子是不相同的，也就是在插入数据以后60这个节点的平衡因子会有两种可能，也就是表明对于不同的插入，调整之后的平衡因子可能不一样：

所以说我们双旋之后的平衡因子的更改就可以依据60这个节点的平衡因子是正还是负，而且在调整之后不难发现60节点成为了新的根节点，60节点的左子树变成了30节点的右子树，而60节点的右子树变成了90节点的左子树。

而且在插入数据之后调整平衡因子的过程最终并没有影响该树的高度所以也不会影响该该树的父节点的平衡因子。

---

而且最容易出错的是代码写的太过冗余，我们一定要将90,60,30这三个节点先存起来，因为我们双旋其实就是复用两次单旋的函数而实现的，所以说在单旋完成之后父亲“”还是不是“父亲”就真的说不准了，所以最后调整平衡因子的时候就可以直接调整。

 双旋代码示例

                else//parent->_bf=-2或2则需要旋转
				{
					//原来parent->_bf为-1或者1
					if (parent->_bf == 2 && newroot->_bf == 1)//左单旋
						levorotation(parent);
					else if (parent->_bf == -2 && newroot->_bf == -1)//右单旋
						dextrorotation(parent);
					else if (parent->_bf == 2 && newroot->_bf == -1)//
					{
						Node* newrootl = newroot->_left;//记录下来该节点
 
						//先右单旋再左单旋
						int bf = newrootl->_bf;//记录插入节点的位置
						dextrorotation(newroot);
						levorotation(parent);
						
						//旋转以后节点以及换过位置newroot->_left变成新的父节点
						if (bf == 0)
						{
							parent->_bf = newroot->_bf = newrootl->_bf = 0;
						}
						else if (bf == 1)
						{
							newrootl->_bf = 0;
							parent->_bf = -1;
							newroot->_bf = 0;
						}
						else if(bf==-1)
						{
							newrootl->_bf = 0;
							parent->_bf = 0;
							newroot->_bf = 1;
						}
							
					}
					else if (parent->_bf == -2 && newroot->_bf == 1)
					{
						Node* newrootr = newroot->_right;//记录下来该节点(旋转的是会改变节点指向)
 
						//同理
						int bf = newrootr->_bf;
						levorotation(newroot);
						dextrorotation(parent);
 
						parent->_bf = 0;
						if (bf == 0)
							newrootr->_bf = parent->_bf = newroot->_bf = 0;
						else if (bf == 1)
						{
							newrootr->_bf = 0;
							parent->_bf = 0;
							newroot->_bf = -1;
						}
						else if (bf == -1)
						{
							newrootr->_bf = 0;
							parent->_bf = 1;
							newroot->_bf = 0;
						}
					}
					return true;
				}