给定一个空的二叉搜索树,依次插入以下元素:(5, 3, 7, 2, 4, 6, 8)。如果希望该二叉搜索树在插入操作后仍然保持平衡(使用AVL树的平衡规则),那么最终树的高度是多少?

答案解析

本题考察AVL树的插入和平衡调整。核心考点是AVL树的平衡规则和旋转操作。解题思路是模拟插入过程,并在必要时执行旋转操作。下面逐步进行插入并演示平衡过程: 1. 插入5: 树为 5 2. 插入3: 树为 5(3,) 3. 插入7: 树为 5(3,7) 4. 插入2: 树为 5(3(2,),7) 5. 插入4: 树为 5(3(2,4),7) 6. 插入6: 树为 5(3(2,4),7(6,)) 7. 插入8: 树为 5(3(2,4),7(6,8)) 此时 5 的平衡因子为 -2,需要进行旋转:以3为中心左旋,树变为 3(2,5(4,7(6,8))) 此时 7 的平衡因子为-2,需要进行旋转,以6为中心右旋,树变为3(2,5(4,6(7,8))) 此时 5 的平衡因子为-1,平衡,最终树为3(2,5(4,6(7,8))) 最终树的高度为3(3,5,6各一层)。 选项A,2 是错误的,高度不为2 选项B,3 是正确的,高度为3 选项C,4 是错误的,高度不为4 选项D,5 是错误的,高度不为5 易错点:忽略AVL树插入后的平衡调整,或者对旋转规则理解不清晰。
正确答案:B
随机推荐
开始刷题