[数据结构与算法]平衡二叉树 AVL树 实现 C语言

定义： 为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的左右子树的高度差的绝对值不超过1.将这样的二叉树称为平衡二叉树，简称平衡树。
平衡因子： 结点左子树和右子树的高度差，平衡树平衡因子取值只可能是-1、0、1。
1、LL平衡旋转（右单旋转）
在结点A的左孩子（L）的左子树（L）上插入新节点。

/* LL单旋  */
static Position SingleRotateWithRight(Position A)
{
    Position B;

    B = A->Left;
    A->Left= B->Right;
    B->Left = A;

    A->Height = Max(Height(A->Left), Height(A->Right)) + 1;
    B->Height = Max(Height(B->Left),A->Height) + 1;

    return B; /*New root */
}

2、RR平衡旋转（左单旋转）
在结点A的右孩子（R）的右子树（R）上插入新节点。

/* 向左单旋 */
static Position SingleRotateWithLeft(Position A)
{
    Position B;

    B= A->Right;
    A->Right= B->Left;
    B->Left= A;

    A->Height = Max(Height(A->Left), Height(A->Right)) + 1;
    B->Height = Max(A->Height,Height(B->Right)) + 1;

    return B; /* New Root */
}

3、LR平衡旋转（先左后右双旋转）
在结点A的左孩子（L）的右子树（R）上插入新节点。

/* 先左后右双旋 */
static Position DoubleRotateWithLeft(Position A)
{
    /* Rotate between K1 and K2 */
    A->Left = SingleRotateWithRight(A->Left);

    /* Rotate between K3 and K2 */
    return SingleRotateWithLeft(A);
}

2、RL平衡旋转（先右后左双旋转）
在结点A的右孩子（R）的左子树（L）上插入新节点。

/* 先右后左双旋 */
static Position DoubleRotateWithRight(Position A)
{
    A->Right = SingleRotateWithLeft(A->Right);

    return SingleRotateWithRight(A);
}

例子：
插入 15、3、7、10、9、8，生成平衡树。

代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
typedef int ElementType;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

struct AvlNode
{
    ElementType Element;
    AvlTree Left;
    AvlTree Right;
    int Height;
};

