对removeMin的理解，不知道对不对
来源：12-8 基于AVL树的集合和映射
慕桂英雄
2019-09-11
不用removeMin是因为他没有维护height，只是简单地删掉了子树里最左边的那个点（也就是最小的点），这个点其实没有被真的删掉而是被调到上面去顶替被真正删掉的点。而如果原来决定右侧子树height的较长的主干线中包含了这个最小点，这个主干线的height其实会-1，不做维护的话可能会发生一个节点height是5，但是左子树height是3的情况，而往后递归的过程中，仍旧把这个子树按照height为5来计算（其实应该是4了）。可能就会造成不平衡的树但是上层的递归却判断不出来。
还有个地方
if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0)
return rightRotate(retNode);
LL的判断中 getBalanceFactor(retNode.left) == 0 的情况是不是不会存在？
写回答
1回答
-
1）
是的，不用 removeMin 是因为它没有维护 height，自然也没有维护平衡。
实际上，让 removeMin 维护 height，进而维护平衡，是没问题的。但即使如此，在 remove 中，也不需要使用 removeMin，因为我们现在的做法，相当于只维护了一次平衡。但是如果调用 removeMin，就维护了两次平衡。
2）
存在，可以尝试把代码中的条件改成 if (balanceFactor > 1 && getBalanceFactor(retNode.left) > 0)
用上一小节的测试用例，你应该可以看到报错：）
继续加油！：）
012019-09-14
相似问题