[C언어 알고리즘] 3.4.3 이진 탐색 트리 구현

[C언어 알고리즘] 3.4.3 이진 탐색 트리 구현

---

 이제 이진 탐색 트리를 구현합시다. 이진 탐색 트리는 자료를 보관하는 컬렉션 중에 탐색 효율성을 높인 자료구조입니다. 여기에서는 도서를 보관하는 이진 탐색 트리를 구현하기로 할게요.

 

 먼저 노드를 정의합시다. 이진 탐색 트리의 노드는 데이터와 왼쪽 자식 노드의 위치, 오른쪽 자식 노드의 위치로 구성합니다. 이 책에서는 삭제 편의성을 위해 부모 노드의 위치도 포함할게요. 그리고 동적으로 노드를 생성하는 함수를 제공합시다.

typedef struct _Node Node;

struct _Node

{

    Book *book;

    Node *lch;

    Node *rch;

    Node *pa;

};

Node *New_Node(Book *data);

 

 이진 탐색 트리에는 root 노드의 위치 정보와 보관한 데이터의 개수를 멤버로 구성할게요.

typedef struct _BinSearchTree BST;

struct _BinSearchTree

{

    Node *root;

    int count;

};

 

 이진 탐색 트리를 동적으로 생성하는 함수와 소멸하는 함수를 제공합시다. 그리고 이진 탐색 트리에 책을 보관하는 함수, 특정 번호의 도서를 제거하는 함수, 특정 번호의 도서를 검색하는 함수와 전체 도서 목록을 보여주는 함수를 제공합시다.

BST *New_BST();

void Delete_BST(BST *bst);

int BST_Insert(BST *bst,Book *book);

int BST_Remove(BST *bst, int num);

Book *BST_Find(BST *bst, int num);

void BST_List(BST *bst);

 

 

 

 동적으로 노드를 생성하는 함수를 구현합시다. 여기에서는 Node 형식 크기의 메모리를 할당받은 후 입력 인자로 받은 도서 정보를 설정하고 나머지 멤버는 0으로 초기화합니다.

Node *New_Node(Book *data)

{

    Node *node = 0;

    node = (Node *)malloc(sizeof(Node));

    node->book = data;

    node->lch = node->rch = node->pa = 0;

    return node;

}

 

 동적으로 이진 탐색 트리를 생성하는 함수를 구현합시다. 생성할 때 root는 비어있는 상태이고 보관하고 있는 도서 개수는 0입니다.

BST *New_BST()

{

    BST *bst = 0;

    bst = (BST *)malloc(sizeof(BST));

    bst->root = 0;

    bst->count = 0;

    return bst;

}

 

 동적으로 생성한 이진 탐색 트리를 소멸하는 함수에서는 후위 순회 운행으로 모든 노드를 제거한 후에 자신을 위한 메모리를 해제합니다.

void BST_PostOrder(Node *sr);

void Delete_BST(BST *bst)

{

    BST_PostOrder(bst->root);

    free(bst);

}

 

 후위 순회 운행은 왼쪽 서브 트리를 먼저 방문한 후에 오른쪽 서브 트리를 방문하고 마지막으로 자신을 방문합니다. 그리고 재귀의 탈출 조건은 입력 인자로 전달받은 노드가 0일 때입니다. 따라서 sr이 참일 때만 작업을 수행하게 구현할 수 있습니다.

void BST_PostOrder(Node *sr)

{

    if(sr)

    {

        BST_PostOrder(sr->lch);

        BST_PostOrder(sr->rch);

        Delete_Book(sr->book);

        free(sr);

    }

}

 

 도서를 보관하는 함수를 구현합시다.

Node *BST_FindSeat(Node *sr,int num);

int BST_Insert(BST *bst,Book *book)

