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

Question

我刚刚完成了面试,我正在努力解决这个问题,这对我来说是一个非常难的问题.

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

我的第一个答案是使用红黑树,这当然可以完成这项工作,但我必须假设他们没想到我会在15分钟内实施一棵红黑树.

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

谢谢,

戴夫

Answer 1

我个人认为,最好的方法是使用像treap一样的随机二叉搜索树.这并不能绝对保证树的平衡,但很有可能树会有很好的平衡因子.treap通过用均匀随机数增加树的每个元素来工作,然后确保树是关于键的二元搜索树和关于均匀随机值的堆.插入treap非常容易:

1. 选择一个随机数以分配给新添加的元素.
2. 使用标准BST插入将元素插入BST.
3. 虽然新插入的元素的键大于其父键的键,但执行树旋转以将新元素置于其父元素上方.

最后一步是唯一真正困难的一步,但如果你有时间在白板上解决这个问题,我很确定你可以在面试中即时实现这一点.

另一个可能有效的选择是使用一个splay树.它是另一种快速BST,可以在假设您具有标准BST插入功能和树旋转功能的情况下实现.重要的是,splay树在实践中非常快,并且已知它们(在恒定因子内)至少与任何其他静态二叉搜索树一样好.

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

希望这可以帮助!

Answer 2

AA 树比红黑树简单一点，但我无法立即实现它。