C 이진탐색트리(Binary search tree) 구현

2021. 9. 9. 18:37

※ 이 글은 코드 위주이니 설명은 아래 링크로 확인 !

C 트리(Tree) 설명

트리 - 비선형 자료구조의 일종이다. - 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다. ※ 사용 예로 컴퓨터의 디렉터리 구조를 들 수 있다. 용어 정리 1. 노드(Node) : 트리의 구성요소

srdeveloper.tistory.com

이진 탐색 트리에 사용할 구조체

typedef struct Node
{
    int data;
    struct Node* Left, * Right;
}Node;

※ 2개의 자식 노드를 가질것이므로 왼쪽, 오른쪽 참조 변수를 가진다.

데이터 삽입(Insert)

Node* Insert(Node* node, int data)
{
    if(node == NULL)
    {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->Left = NULL;
        newNode->Right = NULL;
        
        return newNode;
    }
    else
    {
        if(node->data > data)
        {
            node->Left = Insert(node->Left, data);
        }
        else if(node->data < data)
        {
            node->Right = Insert(node->Right, data);
        }
        else
        {
        	//중복 된 데이터이므로 추가하지 않는다.
        }
        
        return node;
    }
}

※ 간결한 코드를 위해 재귀함수로 작성했다. (밑에 나올 수정, 탐색, 삭제, 순회 또한 재귀로 구성한다.)

※ 인수로 받은 데이터와 노드가 가진 키값의 대소관계에 따라 재귀 함수를 호출해준다.

데이터 수정(Modify)

void Modify(Node* node, int data, int newData)
{
    if(node == NULL) return;
    
    if(node->data == data)
    {
        node->data = newData;
    }
    else
    {
        if(node->data > data)
        {
            Modify(node->Left, data, newData);
        }
        else
        {
            Modify(node->Right, data, newData);
        }
    }
}

※ 더 이상 newData와 같은 키값을 가진 노드가 없거나, 같은 키값을 가진 노드가 나올때까지 재귀함수를 호출해서 만약 존재하면 데이터를 변경한다.

※ 수정할 때 이진 탐색 트리의 규칙에 위배되는 값이 들어가도 수정되는 코드는 따로 넣지 않았다. (기능의 본질에만 중점을 두고 작성되었다.)

데이터 탐색(Search)

Node* Search(Node* node, int data)
{
    if(node == NULL) return NULL;
    
    if(node->data == data)
    {
        return node;
    }
    else
    {
        if(node->data > data)
        {
            return Search(node->Left, data);
        }
        else
        {
            return Search(node->Right, data);
        }
    }
}

※ 더 이상 data와 같은 키값을 가진 노드가 없으면 NULL, 같은 키값을 가진 노드가 나올때까지 재귀함수를 호출해서 만약 노드가 존재하면 찾은 노드를 반환한다.

데이터 삭제(Delete)

Node* FindMinNode(Node* node, Node** minNode)
{
    if(node->Left == NULL)
    {
        *minNode = node;
        node = node->Right;
        return node;
    }
    else
    {
        node->Left = FindMinNode(node->Left, minNode);
        return node;
    }
}

Node* Delete(Node* node, int data)
{
    if(node == NULL) return NULL;
    
    if(node->data == data)
    {
        Node* deleteNode = node;
        if(node->Left == NULL && node->Right == NULL)
        {
            node = NULL;
        }
        else if(node->Left != NULL && node->Right == NULL)
        {
            node = node->Left;
        }
        else if(node->Left == NULL && node->Right != NULL)
        {
            node = node->Right;
        }
        else
        {
            Node* minNode = NULL;
            node->Right = FindMinNode(node->Right, &minNode);
            minNode->Left = deleteNode->Left;
            minNode->Right = deleteNode->Right;
            node = minNode;
        }
        
        free(deleteNode);
        return node;
    }
    else
    {
        if(node->data > data)
        {
            node->Left = Delete(node->Left, data);
        }
        else
        {
            node->Right = Delete(node->Right, data);
        }
        
        return node;
    }
}

※ 이진탐색트리에서의 삭제는 다른 자료구조와는 다르게 다소 복잡한 형태를 가지고 있다.

1. 삭제할 키 값을 가지고 있는 노드를 재귀함수로 탐색한다.

2. 노드를 찾게되면 조건을 다음과 같이 나눈다.

2-1) 찾은 노드에서 양쪽의 자식이 없을 때 : 찾은 노드만 삭제하면 된다. (반환값 NULL)

2-2) 왼쪽 자식 노드만 있을 때 : 찾은 노드를 삭제하고 왼쪽 노드를 반환한다.

2-3) 오른쪽 자식 노드만 있을 때 : 찾은 노드를 삭제하고 오른쪽 노드를 반환한다.

2-4) 양쪽 자식 노드가 전부 존재할 때 : 왼쪽 자식 노드 중 가장 큰 키값을 가진 노드를 찾거나, 오른쪽 자식 노드 중 가장 작은 키값을 가진 노드를 찾아서 키값이 일치한 노드의 자리에 넣어주고 기존의 노드는 삭제한다. (이렇게 찾는 이유는 이진 탐색 트리의 규칙 때문에 그렇다.)

