리눅스에서 이진 검색 트리에 대한 복수 검색 키 C

Question

나는 이진 트리를 검색 테이블로 정의한다. 트리는 연결된리스트 바이너리 트리이며 노드는 다음과 같다.

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

typedef table_t node_t *; 그것은 데이터베이스처럼, 참으로

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

: 은 그래서

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

처럼

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

지금은 여러 개의 키가

같은 기능을 가지고 있고 같은 기능을 갖고 싶어 항목에 대한 키를 검색 할 수 있습니다.

소스 코드 예제가 있습니까? 나는 리눅스 C 감사를 사용하고 있습니다!

Answer 1

글쎄, 이진 트리에서 키는 서로에 대해서만 의미가 있습니다. key1_b가 오른쪽 브랜치에서 key1_b가 더 크거나 작을 때만 (당신이 구조하는 방법에 따라) key1_a가 왼쪽 브랜치에서 의미가 있음을 의미합니다. 두 세트의 키가있는 트리가있는 경우 동일한 비율을 가진 경우 동일한 트리 데이터 구조에있을 수 있다고 가정합니다. 에서처럼, key2의 각 키가 정확히 key1 위의 50입니다. 그러나 그것은 전혀 유용하지 않을 것입니다.

내가 가지고있는 유일한 아이디어는 일부 null 값 키가 있으므로 만드는 것입니다. 그래서 당신이 당신의 나무를 횡단하고 있다면, 당신은 key2의 잎이 아니라 key2의 잎에 있다면, 당신은 계속 가고 아래의 나머지 나무들은 키에 null 값 (어쩌면 -1?)을 가질 것입니다. 또는 부울 트리거를 갖게하여 key1이 트리의이 분기에 더 이상 존재하지 않도록합니다. 설명하기가 어렵지만, 제가 의미하는 바를 보시겠습니까? 기본적으로 거의 2 개의 inter-weaved 나무로 취급하고, 당신이 갈라질 때까지 함께 갈 것입니다 (그리고 실제 나무 구조를 동일하게 유지하면서 키의 하나에 대해 null 값을가집니다)

소리가납니다 지나치게 복잡하기 때문에 가치가 있는지 나는 모른다.

Answer 2

바이너리 트리는 단일 키로 만 인덱싱 할 수 있습니다. 여러 키를 사용하여 인덱싱 할 경우

, 당신은 모든 키에 대한 메타 트리를 구축 할 수 있습니다, 메타 트리 메타 - 노드 (들)이 여기서

당신은 두 그루의 나무를 가질 수

typedef struct meta_node 
{ 
    int index; 
    node * data; 

    ... 
} 
meta_node_t; 

Answer 3

하지만, 여전히 같은 노드를 사용하면 노드를 만들 때

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으로 연결 한 다음 노드 자체로 연결합니다.

삭제하려면 먼저 두 트리에서 노드의 연결을 해제해야합니다. 그러면 노드를 해제 할 수 있습니다.