{

    Node *parent = 0;

 먼저 이진 탐색 트리에서 보관할 도서의 부모 노드를 찾습니다. 이 부분은 별도의 함수로 작성합시다.

    parent = BST_FindSeat(bst->root,book->num);

 만약 부모가 존재하면 이진 탐색 트리에 최소 한 권의 책 정보를 보관하고 있는 상태입니다.

    if(parent)

    {

 부모의 도서 번호와 보관할 도서 번호의 차이를 구합니다.

        Node *node = 0;

        int gap = parent->book->num - book->num;

 만약 차이가 없다면 이미 해당 번호의 도서를 보관한 상태입니다.

        if( gap == 0)

        {

            return 0;

        }

 보관할 도서를 인자로 새로운 노드를 생성하고 부모 노드를 설정합니다.

        node = New_Node(book);

        node->pa = parent;

 만약 gap이 0보다 크면 부모의 도서 번호가 클 때이므로 왼쪽에 매답니다.

        if(gap>0)

        {

            parent->lch = node;

        }

 그렇지 않다면 오른쪽에 매답니다.

        else

        {

            parent->rch = node;

        }

    }

 

 만약에 부모를 찾지 못했다면 현재 이진 탐색 트리는 빈 상태입니다. 이 때는 새로운 노드를 생성하여 root로 지정합니다.

    else

    {

        bst->root = New_Node(book);

    }

 추가하였으면 보관한 도서 개수를 1 증가합니다.

    bst->count++;

    return 1;

}

 

 이번에는 특정 노드를 루트로 하는 서브 트리에서 특정 도서 번호의 책을 보관할 부모 노드 혹은 같은 도서 번호의 도서를 보관한 노드를 찾는 함수를 작성합시다.

Node *BST_FindSeat(Node *sr,int num)

{

    int gap = 0;

 만약 sr이 0이면 빈 상태이므로 0을 반환합니다.

    if(sr==0)

    {

        return 0;

    }

 sr에 보관한 도서 번호와 검색할 도서 번호의 차이를 계산합니다.

    gap = sr->book->num - num;

 만약 차이가 없다면 해당 노드를 반환합니다.

    if(gap == 0)

    {

        return sr;

    }

 만약 차이가 0보다 sr에 보관한 도서 번호가 클 때입니다.

    if(gap>0)

    {

 이 때는 sr의 왼쪽 서브 트리가 있는지 확인합니다. 만약 있다면 재귀 함수 호출로 sr의 왼쪽 서브 트리에서 찾은 노드를 반환합니다.

        if(sr->lch)

        {

            return BST_FindSeat(sr->lch,num);

        }

 만약 sr의 왼쪽 서브 트리가 없다면 sr을 반환합니다.

        return sr;

    }

 gap이 0보다 작다면 오른쪽 서브 트리에서 찾습니다. sr의 오른쪽 자식이 있다면 재귀 함수 호출로 sr의 오른쪽 서브 트리에서 찾은 노드를 반환합니다.

    if(sr->rch)

    {

        return BST_FindSeat(sr->rch,num);

    }

 그렇지 않다면 sr을 반환합니다.

    return sr;

}

 

 이번에는 특정 도서 번호의 도서를 보관하는 노드를 삭제하는 함수를 작성합시다.

void BST_Disconnect(BST *bst,Node *node);

int BST_Remove(BST *bst, int num)

{

    Node *node = 0;

 먼저 특정 도서 번호의 도서를 보관한 노드를 검색합니다.

    node = BST_FindSeat(bst->root,num);

 

 만약 검색 결과가 있다면 이진 탐색 트리는 비어있는 상태가 아닙니다.

    if(node)

    {

 이 때 검색한 노드의 도서 번호와 입력 인자로 전달받은 도서 번호가 같은지 확인합니다. BST_FindSeat 함수는 도서를 보관할 때 부모 노드를 찾을 때도 사용하는 함수이기 때문입니다.

        if(node->book->num == num)

        {

 만약 같다면 이진 탐색 트리에서 해당 노드의 연결을 끊습니다. 이 부분은 별도의 함수로 작성합시다.

            BST_Disconnect(bst,node);

 그리고 해당 노드를 메모리에서 소멸하고 보관한 도서 개수를 1 감소합니다.

            free(node);

            bst->count--;

            return 1;

        }

    }

 만약에 검색한 노드가 0이거나 검색한 노드의 도서 번호가 입력한 도서의 번호가 같지 않으면 존재하지 않을 때이므로 삭제를 하지 못했다는 의미로 0을 반환합니다.

    return 0;

}

 

 이번에는 이진 탐색 트리에서 특정 노드의 연결을 끊는 함수를 작성합시다.

Node *BST_Change(Node *node); //왼쪽과 오른쪽에 자식이 있을 때 자신을 대체하는 노드를 찾는 함수

void BST_Disconnect(BST *bst,Node *node)

