次のような非常に多くのツリーの実装を見つけることができました。
http://sujitpal.blogspot.com/2006/05/java-data-structure-generic-tree.html
そして今、JavaでのUniform Recursive Treeの実装を探しています。本稿では、Uniform Recursive Tree の詳細について説明します。 http://www.sciencedirect.com/science/article/pii/S0022247X05004191
よろしくお願いします。
実際、これを実装するのはそれほど難しくありません。基本的に n 分ツリーから始めて、ノードをツリー内の既存のノードの 1 つに子として追加する方法を理解するだけです。
ノードを持つツリーのk場合、新しいノードは、前のノードのいずれか (つまり、セット内のノードk + 1のいずれか) の子になることができます。k{1, 2, ..., k}
必要なのは、現在ツリーに存在するすべてのノードのリストです。Treeこれは、データ構造内の別の内部構造であると私は主張します。次に、ツリーのノードの 1 つを選択する方法を理解する必要があります。これは確率関数によって行われます。この部分が少し不明確だと思いますが、それは主に、確率に関することをたくさん忘れてしまったためです (そして、学校では確率が嫌いでした)。しかし、この論文では、確率を計算する方法について説明しています。基本的に、一連の確率質量関数があります。したがって、 node1があり、次にnode がある場合2、 node2は node に接続されます (接続するノード1が 1 つしかないため2)。ノードは次の確率で3ノードに接続されます1p(2, 1)2またはの確率でノードへp(2, 2)。ただし、確認する必要があるのは、次のことです。
p(k, i) >= 0
と：
sigma(p(k, i)) from i = 1 to k equals 1
単純な実装では、既存のノードのリストからノードの 1 つをランダムに選択するだけです。