3

バイナリ ツリーを作成しています。新しい文字列ノードをツリーに追加するときは、最初にそのノードが既に存在するかどうかを検索する必要があります。その場合、別のノードに追加するのではなく、その値を 1 つ増やす必要があります。

これを行うのに最適なデータ構造はどれですか?

4

4 に答える 4

1

私があなたを誤解していなければ、あなたの質問はとても簡単です。2 つのメンバー変数を保持するクラスを作成するだけです。

public class Node {
    v1 data_type_1;
    v2 data_type_2;
}

これをバイナリ ツリーのノードとして使用します。

于 2013-03-27T18:33:49.000 に答える
1

バーニーの答えは良いです。しかし、あなたの質問にもう少し具体的に答えるために、おそらくノードクラスを次のようにしたいと思うでしょう:

public class Node
{
    String value;
    int count;

    Node leftChild;
    Node rightChild;
}

ツリー用にこれらのインスタンスを作成します。これらのインスタンスの 1 つが「ルート」になります。leftChild他のすべてのインスタンスは、およびを介して、ルートから直接または間接的にハングしますrightChild。

幸運を！

于 2013-03-27T18:56:28.380 に答える
0

ええ、本質的に多分

https://github.com/JohannesLichtenberger/sirix/tree/master/bundles/sirix-core/src/main/java/org/sirix/index/avltree

役立ちます。これは、バランスの取れたバイナリ ツリーである AVLTree の実装です。他のコンテンツも保存できるように、ジェネリック型で実装します（そして私は持っています）。

私の場合、ほとんどの部分をメインメモリに格納できるインデックス構造として使用されています（ただし、バージョン管理アルゴリズムを使用するディスク上の表現でも使用されます）。文字列/パスの組み合わせ (キー) と、パスに属する ID の単純なセット (値) を保存しています。

ただし、おそらく、2 つの子ノードへの 2 つの「ポインター」、または 2 つの Node オブジェクトへのメモリ内参照のいずれかを格納する必要があります。

編集: Google Guava の今後の BinaryTreeTraverser をよく見てください: https://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/collect/BinaryTreeTraverser .java

于 2013-03-27T18:53:37.563 に答える
0

そのため、構造体のモットーは、カウントで重複を減らすことによってメモリを最小限に抑えることです。そして、ソートされた順序でデータを保存します。

このノードは、ツリーに役立つ可能性があります。

public class node
{
   String value;
   int count;
   node left;
   node right;
}

しかし、これよりも優れた解決策があります TreeMap です。ここでの検索は O(1) (重複カウントの増分は検索と同等) を取るため、前のケースでは O(log(n)) です。

Map testTreeMap = new TreeMap();
if(testTreeMap.get(MyString)!=null)
{
testTreeMap.put(MyString, testTreeMap.get(MyString) +1)
}
else
{
testTreeMap.put( MyString , Integer(count) ) // count=1
}

これであなたは完全に完成しました.. !!

http://tutorialswithexamples.com/java-treemap-tutorial-and-examples/

于 2013-03-27T20:43:10.357 に答える