C언어 이진트리 삭제 함수 tdelete()

2020. 3. 18. 07:01 컴퓨터/프로그래밍

C함수 이진트리 삭제 tdelete()

tdelete()는 이진 트리에서 데이터를 삭제합니다.

  • 헤더: search.h
  • 형태: void *tdelete(const void *key, void **rootp, int (*compar)(const void *, const void *))
  • 인수: const void *key 추가하려는 자료의 포인터 주소
    void **rootp 이진 트리 포인터
    int (*compar)(const void *, const 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( "jwmx"   , &btree, compare);
   tsearch( "badayak", &btree, compare);    
   tsearch( "com"    , &btree, compare);

   twalk( btree, print_tree);

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

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

   tdelete( "jwmx", &btree, compare);
   ptr   = tfind( "jwmx", &btree, compare);
   if ( ptr){
      str   = *ptr;
      printf( "%s\n", str);
   } else {
      printf( "jwmx is not found.\n");
   }

   return 0;
}

실행 결과

]$ ./a.out
1 badayak
0 com
1 jwmx
-------------------------------
jwmx is found.
badayak is found.
jwmx is not found.
]$
이 댓글을 비밀 댓글로
error: Content is protected !!