对removeMin的理解，不知道对不对

Question

不用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 的情况是不是不会存在？

Answer 1

liuyubobobo 2019-09-11 15:17:13

1）

是的，不用 removeMin 是因为它没有维护 height，自然也没有维护平衡。

实际上，让 removeMin 维护 height，进而维护平衡，是没问题的。但即使如此，在 remove 中，也不需要使用 removeMin，因为我们现在的做法，相当于只维护了一次平衡。但是如果调用 removeMin，就维护了两次平衡。

2）

存在，可以尝试把代码中的条件改成 if (balanceFactor > 1 && getBalanceFactor(retNode.left) > 0)

用上一小节的测试用例，你应该可以看到报错：）

继续加油！：）

• 提问者 慕桂英雄 #1

  非常感谢！