我刚刚结束了一次工作面试，我一直在纠结这个问题，在我看来，在 15 分钟的面试中这是一个很难回答的问题。
问题是：
编写一个函数，给定整数流（无序），构建平衡搜索树。
现在，您不能等待输入结束（它是一个流），因此您需要动态平衡树。
我的第一个答案是使用红黑树，这当然可以完成这项工作，但我必须假设他们没想到我会在 15 分钟内实现红黑树。
那么，对于我不知道的这个问题有什么简单的解决方案吗？
Thanks,
Dave
我个人认为最好的方法是使用随机二叉搜索树，例如treap http://en.wikipedia.org/wiki/Treap。这并不能绝对保证树会平衡，但树很有可能具有良好的平衡因子。 Treap 的工作原理是用均匀随机数增加树的每个元素，然后确保该树对于键而言是二叉搜索树，对于均匀随机值而言是堆。插入陷阱非常容易：
- 选择一个随机数分配给新添加的元素。
- 使用标准 BST 插入将元素插入 BST。
- 当新插入元素的键大于其父元素的键时，执行树旋转以使新元素位于其父元素上方。
最后一步是唯一真正困难的一步，但如果您有时间在白板上解决它，我很确定您可以在面试中即时实现这一点。
另一个可能有效的选择是使用八字树 http://en.wikipedia.org/wiki/Splay_tree。这是另一种类型的快速 BST，假设您有标准的 BST 插入函数和进行树旋转的能力，就可以实现它。重要的是，八字树是极其在实践中速度很快，并且众所周知，它们（在恒定因子内）至少与任何其他静态二叉搜索树一样好。
根据“搜索树”的含义，您还可以考虑将整数存储在某种针对整数查找而优化的结构中。例如，您可以使用按位特里树 http://en.wikipedia.org/wiki/Trie#Bitwise_tries存储整数，它支持与机器字中的位数成比例的查找时间。使用递归函数来查看这些位可以很好地实现这一点，并且不需要任何类型的旋转。如果您需要在十五分钟内完成一个实现，并且面试官允许您偏离标准二叉搜索树，那么这可能是一个很好的解决方案。
希望这可以帮助！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
