我觉得291行可以不用修改removeMin这条语句

Question

老师我认为successor.right=removeMin 并不需要改成remove(node.right,successor.key) 因为removeMin虽然会破坏平衡性，但是就算是确定破坏了，我们在下面retNode中也会判断，次数retNode肯定会被判断为不平衡，然后进入平衡条件LL,LR,RL,RR中进行修正。所以最后retNode修正后还是平衡。 只是如果改成remove(node.right,succesor.key)那么retNode就可能平衡也可能不平衡，就不一定进入4个平衡条件进行修正。
也就是其实不改，最后对retNode进行修正就完事了。如果改了，只是对removeMin（node.rightNode）进行修正。我觉得本质是没有区别的。不知道我这样理解对么?

Answer 1

liuyubobobo 2019-05-08 08:49:13

不对。必须修正。

我们后续的平衡修正，是修正以retNode为根节点的AVL树。也就是不平衡发生在retNode上，才能靠下面的逻辑修正。但是在removeMin的过程中，retNode的子节点，有可能产生了不平衡。

我们在这一小节的测试main函数中，remove后如果不平衡，会抛出异常。你可以按照你的思路，继续使用原来的removeMin试试看？会抛出异常的：）

继续加油！：）