重新平衡任意 BST? [英] Rebalancing an arbitrary BST?
问题描述
参考:我被问到这个问题@MS SDE 面试，第三轮.这不是家庭作业的问题.我也考虑了一下，并在下面提到了我的方法.
Reference: I was asked this question @MS SDE interview, 3rd round. And it's not a homework problem. I also gave it a thought and mentioning my approach below.
问题:修改 BST，使其尽可能平衡.不用说，你应该尽可能高效.
Question: Modify a BST so that it becomes as balanced as possible. Needless to mention, you should do it as efficient as possible.
提示:面试官说这是一个合乎逻辑的问题，如果你换个思路你就会得到答案.不涉及困难的编码.
--> 话虽如此，我不认为他希望我指向 AVL/RB 树.
Hint:
Interviewer said that this is a logical question, if you think differently you will get the answer. No difficult coding involved.
--> Having said that, I do not think he was expecting me to point to AVL/RB Trees.
我的解决方案:我建议，我会做树的中序遍历，将中间元素作为新树的根(我们称之为新根).然后到中间元素的左边，取中间元素作为新根树的左子树的根.同样做右侧部分.递归地执行此操作将提供最佳的平衡 BST.
My Solution: I proposed that, I would do inorder traversal of tree, take middle element as root of new tree(lets call it new root). Then go to the left part of middle element, take its middle element as root of left subtree of tree rooted new root. Similarly do for right part. Doing this recursively will give the optimal balanced BST.
我为什么在这里发布它:但是他对答案并不满意:(那么，真的有办法在不采用权重/RB着色策略的情况下做到这一点，还是他只是在逗我?请提出您的专业意见.
Why I am posting it here: But he was not satisfied with the answer :( So, is there really a way of doing this w/o going for weights/RB coloring strategy, or was he just fooling around with me? Please put in your expert thoughts.
重复?不！我知道有这个问题但是请求者提出的解决方案太复杂了，和另一个谈论 AVL 树.
Duplicate? No! I know there is this question but the solution proposed by requester is too complicated, and other one talks about AVL trees.
推荐答案
您可能想要查看 Day-Stout-Warren 算法，这是一种 O(n) 时间、O(1) 空间的算法，用于将任意二叉搜索树重塑为完全二叉树.直观上，该算法的工作原理如下:
You might want to look into the Day-Stout-Warren algorithm, which is an O(n)-time, O(1)-space algorithm for reshaping an arbitrary binary search tree into a complete binary tree. Intuitively, the algorithm works as follows:
- 使用树旋转，将树转换为退化链表.
- 通过对链表应用选择性旋转，将列表转换回完全平衡的树.
这个算法的美妙之处在于它以线性时间运行，并且只需要恒定的内存开销；实际上，它只是重塑底层树，而不是创建新树并复制旧数据.编码起来也比较简单.
The beauty of this algorithm is that it runs in linear time and requires only constant memory overhead; in fact, it just reshapes the underlying tree, rather than creating a new tree and copying over the old data. It is also relatively simple to code up.
希望这有帮助！
这篇关于重新平衡任意 BST?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
