c++ - 連想配列、配列およびツリー

Question

2 つの質問があります。Array Abstract データ型を変更して連想配列を実装するにはどうすればよいですか? ツリー抽象データ型を変更して連想配列を実装するにはどうすればよいですか?

Answer 1

配列から連想配列を作成するには、通常、ある種の構造の配列から始めます。

struct item {
    key_type key;
    value_type value;
};

次に、s を使用keyして s を検索しvalueます。効率のために、通常は s に基づいて配列をソートするkey必要があるため、バイナリ検索 (または、キーの分布にある程度の予測可能性がある場合は補間検索) を使用できます。

ツリーの場合、バイナリ検索がデフォルトであることを除いて、ほとんど同じことを行います。配列の場合と非常によく似たノードに加えて、いくつかのポインターが作成されます。

struct node { 
    key_type key;
    value_type value;
    struct node *left;
    struct node *right;
};

関連するツリーのタイプによっては、別のポインターを使用して、スレッド化されたツリーやバランス情報 (AVL または RB ツリーなど) を作成することもできます。逆に、B ツリーの場合は、連想配列とほぼ同じようなノードの配列になり、それらをリンクしてバランスの取れたツリーにします。