平衡二叉树基本操作（AVL平衡二叉树）

概念

平衡二叉树，又称为AVL树。
定义：平衡二叉树或为空树，或满足如下性质的二叉树：
①首先是一个二叉搜索树
②左右子树深度之差的绝对值不超过1
③左右子树仍然为平衡二叉树
平衡因子 BF=左子树深度-右子树深度
平衡二叉树的每个节点的平衡因子只能是-1，1，0.若其绝对值是1，则该二叉排序树就是不平衡的。

插入节点的调整方法

若向平衡二叉树中插入一个节点后破坏了平衡二叉树的平衡性，首先从根结点到该新插入节点的路径之逆向根结点方向找到第一个失去平衡的节点，然后以该失衡节点和它相邻的刚查过的两个节点构成调整子树，使之称为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原来其他所有不平衡子树无需调整，整个二叉排序树就又成了一个平衡二叉树。
失去平衡的最小子树是指以离插入节点最近，且平衡因子绝对值大于1的节点作为根的节点作为根的子树。
①LL型平衡旋转法
由于在A的左孩子B的左子树上插入节点F，使A的平衡因子由1增至2失去平衡，故需进行依次顺时针旋转操作。即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转称为B的右子树的根结点。而原来B的右子树则变成A的左子树。

②RR型平衡旋转法
由于在A的右孩子C的右子树上插入节点F，使A的平衡因子由-1减至-2而失去平衡。故需要进行一次逆时针旋转操作。即将A的右孩子向左上旋转代替A作为根结点，A向左下旋转称为C的左子树的根结点。而原来C的左子树则变成A的右子树。

③LR型平衡旋转法
由于在A的左孩子B的右子树上插入节点F，使A的平衡因子由1增至2而失去平衡。故需要进行两次旋转操作（先逆时针，后顺时针）。即先将A节点的左孩子B的右子树的根结点D向左上旋转提升到B节点的位置，然后再把该结点向右上旋转提升到A节点的位置。即先使之称为LL型，再按LL型处理。

如图中所示，先将圆圈部分调整为哦ing横竖，然后将其以根结点接到A的左子树上，此时称为LL型，再按照LL型处理成平衡型。

④RL型平衡旋转法
由于在A的右孩子C的左子树上插入节点F，使A的平衡因子由-1减至-2而失去平衡，故需进行两次旋转操作（先顺时针，再逆时针），即先将A节点的右孩子C的左子树的根结点D向右上旋转到C的位置，然后再把该D节点向左上旋转到A的位置。即使之先成为RR型，再按照RR型处理。

如图所示，先将圆圈部分调整为平衡树，然后将其以根结点接到A的左子树上，此时成为RR型，再按照RR型处理为平衡型。

平衡化靠的是旋转。参与旋转的是3个节点（其中一个可能是外部节点NULL），旋转就是把这3个节点转个位置。注意的是，左旋的时候p->right一定不为空，右旋时p->left一定不为空。

如果从空树开始建立，并时刻保持平衡，那么不平衡只会发生在插入删除操作上，而不平衡的标志就是出现bf2或者bf-2的情况。

删除节点的调整方法

在平衡二叉树上删除节点x（假定有且仅有一个节点等于x）的过程如下：
①采用二叉排序树 的删除方法找到节点x并且删除它。
②沿着根到被删除节点的路线之逆逐层向上查找，必要时修改x祖先节点的平衡因子，因为删除后会使得某些子树的高度降低‘
③查找过程中，一旦发现某个x的祖先* p失衡，就要进行调整。不妨设x节点在* p的左子树中，在* p节点失衡后，要做何种调整，取决于* p节点的右孩子，* p1，若* p1的平衡因子是1，则做RL调整；若 * p1的平衡因子是-1，则做RR调整；若* p1的平衡因子是0，则做RL或者RR调整都可以。如果x在* p的右子树中，调整过程类似。
④如果调整后，子树的高度降低了，这个过程还要继续，知道根结点为止。即，删除一个节点可能会引起多次调整，而不是插入时的至多一次调整。

