重新平衡任意BST? [英] Rebalancing an arbitrary BST?
问题描述
参考: 在第3轮@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.
推荐答案
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屋！
