So wählen Sie einen zufälligen Knoten aus einem Baum

Question

Wie würde man ein zufälliges Element aus einem Baum auswählen? Ist es notwendig, die Tiefe/Größe des Baumes vorher zu kennen?

Answer 1

Tun Sie einfach für jeden Knoten einen zufälligen Anruf im Bereich 0 bis (Anzahl der Kinder) -1 und wählen Sie das nächste Kind nach dieser Nummer.

Wiederholen Sie dies, bis Sie in einem Blatt sind.

Answer 2

Es ist nicht. Um einen Knoten gleichmäßig nach dem Zufallsprinzip zu wählen, durchlaufen Sie den Baum einfach in beliebiger Reihenfolge. Sei der untersuchte n-te Knoten der Auserwählte mit der Wahrscheinlichkeit 1/n. Das heißt, notieren Sie den Knoten, den Sie in einer Variablen zurückgeben, und wenn Sie den n-ten Knoten betrachten, ersetzen Sie den aktuellen Knoten durch den n-ten mit der Wahrscheinlichkeit 1/n. Sie können durch Induktion zeigen, dass dies einen Knoten gleichmäßig nach dem Zufallsprinzip zurückgibt, ohne vorher wissen zu müssen, wie viele es sind.

Answer 3

Wenn Sie Ihre Blätter strukturiert haben in einem Index-fähigen Datentyp gespeichert, sich selbst zu sein, wie ein Array, dann können Sie leicht (Pseudo-Code):

random_leaf = leaf_pile[ random(size of leaf pile) ] 

Das ist eine schöne, erfrischende O (1) :-)

Natürlich kann es Löcher geben, also müssen Sie möglicherweise von dort iterieren. Wenn es als verknüpfte Liste gespeichert ist, können Sie es iterieren.

Nur eine Alternative zum Offensichtlichen bieten. Es hängt wirklich von Ihrer Datenstruktur und Ihrem häufigsten Anwendungsfall ab.