6

O(log n) 時間でバランスの取れた二分探索木から均一に分散されたランダム値 (関数を呼び出すことは、ツリー内の任意の値を取得する可能性が等しくなる可能性があることを意味します) を取得することは可能ですか?

私の最初のアイデアは、乱数 0、1、または 2 を生成することでした。0 の場合は現在のノードから左のパスを使用し、1 の場合は右のパスを使用し、それ以外の場合はノードの値がランダム値になります。リーフ ノードにヒットした場合は、そのノードの値を取得します。ただし、これがランダムに配布されるとは思いません。

これは好奇心からであり、特定のアプリケーションのためではありません。

説明が必要な場合はお知らせください。

例は、ツリーがある場合です

     1
    / \
   2   5
       /
      3

を呼び出すと、1、2、3、および 5 の数字が均一に返されます。int get_random_number()

明確化: 他のすべての通常の BST 操作は、insert()、delete() などのように、O(log n) のままにする必要があります。

4

1 に答える 1

12

あなたのアイデアはランダムな分布を作成しません。根は、木の大きさに関係なく、1/3 の確率で摘み取られます。

ツリーの要素数がわかっている場合は、1 から N までの数値 k を生成し、ツリーの k 番目に大きい要素を取得します。バランスの取れたツリーの O(logn) でそれを行う方法については、こちらを参照してください。

于 2012-11-09T01:02:56.907 に答える