从整数流创建一个平衡的二叉搜索树 [英] Create a balanced binary search tree from a stream of integers

问题描述

我刚刚完成了面试，我正在努力解决这个问题，在我看来，这是一个非常困难的问题，给了15分钟的面试。

问题是：
编写一个给定整数流（无序）的函数，构建一个平衡的搜索树。
现在，你不能等待输入结束（这是一个流），所以你需要平衡树上的空白。

我的第一个答案是使用一个红黑树，当然这个工作，但我必须假设他们没有想到我在15分钟内实施一个红色的黑树。

谢谢，

Dave

解决方案

我个人认为最好的方法是去一个随机二进制搜索树 treap 。这并不是绝对保证树的平衡，而是很有可能树的平衡因子很好。通过用均匀的随机数增加树的每个元素，然后确保树是相对于键的二叉搜索树和相对于均匀随机值的堆，可以进行捕获。插入一个宝贝非常容易：

1. 选择一个随机数字分配给新添加的元素。


2. 使用标准BST插入将元素插入到BST中。


3. 当新插入的元素的键大于其父项的键时，执行树的轮换以使新的元素高于其父母。

最后一步是唯一非常难的一个，但如果你有一些时间在一个白板我很确定你可以在面试中实时实现。

另一个可能工作的选项是使用 splay tree 。这是另一种可以实现的快速BST，假设您有一个标准的BST插入功能，并且可以执行树的旋转。重要的是，在实践中，播放树是非常快速的，并且已知它们（至少在一个常数因子中）至少与任何其他静态二叉树搜索树一样好。

根据搜索树的含义，您还可以考虑将整数存储在针对整数查找进行优化的某些结构中。例如，您可以使用 按位特技 来存储支持查找的整数在时间上与机器字中的位数成比例。这可以非常好地使用递归函数来查看位，并且不需要任何类型的旋转。如果你需要在十五分钟之内爆出一个实现，如果面试官允许你偏离标准的二叉搜索树，那么这可能是一个很好的解决方案。

希望这有帮助！

I have just finished a job interview and I was struggling with this question, which seems to me as a very hard question for giving on a 15 minutes interview.

The question was: Write a function, which given a stream of integers (unordered), builds a balanced search tree. Now, you can't wait for the input to end (it's a stream), so you need to balance the tree on the fly.

My first answer was to use a Red-Black tree, which of course does the job, but i have to assume they didn't expect me to implement a red black tree in 15 minutes.

So, is there any simple solution for this problem i'm not aware of?

Thanks,

Dave

解决方案

I personally think that the best way to do this would be to go for a randomized binary search tree like a treap. This doesn't absolutely guarantee that the tree will be balanced, but with high probability the tree will have a good balance factor. A treap works by augmenting each element of the tree with a uniformly random number, then ensuring that the tree is a binary search tree with respect to the keys and a heap with respect to the uniform random values. Insertion into a treap is extremely easy:

1. Pick a random number to assign to the newly-added element.
2. Insert the element into the BST using standard BST insertion.
3. While the newly-inserted element's key is greater than the key of its parent, perform a tree rotation to bring the new element above its parent.

That last step is the only really hard one, but if you had some time to work it out on a whiteboard I'm pretty sure that you could implement this on-the-fly in an interview.

Another option that might work would be to use a splay tree. It's another type of fast BST that can be implemented assuming you have a standard BST insert function and the ability to do tree rotations. Importantly, splay trees are extremely fast in practice, and it's known that they are (to within a constant factor) at least as good as any other static binary search tree.

Depending on what's meant by "search tree," you could also consider storing the integers in some structure optimized for lookup of integers. For example, you could use a bitwise trie to store the integers, which supports lookup in time proportional to the number of bits in a machine word. This can be implemented quite nicely using a recursive function to look over the bits, and doesn't require any sort of rotations. If you needed to blast out an implementation in fifteen minutes, and if the interviewer allows you to deviate from the standard binary search trees, then this might be a great solution.

Hope this helps!

这篇关于从整数流创建一个平衡的二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！