查找算法--树表查找之平衡二叉树

 

        前一篇博客学习了高效动态表查找的二叉排序树，虽然在二叉排序树上实现的插入，删除和查找等基本操作的平均时间为O(log2(n)),但随着插入和删除操作导致树形的改变，成为单枝树，只能从根开始一层一个查找，实质变为顺序查找，此时就是最坏的情况，基本运算的时间会增至O(n);为了避免这种情况，我们可以使用平衡二叉树，使之即保存BST性质又保证树的高度至多左右子树相差一。平衡二叉树有较多种，我们主要介绍较为著名的AVL树。

   

平衡二叉树(AVL)

 

1.概念介绍

        平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

        我们通过平衡因子来具体实现上述的平衡二叉树的定义，平衡因子的定义为：平衡二叉树中每一个结点有一个平衡因子域，每个结点的平衡因子是该结点左子树的高度减去右子树的高度。若一棵二叉树中所有结点的平衡因子的绝对值小于或等于1，则该树成为平衡二叉树。

       例如：

    

 每个结点旁边标记的就是该结点的平衡因子，具体计算如下：

我们看图a，左子树高度减去右子树高度，得

5的结点平衡因子就是 3 - 2 = 1；

2的结点平衡因子就是 1 - 2 = -1；

4的结点平衡因子就是 1 - 0 = 1；

6的结点平衡因子就是 0 - 1 = -1；

 

2.结点插入

首先我们定义树结点的结构为：

//树结点结构
struct node
{
	int data;//数据
	int bf;//平衡因子
	node*lchild,*rchild;
	node()
	{
		lchild=rchild=NULL;
	}
};

 

  在平衡二叉树中插入结点与二叉查找树最大的不同在于要随时保证插入后整棵二叉树是平衡的。若插入的新结点破坏了平衡性首先要从根节点到该新结点的路径逆向找到第一个失去平衡的结点。在这里我们要介绍失去平衡的最小子树的概念。

失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。 

   (1)LL型调整

        由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。 即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。

如图所示：

   

 代码实现：

 

void L_rotata(node * &p){//左旋，
	node * rc=p->rchild;
	p->rchild=rc->lchild;
	rc->lchild=p;
	p=rc;

}

 

 

   (2)RR型调整

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

   如图所示：

 实现代码：

 

void R_rotate(node * &p){//右旋，
	node * lc=p->lchild;
	p->lchild=lc->rchild;
	lc->rchild=p;
	p=lc;
}

 

 

  (3)LR型调整

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

如图所示：

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

 

实现代码：

 

void Leftbalance(node * &T){//左子树的平衡处理
	node * lc=T->lchild;
	switch(lc->bf){
	//LL的情况
	case LH:
		T->bf=lc->bf=EH;
		R_rotate(T);
		break;

	case RH://LR的情况，同时针对rd上的不同情况，进行对T，lc的平衡因子的设置
		node * rd=lc->rchild;
		switch(rd->bf){
			case LH:T->bf=RH; lc->bf=EH;break;
			case EH:T->bf=lc->bf=EH;break;
			case RH:T->bf=EH;lc->bf=LH;break;
		}
		rd->bf=EH;
		L_rotata(T->lchild);
		R_rotate(T);
	}


}

 

 

(4)RL型调整

 

 

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

如图所示：

 

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

实现代码：

void Rightbalance(node * &T)//右子树的平衡处理，与左子树的平衡处理类似
{
	node * rc=T->rchild;
	switch (rc->bf)
	{
		case RH:
			T->bf=rc->bf=EH;
			L_rotata(T);break;
		case LH:
		   node * ld=rc->lchild;
			switch(ld->bf){
		case LH:
			T->bf=EH; rc->bf=RH;break;
		case EH:
			T->bf=rc->bf=EH;break;
		case RH:
			T->bf=LH; rc->bf=EH;break;

			}
			ld->bf=EH;
			R_rotate(T->rchild);
			L_rotata(T);
	}

}

 含有n个结点的平衡二叉树的平均查找长度为O(log2(n));

 

 附上源码地址：https://github.com/longpo/algorithm/tree/master/AVL