数据结构——AVL树(C语言)

AVL(Adelson-Velskii 和 Landis)树是带有平衡条件的二叉查找树。在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(lngn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

节点的平衡因子是它的左子树的高度减去它的右子树的高度(有时相反)。带有平衡因子1、0或-1的结点被认为是平衡的。带有平衡因子-2或2的节点被认为是不平衡的,并需要重新平衡这个树。平衡因子可以直接存储在每个节点中,或从可能存储在节点中的子树高度计算出来。

AVL树的基本操作一般涉及运作同在不平衡的二叉查找树所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL旋转"。

以下图标表示的四种情况,就是AVL旋转中常见的四种。(图片用了维基百科的,不确定不开vpn图是否会挂)。

下面来看AVL树的操作有哪些:

#ifndef _AvlTree_H

struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
typedef int ElementType;

AvlTree MakeEmpty( AvlTree T );
Position Find( ElementType X, AvlTree T );
Position FindMin( AvlTree T );
Position FindMax( AvlTree T );
AvlTree Insert( ElementType X, AvlTree T );
AvlTree Delete( ElementType X, AvlTree T );
ElementType Retrieve( Position P );

#endif /* _AvlTree_H */

下面是对于上面操作定义的实现:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "AvlTree.h"

#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;
}

/* 向左单旋 */
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 */
}

/* 向右单旋  */
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 */
}

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

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

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

    return SingleRotateWithRight(K3);
}

AvlTree Insert(ElementType X, AvlTree T)
{
    if (T == NULL)
    {
        T = 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;
}

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;
}

/* 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);
}

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

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

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

/**
 * 后序遍历二叉树
 * @param T Tree
 */
void PostorderTravel(AvlTree T)
{
    if (T != NULL)
    {
        PostorderTravel(T->Left);
        PostorderTravel(T->Right);
        printf("%d\n", 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);
    }
}

在实现完成这些函数后,我们在main函数中对AVL树进行测试:

int main(int argc, char const *argv[])
{
    printf("Hello World\n");

    AvlTree T;
    Position P;
    int i;

    T = MakeEmpty(NULL);

    T = Insert(21, T);
    T = Insert(2150, T);
    T = Insert(50, T);
    T = Insert(12, T);
    T = Insert(1201, T);

    printf("Root: %d\n", T->Element);

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

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

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

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

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

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

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏与神兽党一起成长

学习Java Collection Framework的Iterator实现

继续研读JDK的源码,在比较HashMap和ConcurrentHashMap的不同之处发现了一个细节——关于Iterator的实现的不同,其实HashMap和...

9750
来自专栏恰童鞋骚年

数据结构基础温故-4.树与二叉树(中)

在上一篇中,我们了解了树的基本概念以及二叉树的基本特点和代码实现,还用递归的方式对二叉树的三种遍历算法进行了代码实现。但是,由于递归需要系统堆栈,所以空间消耗要...

14210
来自专栏编程之旅

数据结构——二叉查找树(C语言)

二叉查找树,也称作二叉搜索树,有序二叉树,排序二叉树,而当一棵空树或者具有下列性质的二叉树,就可以被定义为二叉查找树:

23440
来自专栏书山有路勤为径

二叉树转链表

给定一个二叉树,将该二叉树 就地(in-place)转换为单链表。单链表中节点顺序 为二叉树前序遍历顺序。(不额外开辟存储空间) LeetCode 114. ...

8520
来自专栏Android机器圈

数据结构与算法 -- 二叉树链式详解((非)/递归遍历,叶子个数,深度计算)

PS:树型结构是一种重要的非线性数据结构,教科书上一般都是树与二叉树,由此可见,树和二叉树是有区别和联系的,网上有人说二叉树是树的一种特殊形式,但经过查资料,树...

11450
来自专栏用户2442861的专栏

List、Set、Map、数组之间各种转换

刚学Java不久的时候,接到一个电面,然后问了一些java的知识,比如说Java的编码,Unicode等,但是最让我蛋疼的是怎么吗map转为set,那个时候对...

46020
来自专栏算法channel

图解用栈数据结构对树的遍历

本公众号主要推送关于如何构思算法使之应用到我们的工作中。计算机常用算法思想大致来说有,分而治之,动态规划,贪心算法,搜索算法,回溯 ,训练这些思维的一个很好的平...

381110
来自专栏郭耀华‘s Blog

《剑指offer》全部题目-含Java实现

陆续刷了好久,算是刷完了《剑指offer》,以下全部AC代码,不一定性能最优,如有错误或更好解答,请留言区指出,大家共同交流,谢谢~ 1.二维数组中的查找 在...

1.1K70
来自专栏gaoqin31

二叉查找树

高:ni的高是从ni到一片树叶的最长路径的长,因此,所有叶子的高为0,一颗树的高等于它的根的高

8720
来自专栏desperate633

Top 10 Methods for Java Arrays1 声明一个array2 打印一个array3 从array创建一个list4 检查array中是否存在某个元素5 连接两个array6 D

9310

扫码关注云+社区

领取腾讯云代金券