平衡二叉树

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

  • 左高右低不平衡

    • 图一处于平衡

    • 图二新增节点N

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

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

      1. 右旋转,P降级,因为不平衡,就需需要此消彼长形成平衡,也就是leftdeep-1,rightdeep+1.
      2. L上升,出现了问题LR的归处,LR存放着所有大于(平衡有序二叉树)L节点的数据,且下雨P的数据。而P因为失去了左子树L且左子树的右子树满足,L<LR<P,所以拿LR替代L称为P的新的左子树。
      3. P下降,P下降造成左子树遗失,刚好用L节点的右子树形成局部平衡二叉树,以此维护整个树的平衡。
    • 右高左低不平衡

      与前面的相反的操作。

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

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

        1. L左旋转,统一平衡符号
        1. P右旋转,形成新的平衡。
  1. 右旋转封装成方法
    	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。
    • 完结撒花。
  2. 左平衡(左边不平衡就会右旋转)
    	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;
}