algorithm - 从整数流创建平衡二叉搜索树

Question

我刚刚结束了一次求职面试，我一直在为这个问题而苦恼，在我看来，这个问题很难回答 15 分钟的面试。

问题是:编写一个函数，给定一个整数流(无序)，构建一个平衡搜索树。现在，您不能等待输入结束(它是一个流)，因此您需要动态平衡树。

我的第一个答案是使用红黑树，这当然可以，但我必须假设他们不希望我在 15 分钟内实现红黑树。

那么，对于这个我不知道的问题，有什么简单的解决方案吗？

谢谢，

戴夫

Answer 1

我个人认为最好的方法是使用随机二叉搜索树，例如 treap 。这并不能绝对保证树是平衡的，但树很有可能具有良好的平衡因子。 treap 的工作原理是用一个均匀随机数来增加树的每个元素，然后确保树是关于键的二叉搜索树和关于均匀随机值的堆。插入陷阱非常容易:

1. 选择一个随机数分配给新添加的元素。
2. 使用标准 BST 插入将元素插入 BST。
3. 当新插入元素的键大于其父元素的键时，执行树旋转以使新元素位于其父元素之上。

最后一步是唯一真正困难的一步，但如果你有时间在白板上解决它，我很确定你可以在面试中即时实现它。

另一个可能有效的选项是使用 splay tree 。这是另一种可以实现的快速 BST，假设您具有标准 BST 插入功能和进行树旋转的能力。重要的是，splay 树在实践中非常快，并且众所周知它们(在常数因子内)至少与任何其他静态二叉搜索树一样好。

根据“搜索树”的含义，您还可以考虑将整数存储在一些为查找整数而优化的结构中。例如，您可以使用 bitwise trie 用于存储整数，它支持与机器字中的位数成比例的时间查找。这可以使用递归函数查看位来很好地实现，并且不需要任何类型的旋转。如果您需要在 15 分钟内完成一个实现，并且面试官允许您偏离标准的二叉搜索树，那么这可能是一个很好的解决方案。

希望这对您有所帮助!