3

二分木を検索テーブルとして定義します。ツリーはリンク リスト バイナリ ツリーで、ノードは次のようになります。

typedef struct node{
    int key;
    char *buf;
    ...
}node_t;

typedef table_t node_t *; だから私は次のような機能を持っています

  insert(table_t table, node_t node)
  search(table_t table, node_t node)

今、私は複数のキーを持っています

typedef struct node{
    int key1;
    int key2;
    char *buf;
    ...
}node_t;

次のような機能が必要です。

  search_by_key1(table_t table, node_t node, int key1)
  search_by_key2(table_t table, node_t node, int key2)

実際、これはデータベースのようなもので、アイテムの任意のキーを検索できます。

ソースコードの例はありますか? 私はLinux Cを使用しています ありがとう！

4

4 に答える 4

1

二分木は、単一のキーによってのみ索引付けできます。

複数のキーを使用してインデックスを作成する場合は、キーごとにメタツリーを構築できます。メタツリーにはメタノードがあります。

typedef struct meta_node
{
    int index;
    node * data;

    ...
}
meta_node_t;
于 2013-06-10T10:38:50.547 に答える
0

二分木では、キーは相互に関連してのみ意味を持ちます。つまり、key1_a は、key1_b が右側のブランチで大きい/小さい場合にのみ、左側のブランチで意味を持ちます (構成方法によって異なります)。2 セットのキーのツリーがある場合、仮説的には、それらが同じ比率を持っていれば、同じツリー データ構造にある可能性があります。のように、key2 の各キーが key1 の上に正確に 50 ある場合。しかし、それは実際にはまったく役に立ちません。

私が持っている唯一のアイデアは、null値のキーがいくつかあるようにすることです。そのため、ツリーをトラバースしていて、key1 のリーフにいるが key2 のリーフにいない場合は、そのまま続行すると、ツリーの下位の残りのキーに null 値 (おそらく -1?) が含まれます。または、ブール値のトリガーを使用して、key1 がツリーのこのブランチに存在しなくなるようにします。説明するのはちょっと難しいですが、私の言いたいことがわかりますか？基本的にそれを2つの織り交ぜられたツリーとしてほぼ扱い、分岐する必要があるまで一緒に進みます（実際のツリー構造を同じに保ちながらそれを行いますが、キーの1つにnull値を持ちます）

あまりにも複雑に聞こえるので、それだけの価値があるかどうかはわかりません。

于 2013-06-09T18:26:07.327 に答える
0

2 つのツリーを持つことができますが、それでも同じノードを使用します。

struct basic_node {
    int key;
    struct basic_node *left, *right;
    struct node *node;
};
struct node {
    struct basic_node tree1;
    struct basic_node tree2;
    char *data;
};

struct node *tree1_root, *tree2_root;

ノードを作成するときは、 を割り当ててから、そのキーに従ってそれぞれのツリーに個別にstruct node挿入します。basic_nodeそれぞれで、それを含むノードへのポインターをbasic_node設定します。node

検索するときは、いずれかのツリー ルートから開始し、単純な検索を実行します。これにより、目的の が表示されbasic_node、次にノード自体に移動します。

削除したい場合は、最初に両方のツリーからノードをリンク解除する必要があります。その後、ノードを解放できます。

于 2013-06-10T10:46:19.207 に答える