0

二分探索木で重複を処理するエレガントな方法は何ですか? 各キーにいくつかの異なる値が関連付けられていると仮定しましょう。私がする必要があるのは、すべての値を順番に繰り返すことです。したがって、キー 1 で 2 つの値 A と B があり、キー 2 で 1 つの値 C がある場合、次のような呼び出しで (1,A)、(1,B)、(2,C) のペアを取得したいと思います。 TreeIterator.next();

私は考えることができます：

  • 各ノードにはキーと、同じキーを持つ値が入る値の配列があります
  • 各ノードにはvisitedフラグがあります

他の提案はありますか？一般的なガイドラインとして、Tree の実装はできるだけ抽象的にしたいと考えています。

4

1 に答える 1

1

基本的に、各キーの値のリストが必要なようです。はい。したがって、マップに追加するプロセスは次のとおりです。

  • キーは存在しますか？
    • その場合は、既存のリストに値を追加します。
    • そうでない場合は、ツリー内の適切なポイントに (通常どおり) 新しいノードを作成し、1 つの値のリストから開始します。

マップを反復処理するときの一般的なパターンは次のとおりです。

  • 左側のノード (小さいキー) からすべての値を生成します
  • このノードのすべての値を生成します - (key, value1)、(key, value2) など
  • 右側のノードからすべての値を取得します (より大きなキー)

もちろん、学習目的でこれを自分で実装する必要がない場合は、Guavaのなどの既製のマルチマップを使用できますTreeMultimap。独学で実装する場合は、まず「通常の」二分探索マップを実装し、そこから始めます。

于 2013-03-16T10:54:29.707 に答える