2010年计算机专业统考的一题关于平衡二叉树

Question

原题：在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在节点的左边、右子结点中保存的关键字分别是

答案选C，但我的重排序是：

这样的话就没答案了，请问我排的有什么问题？

Answer 1

插入48之后属于右左双旋转的情况，按照图示的方法先做右单旋转，再做左单旋转

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

24的右孩子由53变为37

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

（如有误敬请指正）

Answer 2

生成的二叉排序树的方法有问题吧，48插入后应是37的右孩子，使得二叉树失去了平衡，原因在右子树的左子树上插入一个结点失去平衡，是RL型，先找最小不平衡子树，是24为根结点的。从其出发沿插入方向寻找三个结点24,53,37，以37为旋转点，先将53，90右旋，成为37的右子树，后将24，13绕37左下旋，成为37的左子结，所以37的左右子结点为24，53选C追问

难道我生成的不是平衡二叉树吗？

追答

是平衡二叉树，但不符合题意

本回答被提问者和网友采纳

Answer 3

具体的RL型的旋转规则，记住就可以了。