选择一个节点随机地从非平衡二叉树 [英] Select a Node at Random from Unbalanced Binary Tree

问题描述

我的一个朋友有下列的面试问题，和我们俩都不是很有把握正确的答案是什么。有没有人对如何处理这个想法？

  

给定一个不平衡的二叉树，描述了一种算法来选择在随机，使得每个节点具有被选择的同等概率的节点。

解决方案

您可以用树的单次做到这一点。该算法是相同的，与列表。

当你看到在树中的第一项，将其设置为选定的项目。

当你看到第二个项目，你在范围（0,2]选择一个随机数。如果是1，那么新的项目变成选定的项目。否则，你跳过该项目。

有关你看到的每个节点，增加数量，并与概率为1 /数，你选择它。因此，在第101个节点，你选择的范围（0101]一个随机数。如果是100，这个节点是新选择的节点。

当你完成遍历树，返回所选择的节点。操作为O（n）的时间，其中n是在树的节点数，和O（1）在空间中。没有preprocessing必需的。

One of my friends had the following interview question, and neither of us are quite sure what the correct answer is. Does anyone have an idea about how to approach this?

Given an unbalanced binary tree, describe an algorithm to select a node at random such that each node has an equal probability of being selected.

解决方案

You can do it with a single pass of the tree. The algorithm is the same as with a list.

When you see the first item in the tree, you set it as the selected item.

When you see the second item, you pick a random number in the range (0,2]. If it's 1, then the new item becomes the selected item. Otherwise you skip that item.

For each node you see, you increase the count, and with probability 1/count, you select it. So at the 101st node, you pick a random number in the range (0,101]. If it's 100, that node is the new selected node.

When you're done traversing the tree, return the selected node. The operation is O(n) in time, with n being the number of nodes in the tree, and O(1) in space. No preprocessing required.

这篇关于选择一个节点随机地从非平衡二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！