我正在阅读这篇文章，其中提到我们可以通过以特定方式执行旋转来摆脱树的一侧，然后沿一个方向向下遍历树并删除元素。
虽然我理解他们想要做什么，但我不明白为什么？
与简单的后订单删除相比，这种类型的删除可以提供哪些优势？
我能想到的一个优点是节省了递归使用的内存，但我认为与遍历树两次（一次用于旋转，然后用于删除）相比，这是一个微不足道的开销。我在这里错过了什么吗？
问问题
77 次
1 回答
3
这篇文章似乎认为这种方法的重点是避免递归（以及它对堆栈空间的消耗）：“嗯......如果我们重新排列节点以使它们没有任何左子树怎么办？那么我们可以向右下降，无需跟踪堆栈中的任何内容。”
一般来说，当我不能确定递归的深度是否合理时，我更愿意避免递归，因为在你用完任何其他类型的内存之前很久就会用完堆栈空间——在某些情况下，因为系统被设计为限制递归捕获导致无限递归的错误。但是，我认为这在这里不太重要，您已经承认同一包中的其他例程需要递归。此外，递归的深度取决于树的深度，对于平衡树，这将大致是它的节点数的对数，因此永远不应该太深。
于 2012-10-07T07:31:56.437 回答