在节点删除之前或之后平衡 AVL 树？

Question

本练习要求学生从 AVL 树中删除一个节点。在这种情况下，这需要一些平衡，因为最深和最浅深度之间的差异> 1。但是平衡应该发生在删除之前还是之后？还是无所谓？

image of AVL tree in question

Answer 1

基本上你想像从 BST 中一样删除。然后计算你的深度因子（树的每条路径有多长）并根据不平衡的路径像往常一样使用插入进行旋转。因此，要回答您的问题，请在删除后进行轮换。