平衡二叉树，任意结点深度差满足|deepDiff|<2

左高右低不平衡

图一处于平衡

图二新增节点N

此时左深右浅。需要右旋转。

右旋转，根节点P需要降，L需要升，将L与P之间的元素即,LR放置到P节点。

右旋转,P降级,因为不平衡，就需需要此消彼长形成平衡，也就是leftdeep-1,rightdeep+1.

L上升，出现了问题LR的归处，LR存放着所有大于(平衡有序二叉树)L节点的数据，且下雨P的数据。而P因为失去了左子树L且左子树的右子树满足,L<LR<P,所以拿LR替代L称为P的新的左子树。

P下降，P下降造成左子树遗失，刚好用L节点的右子树形成局部平衡二叉树，以此维护整个树的平衡。

右高左低不平衡

与前面的相反的操作。

插入操作可能会因为符号不统一，称为双旋转。

如图所示,新增节点后，对于P，不平衡因子为2，对于L不平衡银子为-2,所以需要先统一符号

L左旋转,统一平衡符号

P右旋转,形成新的平衡。

右旋转封装成方法

	void R_Rotate(BiTree *P)
	{
		BiTree PL;   //用来存放PL
		PL = (*P)->lchild;   //赋值
		(*P)->lchild = PL->rchild;
		//PL降级，将PL与P之间的数据PL->rchild挂到P的左子树上，
		//因为P降级的时候失去了P->lchild(PL),而PL->rchild的所有数据PLRData满足PL<PLRData<P
		//因此使用PL->rchild作为P的左子树。
		PL->rchild = (*P);
		//P降级为PL的右节点
		*P = PL;
		//新的P节点由原PL代替。
	}

结合第一张图理解，讲解右旋转。

声明一个临时变量PL

存储P的左子树PL到变量变量PL

将P的左子树接为P的左子树

将PL的右子树变为原来的P。

新的P节点变成了原来的PL。

完结撒花。

左平衡(左边不平衡就会右旋转)

	void LeftBalance(BiTree *P)
	{
		//开始维护平衡
		BiTree PL, PLr;
		PL = (*P)->lchild;
		//定义PL
		switch (PL->bf)
		{
			case LH:
				//此时符号一致只需要进行简单右旋转就可以了。
				(*P)->bf = PL->bf = EH;
				R_Rotate(P);
				break;
			case RH:
				//插入在右边,也就造成了符号不一致的问题。
				//需要先对符号进行一致操作。
				PLr = PL->rchild;
				switch (PLr->bf)
				{
					case LH:
						(*P)->bf = RH;
						PL->bf = EH;
						break;
					case EH:
						(*P)->bf = PL->bf = EH;
						break;
					case RH:
						(*P)->bf = EH;
						PL->bf = LH;
						break;
				}
				PLr->bf = EH;
				L_Rotate(&(*P)->lchild);
				R_Rotate(P);
		}
	}

如果是LH,即符号一致，只需要简单右旋转。根据图一的执行结果可以看出P->bf和PL->bf打成了平衡。
LH
EH
RH

源码

#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"


#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 

typedef int Status; 


typedef  struct BiTNode
{
    int data;   //数据
    int bf;     //平衡标志
    struct BiTNode *lchild, *rchild;//左右子树
} BiTNode, *BiTree;

void R_Rotate(BiTree *P)
{
    BiTree PL;   //用来存放PL
    PL = (*P)->lchild;   //赋值
    (*P)->lchild = PL->rchild;
    //PL降级，将PL与P之间的数据PL->rchild挂到P的左子树上，
    //因为P降级的时候失去了P->lchild(PL),而PL->rchild的所有数据PLRData满足PL<PLRData<P
    //因此使用PL->rchild作为P的左子树。
    PL->rchild = (*P);
    //P降级为PL的右节点
    *P = PL;
    //新的P节点由原PL代替。
}

