AVL树详解

需求

我们在学习二叉搜索树的时候，发现无论是查找还是插入元素在理想情况下都可以达到O(logN)级别，但是由于插入的顺序，数的结构也会不同，这种理想情况很难保持甚至最坏的情况会退化成链表。导致性能下降。这时就需要一个能实现高度自动平衡的树结构。就出现了平衡树，
今天讲的是平衡树的一种：AVL树。

初识AVL树

AVL树得名与 Adelson-Velsky和 Landis两位发明者的首字母，它是自平衡的二叉搜索树，具有二叉树搜索树的性质（左子树的结点都比当前结点小，右子树都比当前结点大），同时它又是平衡二叉树，能够自适应高度。在AVL树中，任意节点的两个子树的高度差不超过1，这也是将不平衡的子树调整为平衡子树的重要指标。

AVL树的调整策略

AVL是在进行插入节点时，通过检测是否破坏了平衡条件，进而通过进行一定程度的节点旋转来达到整棵树的平衡。

简单情形

我们知道一个树如果只有一个或两个时，树是平衡的。所以问题会出现在第三个节点插入的位置，如果是下图：

则是平衡的。

先来看最简单的不平衡情况：

当把根节点的右节点“提”到根节点的位置，将旧根节点当新的根节点的左子节点。就可达到平衡状态。

具体到树中，可以归结为以下四种情况：

1.左旋

上述是最特殊的只有三个节点的情况，下面我们将它代入一般的二叉树来研究：

对于一个节点，当右子树的高度比左子树高一个高度的时候，此时新进来的节点也需要插入右子树。当然，如果新插入节点以后，右子树还维持原来的高度，那么这颗树就还是平衡的。问题出在当新插入节点后，右子树的高度增加了，这时破坏了平衡树两个子树的高度差不超过一的性质，就需要调整使其达到平衡状态。这时，我们首先考虑比较好处理的情况，也就是插在右子树的右边的情况。

调整的策略：

此时我们需要将当前节点的右子树“提”到当前节点的位置，当前节点“下降”为其右子树的左子树，具体操作过程如图：

调整之后变为：

到此，树变成了平衡的，由于整棵树要往左边旋转，所以左旋的操作就右子树的地位上移，根节点的地位下降。

2.右旋

现在我们有了左旋的经验，很容易推出需要进行右旋操作的时机：

对于一个节点，当左子树的高度原先就比右子树的高度多一时，插入节点又使左子树的高度增加，并且插在了左子树的左边的时候，就需要调整了：

树变为平衡的。

至此，单旋转就学习完毕，下面学习双旋转。

3.右左旋

前面我们学习单旋转时，插入节点都是与其子树同向的位置，这种情况由于倾斜的状况比较明显，所以只要找到中间的位置，将其“提”到“根节点”的位置，就可以达到平衡。而当其中子树失去平衡是由于所处子树往相反的方向插入，导致倾斜的状况不容易看出，所以需要经过两次旋转来达到平衡状态。
如下图：

我们可以观察到，在当前的结点的右子树的倾斜情况与我们刚才介绍到的右旋的情况很相似：

所以将右子树按右旋处理，处理之后变为：

这时我们惊奇的发现它变成了我们前面介绍的左旋前时的情形。这种情况我们已经会处理了：将右子节点“提”上来，把当前“根”节点变为右子节点的左子树，最后就调整到平衡状态了。

4.左右旋

同样地，左右旋也可通过先将左子树左旋，再将当前根节点右旋的调整来达到平衡状态。

先将左子树左旋：

再进行右旋：

达到平衡状态。

---

到此，二叉树的调整策略就介绍完了，下面上代码：

typedef struct AVLNode* AVLTree;
struct AVLNode{
	int data;
	AVLTree left;
	AVLTree right;
	int height;
	AVLNode(int data):data(data){
		left = NULL;
		right = NULL;
		height = 0;
	}
};

int Max(int a, int b){
	return a > b ? a : b;
}

int GetHeight(AVLTree t){
	if(!t) return 0;
	return t->height;
}

//右旋 
AVLTree SingleRightRotation(AVLTree A){
	//先记录左子树,将左节点的右子树变为根节点的左子树，再将根节点作为左节点的右子树。 
	AVLTree l = A->left;
	A->left = l->right;
	l->right = A;
	//更新两节点的高度。 
	A->height = Max(GetHeight(A->left),GetHeight(A->right))+1;
	l->height = Max(GetHeight(l->left),A->height) + 1;
	return l; 
}

//左旋 
AVLTree SingleLeftRotation(AVLTree A){
	//先记录右子树,将右节点的左子树变为根节点的右子树，再将根节点作为右节点的左子树。 
	AVLTree r = A->right;
	A->right = r->left;
	r->left = A;
	//更新两节点的高度。 
	A->height = Max(GetHeight(A->left),GetHeight(A->right)) + 1;
	r->height = Max(GetHeight(r->right),A->height) + 1;
	return r;
}

//右左旋 
AVLTree DoubleRightLeftRotation(AVLTree A){
	//将左子树右旋 
	A->right = SingleRightRotation(A->right);
	//再将当前节点左旋 
	return SingleLeftRotation(A);
} 

//左右旋 
AVLTree DoubleLeftRightRotation(AVLTree A){
	//将右子树左旋 
	A->left = SingleLeftRotation(A->left);
	//再将当前节点右旋 
	return SingleRightRotation(A);
} 

AVLTree Insert(AVLTree T, int X){
	if(!T){
		T = new AVLNode(X);
	}else if(X < T->data){
		T->left = Insert(T->left,X);
		if(GetHeight(T->left)- GetHeight(T->right) == 2){
			if(X < T->left->data){ //右旋 
				T = SingleRightRotation(T);
			}else{ //左右旋 
				T = DoubleLeftRightRotation(T);
			}
		}
	}else if(X > T->data){
		T->right = Insert(T->right,X);
		if(GetHeight(T->right)- GetHeight(T->left) == 2){
			if(X > T->right->data){ //左旋 
				T = SingleLeftRotation(T);
			}else{ //右左旋 
				T = DoubleRightLeftRotation(T);
			}
		}
	}
	//更新高度 
	T->height = Max(GetHeight(T->left),GetHeight(T->right))+1;
	return T;
}