1

キーと値の両方を使用してBSTを実装する必要がありますか？次のようなメソッド呼び出しを持つBSTを実装できます。この場合、V値に基づいて、トラバーサルを左ノードと右ノードのどちらに移動するかを各ノードで比較します。

public class BST<V>
{
    public void Insert(V value)
    {
        //implementation
    }

    public V Remove(V value)
    {
        //implementation
    }

    //other methods
}

または、次のようなメソッド呼び出しを持つようにBSTを実装できます。ここで、Kキーは、左ノードと右ノードのどちらにトラバースするかを比較して決定します。

public class BST<K key, V value>
{
    public void Insert(K key, V value)
    {
        //implementation
    }

    //which of the following would then be the appropriate method signature?
    public V Remove(K key)
    {
        //implementation
    }
    //or?
    public V Remove(V Value)
    {
        //implementation
    }

    //other methods
}
4

4 に答える 4

2

キーを使用せず、値のみで問題ありません。ただし、これを行うと、ツリーは不変になります。値を変更すると、ツリーのバランスが崩れるため、安全ではなくなります。ノード値にプロパティゲッターのみを提供することにより、これを強制する必要があります。

于 2010-01-12T09:15:33.740 に答える
0

汎用データ構造の場合は、TKeyのIComparable制約でキー値ベースのAPIを使用することをお勧めします（キーと値の関係は事前にわからないため）。キーが値でもあるユースケース固有の実装の場合（たとえば、BSTは、指定されたキーが含まれているかどうかを判断するために使用されます）、キーベースのAPIを使用することをお勧めします。

于 2010-01-12T08:10:45.233 に答える
0

それはあなたが実際に何を必要としているかによります。連想データ構造が必要な場合は、Key-Valueベースの実装を実装する必要があります。そうでなければ、単に要素をソートされたコレクションに入れる場合、要素ごとに個別のキーを用意する必要はないと思います。すべての要素がComparableを実装していることを確認するか、カスタムComparator実装（TreeSet / TreeMapなど）、またはBSTの要素の全順序を設定する明確に定義されたスキームを渡すことができます。

于 2010-01-12T08:50:53.260 に答える
0

いいえ、機能するためにキーを必要とするデータ構造は他に何も必要としません。それはあなたがそれをどのように実装したいかに依存します。ほとんどの場合、キーと値のペアに基づくシステムを使用するのが最も便利ですが、一部の実装では、データ構造のユーザーに比較関数を指定させ、各ノードに「値」（ユーザー定義クラスのインスタンス）。このクラスには特にキーが含まれている場合がありますが、ユーザー指定の比較関数がすべてを処理するため、クラスの形式を知る必要はありません。

これが使用されている場所を考えることができる例は、Windowsカーネルです。

于 2010-01-12T09:29:16.413 に答える