以随机顺序打印平衡BST的最佳方法？

对不起，如果这看起来像一个随机问题，但我有一个超过100,000个名称/值对的数据库（称它们为高分，如果您愿意）存储在AVL风格的平衡二叉搜索树中。大多数时候，为了列出分数，我打印了BST，并进行了有序遍历或逆序遍历，但是今天我发现需要以随机（或伪随机）顺序打印树。有没有一些可接受的或最佳的方式来做到这一点：一次访问每个节点，但以不可预知的方式？以随机顺序打印平衡BST的最佳方法？

PS - 我想到了广度优先遍历，但是因为它总是以相同的方式发生，所以它并不是真正的随机性。必须有一些聪明的方式，或一些理想的面试答案，因为这似乎是一个普遍的问题;除了仅仅将节点标记为已访问或创建外部跟踪数据结构外，我还没有想出任何非常聪明的东西。

来源

2012-05-17 Cindeselia

我不知道为什么这个答案不仅仅是将BST，线性化，然后打印出来。我想你的担心是线性化这样的数据结构可能需要很多内存。如果是这种情况，你可以随时挑选出件树，将它们线性化，然后跳转。随机遍历指针并希望能够顺利运行的排序是一个糟糕的主意：您总是会因为寻找最后一个节点而陷入困境。如果你有一个完整的二叉树，你可以随时拿出数字并从根开始（实质上，你可以从树的完整属性中免费获得线性化）。

编辑：

我比我或许应该少明智的，因为最近我发现这篇文章，虽然它是基于一个功能的实现，它可能对你有用的。我没有看到这一切，所以我不知道它是如何工作，通过迭代的一切，但如果你只是想获得一个节点了，那么你可以使用这个..

http://okmij.org/ftp/Algorithms.html#random-tree-node

来源

2012-05-17 03:38:50

谢谢为了您的回应。对，我想我对线性化算法还没有足够的认识。你是否只是生成一堆随机的左遍历和右遍历，直到你唯一地覆盖它们？我知道如何从1：size生成一个随机的索引排序，但是看起来像这样我就可以将单个索引转换为树遍历了。 – Cindeselia

线性化我的意思是使用标准遍历遍历树，将它们粘贴在列表中，然后随机化列表。即使以懒惰的方式，如果通过随机指针追踪的变体实现，您可以使用任何算法执行类似等效的任何操作，您可以获得大致相当于在所访问的搜索空间范围内传递Thunk的内容。 –

我明白...但是，有点改变我的问题，因为标准遍历是O（n），我不知道我们是否可以有一些索引算法，允许我们随机访问O（1）。当然，按照随机顺序打印所有元素仍然需要完整的线性化，但是为每个节点预分配索引1尺寸的额外步骤可能需要更少的操作来完成一定数量的访问。对不起，我意识到这确实改变了这个问题。这个评论只适用于我们想要n Cindeselia

以随机顺序打印平衡BST的最佳方法？

回答

相关问题