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 nte 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.
Wenn Sie Ihre Blätter so strukturiert haben, dass sie selbst in einem indexierbaren Datentyp wie einem Array gespeichert werden, können Sie leicht (Pseudocode):
%Vor%Das ist ein schönes, erfrischendes O (1): -)
Natürlich kann es Löcher geben, daher müssen Sie möglicherweise von dort aus 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.