平衡BST [英] Balancing a BST

问题描述

参考：
我被问到这个问题@MS SDE面试，第3轮。这不是一个家庭作业的问题。我也给了一个想法，并提到我的方法。

问题：
修改BST，使其变得平衡可能。不用说，你应该尽可能高效。

提示：
采访者说这是一个逻辑问题，如果你有所不同，你会得到答案。没有困难的编码涉及。

- >话虽如此，我不认为他期待我指向AVL / RB树。

我的解决方案：
我建议，我会按顺序遍历树，将中间元素作为新树的根（可以称之为新根）。然后到中间元素的左边，把它的中间元素作为树根新根的左子树的根。同样地，对于正确的部分。
递归递归将给出最佳的平衡BST。

为什么我在这里张贴：
但他是不满意的答案:(所以，真的有一种方式做这个不重要/ RB着色策略，还是他只是愚弄我？
请放在你的专家的想法。 p>

重复？否！
我知道这是问题，但是请求者提出的解决方案太复杂了，其他人就AVL树谈论。

解决方案

您可能需要查看 Day-Stout-Warren 算法，它是一种O（n）时间O（1）空间算法，用于将任意二进制搜索树重新整形为一个完整的二叉树，直观地说，算法的工作原理如下：

1. 使用树轮换，将树转换为简并链表。


2. 通过应用选择轮换链接到列表中，将列表转换为完全平衡的树。

该算法的优点是它以线性时间并且只需要恒定的内存开销;实际上，它只是重塑基础树，而不是创建一个新的树，并复制旧的数据。代码编码也比较简单。

希望这有帮助！

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.

Question: Modify a BST so that it becomes as balanced as possible. Needless to mention, you should do it as efficient as possible.

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.

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.

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.

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:

1. Using tree rotations, convert the tree into a degenerate linked list.
2. By applying selective rotations to the linked list, convert the list back into a completely balanced tree.

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.

Hope this helps!

这篇关于平衡BST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！