algorithm - 重新平衡任意 BST？

Question

引用:我被问到这个问题@MS SDE 面试，第三轮。这不是作业问题。我也考虑了一下，并在下面提到了我的方法。

问题:修改 BST，使其尽可能平衡。不用说，您应该尽可能高效。

提示:面试官说这是一个逻辑问题，如果你换个角度思考你就会得到答案。不涉及困难的编码。
--> 话虽如此，我认为他并不希望我指出 AVL/RB 树。

我的解决方案:我提出，我将对树进行中序遍历，将中间元素作为新树的根(我们称之为新根)。然后到中间元素的左边，将它的中间元素作为树根新根的左子树的根。右半部分同样如此。递归地执行此操作将给出最佳的平衡 BST。

为什么我在这里张贴它:但他对答案并不满意 :( 那么，真的有一种方法可以做到这一点而无需使用权重/RB 着色策略，还是他只是在跟我开玩笑？请提出您的专家意见。

重复？不!我知道有这个 question但是请求者提出的解决方案太复杂了，另一个说的是AVL树。

Answer 1

您可能想查看 Day-Stout-Warren 算法，这是一种 O(n) 时间，O(1) 空间算法，用于将任意二叉搜索树 reshape 为完全二叉树。直观上，该算法的工作原理如下:

1. 使用树旋转，将树转换为退化链表。
2. 通过对链表应用选择性旋转，将链表转换回完全平衡的树。

这个算法的美妙之处在于它以线性时间运行并且只需要恒定的内存开销；事实上，它只是 reshape 底层树，而不是创建新树并复制旧数据。编写代码也相对简单。

希望这对您有所帮助!