void L_Rotate(BiTree *P)
{
     BiTree PR;
     PR = (*P)->rchild;
     (*P)->rchild = PR->lchild;
     PR->lchild = (*P);
     *P = PR;
}

#define LH + 1
#define EH 0
#define RH - 1

void LeftBalance(BiTree *P)
{
    //开始维护平衡
    BiTree PL, PLr;
    PL = (*P)->lchild;
    //定义PL
    switch (PL->bf)
    {
        case LH:
            //此时符号一致只需要进行简单右旋转就可以了。
            (*P)->bf = PL->bf = EH;
            R_Rotate(P);
            break;
        case RH:
            //插入在右边,也就造成了符号不一致的问题。
            //需要先对符号进行一致操作。
            PLr = PL->rchild;
            switch (PLr->bf)
            {
                case LH:
                    (*P)->bf = RH;
                    PL->bf = EH;
                    break;
                case EH:
                    (*P)->bf = PL->bf = EH;
                    break;
                case RH:
                    (*P)->bf = EH;
                    PL->bf = LH;
                    break;
            }
            PLr->bf = EH;
            L_Rotate(&(*P)->lchild);
            R_Rotate(P);
    }
}

void RightBalance(BiTree *P)
{
    BiTree PR, Rl;
    PR = (*P)->rchild;
    switch (PR->bf)
    {
        case RH:
            (*P)->bf = PR->bf = EH;
            L_Rotate(P);
            break;
        case LH:
            Rl = PR->lchild;
            switch (Rl->bf)
            {
                case RH: (*P)->bf = LH;
                    PR->bf = EH;
                    break;
                case EH: (*P)->bf = PR->bf = EH;
                    break;
                case LH: (*P)->bf = EH;
                    PR->bf = RH;
                    break;
            }
            Rl->bf = EH;
            R_Rotate(&(*P)->rchild);
            L_Rotate(P);
    }
}

// P        根节点
// e        是数据
// tasller  用来做变高回溯,方便判断是否需要旋转。

Status InsertAVL(BiTree *P, int e, Status *taller)
{
    if (!*P)
    {
        *P = (BiTree)malloc(sizeof(BiTNode));
        (*P)->data = e;
        (*P)->lchild = (*P)->rchild = NULL;
        (*P)->bf = EH;
        *taller = TRUE;
        //新增几点处于平衡，新增节点同时也可能造成了失衡。
    }
    else
    {
        if (e == (*P)->data)
        {
            *taller = FALSE;
            return FALSE;
        }
        if (e < (*P)->data)
        {
            if (!InsertAVL(&(*P)->lchild, e, taller))
            {//没变高说明找到重复数据
                return FALSE;
            }
            if (*taller)
            {//变高了说明插入到左节点成功，但是可能形成不平衡
                switch ((*P)->bf)
                {
                    case LH:
                        //原本就是左边高，此时左边更高,需要维护平衡。
                        LeftBalance(P);
                        *taller = FALSE;
                        break;
                    case EH:
                        (*P)->bf = LH;
                        *taller = TRUE;
                        break;
                    case RH:
                        (*P)->bf = EH; 
                        *taller = FALSE; 
                        break;
                }
            }
        }
        else
        {
            if (!InsertAVL(&(*P)->rchild, e, taller))
            {
                return FALSE;
            }
            if (*taller)
            {
                switch ((*P)->bf)
                {
                    case LH:
                        (*P)->bf = EH;
                        *taller = FALSE;
                        break;
                    case EH:
                        (*P)->bf = RH;
                        *taller = TRUE;
                        break;
                    case RH:
                        RightBalance(P);
                        *taller = FALSE;
                        break;
                }
            }
        }
    }
    return TRUE;
}
int main(void)
{
    int i;
    int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
    BiTree P = NULL;
    Status taller;
    for (i = 0; i < 10; i++)
    {
        InsertAVL(&P, a[i], &taller);
    }
    return 0;
}

平衡二叉树

源码

在线实例

实例推荐

最新更新

技术问答