C언어 이진 트리 검색 함수 tfind()

2020. 3. 14. 06:27 컴퓨터/프로그래밍

C함수 이진트리 검색 tfind()

tfind()는 이진트리에서 데이터를 검색하고 있으면 해당 노드의 포인터를 없으면, 없으면 NULL을 반환합니다.

  • 헤더: search.h
  • 형태: void *tfind(const void *key, void **rootp, int (*compar)(const void *, const void *))
  • 인수: const void *key 찾으려는 자료의 포인터 주소
    void **rootp 이진 트리 포인터
    int (*compar)(const void *, const void *) 두 노드를 비교하기 위한 함수 포인터
  • 반환: void * 찾은 노드의 포인터 주소, 만일 찾지 못했다면 트리에 자료를 추가하고 추가된 노드의 포인터를 반환
caution

선형 리스트와 이진트리

정렬된 테이블은 bsearch() 함수로 아주 빠르게 검색할 수 있으나 정렬되어 있지 않으면 제대로 검색할 수 없습니다. 그래서 새로운 자료를 등록할 때마다 계속 정렬해 주어야 하는데, 데이터가 많아지면 많아질수록 부담이 됩니다. 이 문제를 선형 리스트로 빠르게 처리할 수 있습니다.

선형 리스트는 자료를 가지고 있는 노드마다 이전과 다음 노드를 가리키는 포인터를 가지고 있어서 노드 하나만 알면 앞과 뒤의 포인터로 이전과 다음 노드의 자료를 구할 수 있습니다.

여기에 새로운 자료를 추가할 때, 각 노드의 크기와 비교하여 포인터 정보만 갱신해 줍니다.

즉, 각 노드의 데이터를 이동할 필요 없이 포인터 정보만 갱신해 주면 정렬이 이루어집니다.

선형 리스트가 자료를 추가하거나 정렬하기는 문제가 없습니다만, 이진 검색하기에는 부족한 구조입니다. 정렬의 중간 노드를 알기 위해서는 전체 노트 개수를 확인하고 노드를 추적해 가야 합니다.

이진트리는 선형 리스트에 더 발전된 구조로 자료를 입력할 때부터 정렬과 함께 이진 검색이 용이하도록 데이터의 크기에 따라 트리식으로 정렬하는 구조입니다.

이진트리의 노드는 2개의 자식 노드만 가질 수 있으며, 왼쪽과 오른쪽 자식 노드는 크기에 따라 좌우로 나뉘게 됩니다. 만일 45를 찾는다면 선형 리스트처럼 포인터 정보를 이용하여 검색하게 됩니다.

이와 같은 구조로 이진트리에서는 빠르게 정렬과 검색할 수 있습니다.

reference

이진트리 관련 함수

예제

#include <stdio.h>
#include <search.h>
#include <string.h>

void print_tree( const void *node, VISIT order, int level)
{
   char *str;

   str   = *(char **)node;

   if ( ( postorder == order)  ¦¦
        ( leaf      == order) )
      printf( "%d %s\n", level, str);
}
int compare( const void *cmp1, const void *cmp2)
{
   return strcmp( (char *)cmp1, (char *)cmp2);
}
int main( void)
{
   void  *btree = NULL;
   char  **ptr;
   char  *str;

   tsearch( "a"      , &btree, compare);
   tsearch( "b"      , &btree, compare);
   tsearch( "c"      , &btree, compare);
   tsearch( "jwmx"   , &btree, compare);
   tsearch( "badyak" , &btree, compare);    // badayak 오타
   tsearch( "com"    , &btree, compare);

   twalk( btree, print_tree);

   printf( "-------------------------------\n");

   ptr   = tfind( "jwmx"  , &btree, compare);
   if ( ptr){
      str   = *ptr;
      printf( "%s\n", str);
   }
   ptr   = tfind( "badayak"  , &btree, compare);
   if ( ptr){
      str   = *ptr;
      printf( "%s\n", str);
   }
   return 0;
}

실행 결과

]$ ./a.out
1 a
0 b
2 badyak
1 c
3 com
2 jwmx
-------------------------------
jwmx
]$
이 댓글을 비밀 댓글로

티스토리 로그인이 풀리면 여기를 클릭하세요.

error: Content is protected !!