在插入一个节点后,从哪个节点开始判断是否平衡,删除一个节点后,在那个节点判断是否平衡?望有人回答,一定采纳,有代码演示就更好啦哈哈哈
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; }
如上图,找到插入的位置后递归返回,之后开始判断是否平衡;之后递归栈不断出栈,判断是否平衡。本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥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设置了自动保存后,会有几个时间点不保存