节点查找

和二叉排序树完全相同。

#include 
typedef struct AVLNode *Position;
typedef Position AvLNodea; // AVL树类型
typedef int ElementType;
typedef AVLNodea AVLTree;
struct AVLNode
{
	ElementType Data; //节点数据
	AVLTree Left;	  //指向左子树
	AVLTree Right;	  //指向右子树
	int Height;		  //树高
};

int Max(int a, int b)
{
	return a > b ? a : b;
}
int GetHeight(AVLTree BT)
{
	int HL, HR, MaxH;
	if (BT)
	{
		HL = GetHeight(BT->Left);  //递归求左子树的高度
		HR = GethEIGHT(BT->Right); //递归求右子树的高度
		MaxH = HL > HR ? HL : HR;  //取左右子树中较大的高度
		return (MaxH + 1);		   //返回树的高度
	}
	else
		return 0;
}
AVLTree SingleLeftRotation(AVLTree A)
{
	//注意：A必须有一个左孩子结点B
	//将A与B做左单旋，更新A与B的高度；返回新的根结点B
	AVLTree B = A->Left;
	A->Left = B->Right;
	A->Right = A;
	A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
	B->Height = Max(GetHeight(B->Left), GetHeight(B->Right)) + 1;

	return B;
} //程序完成了左单旋
AVLTree SingleRightRotation(AVLTree A)
{
	//注意：A必须有一个右孩子结点B
	//将A和B做右单旋，更新A与B的高度，返回新的根结点B；
	AVLTree B = A->Right;
	A->Right = B->Left;
	A->Left = A;
	A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
B->Height=Max(GetHeight(B->Left),GetHeight(B->Right)+1;

return B;
}
//完成了右单旋
AVLTree DoubleLeftRightRotation(AVLTree A)
{
	//注意：A必须有一个左子节点B，且B必须有一个右子节点C
	//将A、B与C做两次单旋，返回新的节点C

	//将B与C做右单旋，C被返回
	A->Left = SingleRightRotation(A->Left);
	//将A与C做左单旋，C被返回
	return SingleLeftRotation(A)；
}
AVLTree DoubleRightLeftRotation(AVLTree A)
{
	//注意：A必须有一个右子节点B，且B必须有一个左子节点C
	//将A、B、C做两次单旋，返回新的根结点C

	// B与C做右单旋，C被返回
	A->Right = SingleRightRotation(AVLTree A->Right);
	//将A与C做右单旋，C被返回
	return SingleLeftRotation(AVLTree A);
}
AVLTree Insert(AVLTree T, ElementType X)
{
	//将X插入AVL树T中，并且返回调整后的AVL树
	if (!T)
	{
		//若插入空树，则新建包含一个结点的树
		T=(AVLTree)malloc(sizeof(struct AVLNode));
		T->Data=X;
		T->Height=0;
		T->Left=T->Right=NULL;
	}
	else if(X<T->Data){
		//插入T的左子树
		T->Left=Insert(T->Left,X);
		//如果需要左旋
		if(GetHeight(T->Left)-GetHeight(T->Right)==2){
			if(X<T->Left->Data) T=SingleRightRotation(T);
			else T=SingleLeftRotation(T);
		}
		//别忘更新树高
		T->Height=Max(GetHeight(T->Left),GetHeight(T->Right))+1;
		return T;
	}
	void InorderTraversal(AVLTree A)
	{
		if(BT){
			InorderTraversal(BT->Left);
			cout<<BT->Data<<" ";
			InorderTraversal(BT->Right);
		}
	}
	int main()
	{
		int N;
		cin>>N;
		AVLTree avl=NULL;
		for(int i=0;i<N;i++){
			int t;
			cin>>t;
			avl=AVL_Insertion(t,avl);
		}
		cout<<avl->Data;
		return 0;

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121