首页 > 试题广场 >

题目来源于王道论坛在图B-1所示的平衡二叉树中，插入

[单选题]

题目来源于王道论坛

在图B-1所示的平衡二叉搜索树中，插入关键字48后得到一棵新平衡二叉搜索树。在新平衡二叉搜索树中，关键字37所在结点的左、右子结点中保存的关键字分别是（）。

图B-1

但求八月九月好运！

所以这题目是错的，应该是平衡搜索树，而不是平衡二叉树

发表于 2019-05-27 12:18:00 回复(1)

更多回答

推荐

林呼

插入48以后，该二叉树根结点的平衡因子由-1变为-2，在最小不平衡子树根结点的右子树（R）的左子树（L）中插入新结点引起的不平衡属于RL型平衡旋转，需要做两次旋转操作（先右旋后左旋）。

调整后，关键字37所在结点的左、右子结点中保存的关键字分别是24、53。

发表于 2018-09-03 20:29:16 回复(0)

牛客1382

平衡二叉树全称是平衡二叉搜索树，所以本质是二叉搜索树

左结点的权值比根节点小，根结点权值比右结点小，以此规则将48插到37的右子树里去。 插入48之后属于右左双旋转的情况，按照图示的方法先做右单旋转，再做左单旋转

右单旋转：以37为轴，53顺时针旋转（向下），原本是37左孩子的48成为53的左孩子24的右孩子由53变为37

左单旋转：仍然以37为轴，24逆时针旋转（向下），成为37的左孩子

详细说明

发表于 2019-12-30 12:18:34 回复(0)

茴香小包子

补一句：解题重点是找到“找到由于插入新节点而失去平衡的最小子树的根节点”，然后根据这个节点，进行旋转

发表于 2021-09-08 09:24:21 回复(0)

提交观点

问题信息

树

上传者：林呼

难度：

4条回答 349收藏 3757浏览

扫一扫，把题目装进口袋