※ 위의 코드를 기준으로는 오른쪽 자식 노드에서 가장 작은 키값을 가진 노드를 탐색하고있다.

※ 즉, 왼쪽 자식이 없는 노드가 가장 작은 키값을 가진 노드가 될것이므로 왼쪽 자식이 없는 노드를 찾을때까지 FindMinNode로 재귀함수를 호출한다.

※ 위 과정중에서 2-4의 방법이 제일 복잡한데, 이유는 FindMinNode 함수로 찾은 노드가 오른쪽 자식 노드를 갖고 있을 수도 있기 때문이다.

※ 즉, FindMinNode로 찾은 노드(이하 minNode)에서 Delete함수에서 인수로 받은 data와 같은 키값을 가지고 있는 노드(이하 rootNode)의 위치로 교체하기전에 minNode의 자식을 minNode의 부모노드와 연결 시키고 rootNode의 위치로 교체되어야 한다.

풀 소스코드는 다음과 같다.

#include <stdio.h>

typedef struct Node
{
    int data;
    struct Node* Left, * Right;
}Node;

Node* Insert(Node* node, int data)
{
    if(node == NULL)
    {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->Left = NULL;
        newNode->Right = NULL;
        
        return newNode;
    }
    else
    {
        if(node->data > data)
        {
            node->Left = Insert(node->Left, data);
        }
        else if(node->data < data)
        {
            node->Right = Insert(node->Right, data);
        }
        else
        {
        	//중복 된 데이터이므로 추가하지 않는다.
        }
        
        return node;
    }
}

void Modify(Node* node, int data, int newData)
{
    if(node == NULL) return;
    
    if(node->data == data)
    {
        node->data = newData;
    }
    else
    {
        if(node->data > data)
        {
            Modify(node->Left, data, newData);
        }
        else
        {
            Modify(node->Right, data, newData);
        }
    }
}

Node* Search(Node* node, int data)
{
    if(node == NULL) return NULL;
    
    if(node->data == data)
    {
        return node;
    }
    else
    {
        if(node->data > data)
        {
            return Search(node->Left, data);
        }
        else
        {
            return Search(node->Right, data);
        }
    }
}

Node* FindMinNode(Node* node, Node** minNode)
{
    if(node->Left == NULL)
    {
        *minNode = node;
        node = node->Right;
        return node;
    }
    else
    {
        node->Left = FindMinNode(node->Left, minNode);
        return node;
    }
}

Node* Delete(Node* node, int data)
{
    if(node == NULL) return NULL;
    
    if(node->data == data)
    {
        Node* deleteNode = node;
        if(node->Left == NULL && node->Right == NULL)
        {
            node = NULL;
        }
        else if(node->Left != NULL && node->Right == NULL)
        {
            node = node->Left;
        }
        else if(node->Left == NULL && node->Right != NULL)
        {
            node = node->Right;
        }
        else
        {
            Node* minNode = NULL;
            node->Right = FindMinNode(node->Right, &minNode);
            minNode->Left = deleteNode->Left;
            minNode->Right = deleteNode->Right;
            node = minNode;
        }
        
        free(deleteNode);
        return node;
    }
    else
    {
        if(node->data > data)
        {
            node->Left = Delete(node->Left, data);
        }
        else
        {
            node->Right = Delete(node->Right, data);
        }
        
        return node;
    }
}

void ShowInOrder(Node* node)
{
    if (node == NULL) return;
    
    ShowInOrder(node->Left);
    printf("%d ", node->data);
    ShowInOrder(node->Right);
}

void main()
{
	Node* root = NULL;
    
    //INSERT
    root = Insert(root, 20);
    root = Insert(root, 10);
    root = Insert(root, 32);
    root = Insert(root, 4);
    root = Insert(root, 13);
    root = Insert(root, 25);
    root = Insert(root, 55);
    //               내부 구조
    //                  20
    //          10              32
    //      4       13      25      55

    ShowInOrder(root);
    //결과 : 4 10 13 20 25 32 55
	
    //MODIFY
    Modify(root, 10, 12);
    ShowInOrder(root);
    //결과 : 4 12 13 20 25 32 55
	
    //SEARCH
    printf("%d", Search(root, 12)->data);
    //결과 : 12
	
    //DELETE
    root = Delete(root, 32);
    //               내부 구조
    //                  20
    //          10              55
    //      4       13      25      

    ShowInOrder(root);
    //결과 : 4 12 13 20 25 55
}

※ 중위순회함수는 트리의 이해를 돕기 위해 잠시 넣은 함수이다.

※ 내부 구조 주석에서 보여지는 트리 데이터는 게시물 상단의 링크에서 사용한 트리를 바탕으로 세팅했다.

'Stack > Data struct' 카테고리의 다른 글

C AVL 트리(AVL Tree) 설명 (0)	2021.09.10
C 트리 순회(Tree traversal) 구현 (0)	2021.09.10
C 트리(Tree) 설명 (0)	2021.09.09
C 큐(Queue) 구현 (0)	2021.09.09
C 스택(Stack) 구현 (0)	2021.09.05

서리 개인 개발 블로그