我要飞=_= 2022-03-26 10:27 采纳率: 70.6%
浏览 41
已结题

C语言平衡二叉树的插入代码理解

这是在MOOC上学数据结构遇到的问题,具体课程是浙江大学由何钦铭教授和陈越教授录制的数据结构

MOOC给的插入代码是
typedef struct AVLNode *Position;
typedef Position AVLTree; /* AVL树类型 */
struct AVLNode{
    ElementType Data; /* 结点数据 */
    AVLTree Left;     /* 指向左子树 */
    AVLTree Right;    /* 指向右子树 */
    int Height;       /* 树高 */
};

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

AVLTree SingleLeftRotation ( AVLTree A )
{ /* 注意:A必须有一个左子结点B */
  /* 将A与B做左单旋,更新A与B的高度,返回新的根结点B */     

    AVLTree B = A->Left;
    A->Left = B->Right;
    B->Right = A;
    A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
    B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
 
    return B;
}

AVLTree DoubleLeftRightRotation ( AVLTree A )
{ /* 注意:A必须有一个左子结点B,且B必须有一个右子结点C */
  /* 将A、B与C做两次单旋,返回新的根结点C */
    
    /* 将B与C做右单旋,C被返回 */
    A->Left = SingleRightRotation(A->Left);
    /* 将A与C做左单旋,C被返回 */
    return SingleLeftRotation(A);
}

/*************************************/
/* 对称的右单旋与右-左双旋请自己实现 */
/*************************************/

AVLTree Insert( AVLTree T, ElementType X )
{ /* 将X插入AVL树T中,并且返回调整后的AVL树 */
    if ( !T ) { /* 若插入空树,则新建包含一个结点的树 */
        T = (AVLTree)malloc(sizeof(struct AVLNode));
        T->Data = X;
        T->Height = 0;
        T->Left = T->Right = NULL;
    } /* if (插入空树) 结束 */

    else if ( X < T->Data ) {
        /* 插入T的左子树 */
        T->Left = Insert( T->Left, X);
        /* 如果需要左旋 */
        if ( GetHeight(T->Left)-GetHeight(T->Right) == 2 )
            if ( X < T->Left->Data ) 
               T = SingleLeftRotation(T);      /* 左单旋 */
            else 
               T = DoubleLeftRightRotation(T); /* 左-右双旋 */
    } /* else if (插入左子树) 结束 */
    
    else if ( X > T->Data ) {
        /* 插入T的右子树 */
        T->Right = Insert( T->Right, X );
        /* 如果需要右旋 */
        if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 )
            if ( X > T->Right->Data ) 
               T = SingleRightRotation(T);     /* 右单旋 */
            else 
               T = DoubleRightLeftRotation(T); /* 右-左双旋 */
    } /* else if (插入右子树) 结束 */

    /* else X == T->Data,无须插入 */

    /* 别忘了更新树高 */
    T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1;
    
    return T;
}

我的问题出在AVLTree Insert()里面,是当X值已经被插入后,如果需要调整,该选择哪一种方法调整,MOOC的代码我能看懂,但是不理解。

举个例子,如图

img


假设这边Feb是比Dec小的,插在了它的左边后,那么似乎就不能做左右双旋了吧?好像得用右左双旋了

-分隔符

写提问的时候突然看懂了,不过还是发出来吧。这是递归,返回到Aug的时候比较Feb和Aug大小,因为X比T->Data大,所以是插入右子树,做的右左双旋。
现在想问问各位专家,这个代码是怎样想出来的,虽然现在看懂了,但要理解,要自己写出来那还差远了;以及我该怎样做以后才有机会自己快速写出这样子的代码?我想不通这是怎么想到的,给我我想一天可能都写不出来。

  • 写回答

2条回答 默认 最新

  • 有问必答小助手 2022-03-28 18:03
    关注

    你好,我是有问必答小助手,非常抱歉,本次您提出的有问必答问题,技术专家团超时未为您做出解答


    本次提问扣除的有问必答次数,已经为您补发到账户,我们后续会持续优化,扩大我们的服务范围,为您带来更好地服务。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 4月7日
  • 已采纳回答 3月30日
  • 创建了问题 3月26日

悬赏问题

  • ¥50 易语言把MYSQL数据库中的数据添加至组合框
  • ¥20 求数据集和代码#有偿答复
  • ¥15 关于下拉菜单选项关联的问题
  • ¥20 java-OJ-健康体检
  • ¥15 rs485的上拉下拉,不会对a-b<-200mv有影响吗,就是接受时,对判断逻辑0有影响吗
  • ¥15 使用phpstudy在云服务器上搭建个人网站
  • ¥15 应该如何判断含间隙的曲柄摇杆机构,轴与轴承是否发生了碰撞?
  • ¥15 vue3+express部署到nginx
  • ¥20 搭建pt1000三线制高精度测温电路
  • ¥15 使用Jdk8自带的算法,和Jdk11自带的加密结果会一样吗,不一样的话有什么解决方案,Jdk不能升级的情况