{

    Node *pa=0;

    Node *ch=0;

 만약 연결을 끊을 노드에 왼쪽 서브 트리와 오른쪽 서브 트리가 있다면 자신을 대체할 노드를 찾은 후에 이를 제거합니다. 따라서 여기에서는 먼저 대체하기만 하고 if 조거문 밑에 제거합니다.

    if(node->lch && node->rch)

    {

        node = BST_Change(node);

    }

 

 이후의 코드는 연결을 끊는 부분입니다. 앞의 if문에서 node에 왼쪽 서브 트리와 오른쪽 서브 트리가 있을 때는 대체하는 노드를 찾는 작업을 수행하였으므로 현재의 node는 자식이 없거나 한 쪽에만 있을 때입니다.

 

 먼저 현재 노드의 부모를 확인합니다.

    pa = node->pa;

 그리고 자식을 확인합니다. 자식은 node의 왼쪽 노드이거나 오른쪽 노드입니다. C언어의 ||연산자의 좌항이 참이면 우항은 수행하지 않습니다. 이 특징을 이용하면 다음처럼 표현할 수 있습니다.

    (ch = node->lch)||(ch = node->rch);

 만약 부모가 있다면 자식의 부모를 변경합니다.

    if(pa)

    {

        ch->pa = pa;

   }

 부모가 없다면 현재 지울려고 하는 node가 root입니다. 따라서 현재 노드를 이진 탐색 트리에서 제거하면 자식이 root가 되어야 합니다.

    else

    {

        bst->root = ch;

    }

 만약 자식이 있다면 부모 노드에 삭제할 노드가 매달린 부분에 자식을 설정합니다.

    if(ch)

    {

 삭제할 노드가 부모 노드의 왼쪽 노드일 때는 부모 노드의 왼쪽에 자식을 설정합니다.

        if(pa->lch == node)

        {

            pa->lch = ch;

        }

 그렇지 않다면 부모 노드의 오른쪽에 자식을 설정합니다.

        else

        {

            pa->rch = ch;

        }

    }

}

 

 이진 탐색 트리에서 연결을 끊을 노드가 왼쪽 자식과 오른쪽 자식이 있을 때 대체하는 함수를 작성합시다.

Node *BST_Change(Node *node)

{

 입력 인자로 받은 노드를 임시 변수에 설정합니다.

    Node *temp = node;

 대체할 노드는 왼쪽 서브 트리나 오른쪽 서브 트리에서 찾을 수 있는데 여기에서는 오른쪽 서브 트리에서 찾을게요. 오른쪽 서브 트리에서 찾을 때는 왼쪽 서브 트리로 계속 이동합니다. 이렇게 찾은 노드는 오른쪽 서브 트리에서 제일 작은 값을 보관한 노드입니다. 따라서 연결을 끊을 노드보다 크면서 연결을 끊을 노드의 왼쪽 서브 트리의 어느 노드보다 큰 값을 갖고 오른쪽 서브 트리의 어느 노드보다 작은 값을 갖습니다.

    while(temp->rch)

    {

        temp = temp->lch;

    }

 그리고 대체할 노드의 데이터를 원래 연결을 끊을 노드의 데이터로 설정합니다. 그리고 대체할 노드를 반환합니다. 연결을 끊는 함수에서는 반환받은 대체할 노드의 연결을 끊습니다.

    node->book = temp->book;

    return temp;

}

 이제 이진 탐색 트리에서 특정 번호의 도서를 찾는 함수를 작성합시다.

Book *BST_Find(BST *bst, int num)

{

    Node *node = 0;

 먼저 이진 탐색 트리에서 검색합니다.

    node = BST_FindSeat(bst->root,num);

 검색 결과가 있다면 이진 탐색 트리는 빈 상태가 아닙니다.

    if(node)

    {

 이 때 검색한 노드의 도서 번호가 입력 인자로 받은 도서 번호와 일치하는지 확인합니다. 일치하면 해당 노드의 도서 정보를 반환합니다.

        if(node->book->num == num)

        {

            return node->book;

        }

    }

 검색한 도의 도서 번호가 입력 인자로 받은 도서 번호와 일치하지 않거나 검색 결과가 없다면 검색을 요청한 번호의 도서는 없습니다. 따라서 0을 반환합니다.

    return 0;

}

 

 이제 전체 정보를 출력하는 함수를 작성합니다.

void BST_Inorder(Node *sr);

void BST_List(BST *bst)

{

 먼저 보관 개수를 출력합시다.

    printf("보관 개수:%d\n",bst->count);

 중위 순회 운행으로 출력하면 도서 번호 순으로 출력할 수 있습니다.

    BST_Inorder(bst->root);

}

void BST_Inorder(Node *sr)

{

    if(sr)

    {

        BST_Inorder(sr->lch);

        Book_View(sr->book);

        BST_Inorder(sr->rch);

    }

}