洛洛大芳 2021-07-03 09:57 采纳率: 81%
浏览 63
已采纳

平衡二叉树插入和删除之后判断是否平衡的问题

在插入一个节点后,从哪个节点开始判断是否平衡,删除一个节点后,在那个节点判断是否平衡?望有人回答,一定采纳,有代码演示就更好啦哈哈哈

  • 写回答

1条回答 默认 最新

  • 暗夜无风 2021-07-03 12:36
    关注

    平衡二叉树插入采用递归的方式,在某个结点插入后,递归返回,在返回的过程中不断地判断是否平衡。即在插入位置的根结点开始判断是否平衡,并不断回溯。
    部分代码如下:

    AVLNode* AVL_Insert(AVLNode* root, int val)
    {
        if (!root)//root是空树,直接创建
        {
            root = new AVLNode(val);
            root->balance = Balance(root);
            return root;
        }
        if (val == root->val)//不允许出现相同的值
        {
            cout << "error!" << endl;
            return root;
        }
    
        if (val < root->val)//小于
        {
            root->left = AVL_Insert(root->left, val);
            root->balance = Balance(root);
            //插入成功后,进行平衡调整
            if (root->balance > 1)
            {
                if (val < root->left->val)//LL型
                {
                    root = LL_Rotate(root);
                }
                else  //LR型
                {
                    root = LR_Rotate(root);
                }
            }
        }
        if (val > root->val)
        {
            root->right = AVL_Insert(root->right, val);
            root->balance = Balance(root);
            //插入成功后,进行平衡调整
            if (root->balance < -1)
            {
                if (val > root->right->val)//RR型
                {
                    root = RR_Rotate(root);
                }
                else  //RL型
                {
                    root = RL_Rotate(root);
                }
            }
        }
        root->balance = Balance(root);
        return root;
    }
    

    img
    如上图,找到插入的位置后递归返回,之后开始判断是否平衡;之后递归栈不断出栈,判断是否平衡。

    展开全部

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
编辑
预览

报告相同问题?

悬赏问题

  • ¥50 如果使用python进行ERA5 10米风场预报检验
  • ¥15 navicat解析mysql密码
  • ¥15 SDAPI(关键词-table)
  • ¥15 unity安卓打包出现问题
  • ¥15 爱快路由器端口更改错误导致无法访问
  • ¥20 安装catkin时遇到了如下问题请问该如何解决呢
  • ¥15 VAE模型如何输出结果
  • ¥15 编译python程序为pyd文件报错:{"source code string cannot contain null bytes"
  • ¥20 关于#r语言#的问题:广义加行模型拟合曲线后如何求拐点
  • ¥15 fluent设置了自动保存后,会有几个时间点不保存
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部