数据结构 平衡二叉树介绍及实现_数据结构二叉平衡树的实现

概念：平衡树，又称AVL树，她也是一棵二叉查找树。
目的：为了将查找的时间复杂度保证在O(logN)范围内。
在AVL树中，每次插入或者删除某些数据之后，有时候需要对二叉树的高度做一些调整，就是为了保证平衡。这个平衡的要求是左右子树的高度差小于等于一，也就是内部的所有节点的左右子树的高度查都要小于等于一。
如图：

这个就符合平衡二叉树的要求；
再看下一个例子：

这个就不符合平衡二叉树的要求，因为A的左右子树高度差大于一，C的左右子树高度差也大于一，需要有所调整，才能符合要求。

---

那么如何调整呢？
头定义：

typedef struct AVLNode *Position;
typedef Position AVLTree; ///AVL树类型 
struct AVLNode{
    ElementType Data; //结点数据 
    AVLTree Left;     //指向左子树
    AVLTree Right;    //指向右子树
    int Height;       //树高
};
int Max ( int a, int b )
{
    return a > b ? a : b;
}
1
2
3
4
5
6
7
8
9
10
11
12

我们要本着高度差小于等一的目的去调整，一共有四种方法：
调整二叉树首先要明白最小不平衡子树，是指最接近平衡因子绝对值大于1的节点做根的子树。要找到哪一个节点是不平衡的，然后又是哪一个节点导致不平衡的发生，就是找这两个节点。如上图中，我们发现A是不平衡点，而 F 是导致不平衡的那个节点，那么做出调整后的效果是：

第一种调整规则：RR型（右右型）
不平衡点 F 在 被破坏平衡的 A 的右子树的右子树中，所以是RR型，我们只需要将左边补一个节点就好了，那么常见的操作是直接将 C 作为根节点，A 补在左子树，因为 A 小于 C ，所以就完成了。如上图

 AVLTree SingleRightRotation ( AVLTree A )//将A与B做右单旋，更新A与B的高度，返回新的根结点B 
{
	 AVLTree B = A->Right;
	 A->Right =  B->Left;
	 B->Left = A;
	 A->Height = Max(GetHeight(A->Left),GetHeight(A->Right))+1;
	 B->Height = Max(GetHeight(B->Right),A->Height) + 1; 
	 return B;
	}
1
2
3
4
5
6
7
8
9

---

第二种调整规则：LL型（左左型）

不平衡点 C 在 被破坏平衡的 A 的左子树的左子树中，所以是LL型，我们只需要将右边补一个节点就好了，那么常见的操作是直接将 B 作为根节点，A 补在右子树，因为 A 大于 B ，符合查找树的要求，所以就完成了。如下图

 AVLTree SingleLeftRotation ( AVLTree A ) //注意：A必须有一个左子结点B
{
	   AVLTree B = A->Left;  // 将 A 与 B 做左单旋，更新A与B的高度，返回新的根结点B    
	   A->Left = B->Right;
	   B->Right = A;
	   A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
	   B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
	   return B;
}
1
2
3
4
5
6
7
8
9

---

第三种调整规则：LR型（左右型）

不平衡点 C 在 被破坏平衡的 A 的左子树的右子树中，所以是LR型，我们需要 C 作为根节点，A 补在右子树，因为 A 大于 C ，符合查找树的要求，所以就完成了。如下图

AVLTree DoubleLeftRightRotation ( AVLTree A )//LR型 ,A必须有一个左子结点B，且B必须有一个右子结点C 
{
		A->Left = SingleRightRotation(A->Left);  // 将B与C做右单旋，C被返回 
		return SingleLeftRotation(A);// 将A与C做左单旋，C被返回 
}
1
2
3
4
5

---

第四种调整规则：RL型（右左型）

不平衡点 C 在 被破坏平衡的 A 的右子树的左子树中，所以是RL型，我们需要 C 作为根节点，A 补在左子树，因为 A 小于 C ，符合查找树的要求，所以就完成了。如下图

  AVLTree DoubleLeftRightRotation ( AVLTree A )//RL型 
{
		 A->Right = SingleRightRotation(A->Right);
		 return SingleRightRotation(A);
}
1
2
3
4
5

---

插入函数：

  AVLTree Insert( AVLTree T, ElementType X )
{ 
		if ( !T )//若插入空树，则新建包含一个结点的树
		 { 
		        T = (AVLTree)malloc(sizeof(struct AVLNode));
		        T->Data = X;
		        T->Height = 0;
		        T->Left = NULL;
		 	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 = SingleLeftRotation(T); // 左单旋
			      else 
			         T = DoubleLeftRightRotation(T); // 左-右双旋
		}
	        else if ( X > T->Data )  //插入T的右子树 
		{
		        T->Right = Insert( T->Right, X );
	                if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 )
	               	     if ( X > T->Right->Data ) 
	                            T = SingleRightRotation(T);     // 右单旋
	                else 
	                     T = DoubleRightLeftRotation(T); //右-左双旋
	 	}
	  	T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1;
   	  return T;
}
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

求高度函数：

int GetHeight( AVLTree T )
{
	int Hl,Hr,Maxh;
	if( T )
	{
		Hl = GetHeight(  T->Left );
		Hr = GetHeight(  T->Right );
		Maxh = Hl > Hr ? Hl : Hr;
		retrun Maxh + 1;
	}
	else return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12