2

これがランダムな質問のように思われる場合は申し訳ありませんが、私は 100,000 を超える名前と値のペア (必要に応じてハイスコアと呼んでください) のデータベースを、バランスのとれた二分探索木、AVL スタイルに格納しています。ほとんどの場合、スコアを一覧表示するために、BST をインオーダー トラバーサルまたはリバース オーダー トラバーサルで出力しますが、今日、ツリーをランダム (または疑似ランダム) 順序で出力する必要があることに気づきました。これを行うための受け入れられた、または最適な方法はありますか?すべてのノードに一度だけアクセスしますが、予測できない方法でアクセスしますか?

PS -- 幅優先トラバーサルについて考えましたが、それは常に同じように行われるため、実際にはランダムではありません。これは一般的な問題のように思われるため、何か賢い方法、または理想的なインタビューの答えが必要です。ノードを訪問済みとしてマークするか、外部追跡データ構造を作成する以外に、本当に賢いものは思いつきませんでした。

4

1 に答える 1

1

これに対する答えが、BSTを取得して線形化し、印刷するだけではない理由がわかりません。ここでの懸念は、このようなデータ構造を線形化すると大量のメモリが必要になる可能性があることだと思います。この場合、いつでもツリーの一部を選択して線形化し、ジャンプすることができます。ポインターをランダムにトラバースして、うまく機能する順序付けを期待するのは悪い考えです。常に最後のノードを探すのにうんざりしてしまいます。完全な二分木があれば、いつでも数値を考え出し、根から始めることができます (基本的に、木の完全性プロパティから無料で線形化を取得できます)。

編集：

この記事は機能的な実装に基づいていますが、役に立つかもしれません。私はそれをすべて読んだわけではないので、すべてを反復するためにどのように機能するかはわかりませんが、単に単一のノードを取得したい場合は、これを使用できます..

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

于 2012-05-17T03:38:50.953 に答える