AvlTree MakeEmpty(AvlTree T)
{
    if (T != NULL)
    {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

/**
 * 计算Avl节点高度
 * @param  P 节点P
 * @return 树高
 */
static int Height(Position P)
{
    if (P == NULL)
        return -1;
    else
        return P->Height;
}

static int Max(int a, int b)
{
    return a > b ? a : b;
}

/* LL单旋 */
static Position SingleRotateWithLeft(Position K2)
{
    Position K1;

    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;

    K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
    K1->Height = Max(Height(K1->Left), K2->Height) + 1;

    return K1; /* New Root */
}

/* RR单旋  */
static Position SingleRotateWithRight(Position K2)
{
    Position K1;

    K1 = K2->Right;
    K2->Right = K1->Left;
    K1->Left = K2;

    K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
    K1->Height = Max(K2->Height, Height(K1->Right)) + 1;

    return K1; /*New root */
}

/* LR双旋 */
static Position DoubleRotateWithLeft(Position K3)
{
    /* Rotate between K1 and K2 */
    K3->Left = SingleRotateWithRight(K3->Left);

    /* Rotate between K3 and K2 */
    return SingleRotateWithLeft(K3);
}

/* RL双旋 */
static Position DoubleRotateWithRight(Position K3)
{
    K3->Right = SingleRotateWithLeft(K3->Right);

    return SingleRotateWithRight(K3);
}

AvlTree Insert(ElementType X, AvlTree T)
{
    if (T == NULL)
    {
        T = (AvlNode*)malloc( sizeof( struct AvlNode ) );
        if (T == NULL)
            printf("Out of space!!!\n");
        else
        {
            T->Element = X;
            T->Height = 0;
            T->Left = T->Right = NULL;
        }
    }
    else if (X < T->Element) /* 左子树插入新节点 */
    {
        T->Left = Insert(X, T->Left);
        if (Height(T->Left) - Height(T->Right) == 2)
            if (X < T->Left->Element)
                T = SingleRotateWithLeft(T);
            else
                T = DoubleRotateWithLeft(T);
    }
    else if (X > T->Element) /* 右子树插入新节点 */
    {
        T->Right = Insert(X, T->Right);
        if (Height(T->Right) - Height(T->Left) == 2)
            if (X > T->Right->Element)
                T = SingleRotateWithRight(T);
            else
                T = DoubleRotateWithRight(T);
    }
    /* Else X is in the tree alredy; we'll do nothing */
    T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
    return T;
}
/* search the min element in AvlTree*/
Position FindMin(AvlTree T)
{
    if (T == NULL)
        return NULL;
    else if (T->Left == NULL)
        return T;
    else
        return FindMin(T->Left);
}

/* search the max element in AvlTree */
Position FindMax(AvlTree T)
{
    if (T == NULL)
        return NULL;
    else if (T->Right == NULL)
        return T;
    else
        return FindMax(T->Right);
}
AvlTree Delete(ElementType X, AvlTree T)
{
    Position TmpCell;
     if(T == NULL) {
        printf("没找到该元素，无法删除！\n");
        return NULL;
     }
     else if (X < T->Element)
         T->Left = Delete(X, T->Left);
     else if (X > T->Element)
         T->Right = Delete(X, T->Right);
     else if(T->Left && T->Right) { //要删除的树左右都有儿子
         TmpCell = FindMin(T->Right);   //用该结点右儿子上最小结点替换该结点，然后与只有一个儿子的操作方法相同
         T->Element = TmpCell->Element;
         T->Right = Delete(T->Element, T->Right);
     }else{
         TmpCell = T;        //要删除的结点只有一个儿子
         if(T->Left == NULL)
             T = T->Right;
         else if(T->Right == NULL)
             T = T->Left;
         free(TmpCell);
     }
     return T;
}

/* 查找X元素所在的位置 */
Position Find(ElementType X, AvlTree T)
{
    if (T == NULL)
        return NULL;
    if (X < T->Element)
        return Find(X, T->Left);
    else if (X > T->Element)
        return Find(X, T->Right);
    else
        return T;
}


ElementType Retrieve(Position P)
{
    if(P != NULL)
        return P->Element;
    return -1;
}

/**
 * 前序遍历"二叉树"
 * @param T Tree
 */
void PreorderTravel(AvlTree T)
{
    if (T != NULL)
    {
        printf("%d", T->Element);
        PreorderTravel(T->Left);
        PreorderTravel(T->Right);
    }
}

/**
 * 中序遍历"二叉树"
 * @param T Tree
 */
void InorderTravel(AvlTree T)
{
    if (T != NULL)
    {
        InorderTravel(T->Left);
        printf("%d", T->Element);
        InorderTravel(T->Right);
    }
}

/**
 * 后序遍历二叉树
 * @param T Tree
 */
void PostorderTravel(AvlTree T)
{
    if (T != NULL)
    {
        PostorderTravel(T->Left);
        PostorderTravel(T->Right);
        printf("%d", T->Element);
    }
}

/* 打印二叉树信息 */
void PrintTree(AvlTree T, ElementType Element, int direction)
{
    if (T != NULL)
    {
        if (direction == 0)
            printf("%2d is root\n", T->Element);
        else
            printf("%2d is %2d's %6s child\n", T->Element, Element, direction == 1 ? "right" : "left");

        PrintTree(T->Left, T->Element, -1);
        PrintTree(T->Right, T->Element, 1);
    }
}
int main(int argc, char const *argv[])
{

    AvlTree T;
    Position P;
    int i;

    T = MakeEmpty(NULL);

    T = Insert(15, T);
    T = Insert(3, T);
    T = Insert(7, T);
    T = Insert(10, T);
    T = Insert(9, T);
    T = Insert(8, T);
    
    printf("Root: %d\n", T->Element);

    printf("树的详细信息: ");
    PrintTree(T, T->Element, 0);
    printf("\n");

    printf("前序遍历二叉树: ");
    PreorderTravel(T);
    printf("\n");

    printf("中序遍历二叉树: ");
    InorderTravel(T);
    printf("\n");

    printf("后序遍历二叉树: ");
    PostorderTravel(T);
    printf("\n");

    printf("最大值: %d\n", FindMax(T)->Element);
    printf("最小值: %d\n", FindMin(T)->Element);

    Delete(7, T);
    printf("树的详细信息: \n");
    PrintTree(T, T->Element, 0);

    return 0;
}

结果：

非递归实现插入：

//对Avl树进行插入操作，非递归版本
Avltree Insert_not_recursion (int x, Avltree T)
{
	stack<Avltree> route; //定义一个堆栈使用

	//找到元素x应该大概插入的位置，但是还没进行插入
	Avltree root = T;
	while(1)
	{
	   if(T == NULL)  //如果T为空树，就创建一棵树，并返回
         {
	      T = static_cast<Avltree>(malloc(sizeof(struct AvlNode)));
		  if (T == NULL) cout << "out of space!!!" << endl;  
		  else                    
		    {
				T->Element = x;
				T->Left = NULL;
				T->Right = NULL;
				T->Hight = 0;
				T->Isdelete = 0;
				route.push (T);
				break;
		    }
		  }
	   else if (x < T->Element)
	   {
	      route.push (T);
		  T = T->Left;
		  continue;
	   }
	   else if (x > T->Element)
	   {
	      route.push (T);
		  T = T->Right;
		  continue;
	   }
	   else
	   {
	      T->Isdelete = 0;
		  return root;
	   }
	}

	//接下来进行插入和旋转操作
	Avltree father,son;
	while(1)
	{
	   son = route.top ();   
	   route.pop();   //弹出一个元素
	   if(route.empty())
		   return son;   
	   father = route.top ();  
	    route.pop();   //弹出一个元素
		if(father->Element < son->Element )   //儿子在右边
		{
		   father->Right = son;
		   if( Height(father->Right) - Height(father->Left) == 2)
		   {
			   if(x >  Element(father->Right))
				   father = SingleRotateWithRight(father);
			   else
				   father = DoubleRotateWithRight(father);
		   }
		  
		   route.push(father);
		}
		else if (father->Element > son->Element)    //儿子在左边
		{
			father->Left = son;
			if(Height(father->Left) - Height(father->Right) == 2)
			{
				if(x < Element(father->Left))
				   father = SingleRotateWithLeft(father);
			   else
				   father = DoubleRotateWithLeft(father);
			}
		
			route.push(father);
                
		}
		father->Hight = max(Height(father->Left),Height(father->Right )) + 1;
	}
	
	

}