본문 바로가기
알고리즘

자료구조, Binary Search Tree

팽투더이 2023. 4. 2. 23:17
728x90

자료구조, Binary Search Tree

Binary Search Tree

📌 BST란?

트리 자료구조의 한 종류

부모노드보다 작은 값은 왼쪽 자식 노드에, 부모노드보다 큰 값은 오른쪽 자식 노드에 저장하는 방식으로 데이터 저장

 

📌 장점

  • 탐색, 삽입, 삭제 연산 시 시간복잡도 O(log n)
  • 최대 2개의 자식 노드를 가지므로 이진 탐색 트리에서 데이터를 탐색할 때 절반 이하의 노드를 탐색한다.
  • 데이터가 정렬된 상태를 유지하므로 중위순회(왼쪽서브노드 → 루트 → 오른쪽서브노드)하면 오름차순으로 정렬된 값을 얻을 수 있다.

BST 최악

📌  단점

  • 이상적인 BST 모양이 아닐 경우(균형잡힌 이진 탐색트리) 경우, 시간 복잡도가 O(n)에 수렴한다.

이러한 최악의 경우를 피하기 위해,

데이터를 삽입할 때마다 트리의 균형을 잡기 위해 균형 조절 알고리즘(AVL, Red-Black 등)을 사용해 이를 개선할 수 있다.

✏️ 노드 생성

// typeof 자료형에 새로운 이름을 부여하는 키워드
// sturct node를 'Node' 라는 새로운 자료형으로 정의 함
typedef struct node
{
    int data;
    struct node *left; // 왼쪽 서브트리를 가리키는 포인터
    struct node *right; // 오른쪽 서브트리를 가리키는 포인터
} Node;

// 새로운 노드 생성 함수
Node* createNode(int data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

왼쪽 서브트리를 가르키는 포인터부 left, 오른쪽 서브트리를 가르키는 포인터부 right, 그리고 int형 데이터를 가지는 노드 구조체(붕어빵틀)를 만든다.

typeof를 이용해 struct node를 Node라는 별칭으로 간단히 사용할 수 있다.

 

새로운 노드를 생성하는 함수를 만든다.

동적메모리에 integer(4byte) + pointer(4byte)*2 = 12byte를 할당해 노드를 생성한다.

생성된 노드는 자식노드가 있을지 없을지 모르므로 초기값은 NULL을 할당해 준다.

 

✏️ BST에 노드를 삽입하는 함수

 

BST 노드 삽입

// BST에 노드 삽입하는 함수
Node *insert(Node *root, int data)
{
    // BST가 비어있으면 삽입하는 노드가 root 노드가 됨.
    if (root == NULL)
    {
        root = (Node*)malloc(sizeof(Node));
        root->data = data;
        root->left = NULL;
        root->right = NULL;
        return root;
    }
    // BST가 비어 있지 않다면, 크기를 비교해 재귀적으로 삽입
    // 루트노드보다 작다면, 왼쪽 서브트리쪽으로 노드 연결됨.
    if (data < root->data)
    {
        root->left = insert(root->left, data);
    }
    // 루트노드보다 크다면, 오른쪽 서브트리쪽으로 노드가 연결됨.
    else{
        root->right = insert(root->right, data);
    }
    return root; // root 노드가 반환되면 BST 전체 구조가 반환됨.
}

삽입은 간단하다.

그냥 root노드보다 작으면 왼쪽 서브노드와 이어지도록 재귀적으로 타고타고 들어간다.

root노드보다 크면 오른쪽 서브노드와 이어지도록 재귀적으로 타고타고 들어간다.

✏️ BST에서 노드를 삭제하는 함수

    // 삭제하려는 데이터가 BST에 없는 경우, NULL값 반환
    if (root == NULL)
    {
        return NULL;
    }
    // 삭제하려는 데이터가 root보다 작으면
    // 왼쪽 서브트리가 root값이 되면서 재귀적 탐색
    if (data < root->data)
    {
        root->left = delete(root->left, data);
    }
    // 삭제하려는 데이터가 root보다 크면
    // 오른쪽 서브트리가 root값이 되면서 재귀적 탐색
    else if (data > root->data)
    {
        root->right = delete(root->right, data);
    }

일단 삭제하려는 노드를 재귀적으로 탐색해  해당 노드 삭제해준다.

그리고 3가지 케이스로 나뉜다.

 

  • Case1. 삭제 하려는 노드의 자식노드가 없는 경우
  • Case2. 삭제 하려는 노드의 자식노드가 1개인 경우
  • Case3. 삭제 하려는 노드의 자식노드가 2개인 경우

 

✏️ Case1. 삭제 하려는 노드의 자식노드가 없는 경우

        // Case1. 삭제 하려는 데이터의 자식 노드가 없는 경우
        if (root->left == NULL && root->right == NULL)
        {
            free(root); // 삭제하려는 데이터의 메모리 할당을 해제해 그냥 삭제
            return NULL; // NULL값을 리턴해준다.
        }

Case1

삭제 하려는 노드의 자식 노드가 없을 경우에는 그 노드의 메모리 할당을 해제해 삭제해주고 NULL 반환해주면 된다.

BST : 
        1
    3
            4
        6
            7
8
    10
            13
        14

BST after node 1 deletion(Case1) : 
    3
            4
        6
            7
8
    10
            13
        14

 

✏️ Case2. 삭제 하려는 노드의 자식노드가 1개인 경우

        // Case2. 삭제 하려는 데이터의 자식 노드가 1개인 경우
        else if (root->left == NULL)
        {
            Node *temp = root->right; // 삭제하려는 노드의 오른쪽 자식을 가리키는 주소값을 temp에 저장
            free(root); // 삭제하려는 노드의 메모리 할당 해제
            return temp; // 자식노드의 메모리 주소값을 return함으로 써 연결을 변경해준다.
        }
        else if (root->right == NULL)
        {
            Node *temp = root->left; // 삭제하려는 노드의 오른쪽 자식을 가리키는 주소값을 temp에 저장
            free(root); // 삭제하려는 노드의 메모리 할당 해제
            return temp; // 자식노드의 메모리 주소값을 return함으로 써 연결을 변경해준다.
        }

Case2

삭제하려는 노드의 자식이 1개인 경우, 자식노드를 가리키는 포인터값을 temp에 저장해주고 해당 노드를 삭제한다.

그후 temp를 반환해주면 조상노드와 자식노드가 연결되어 BST규칙에 어긋나지 않게 노드를 삭제할 수 있다.

BST : 
        1
    3
            4
        6
            7
8
    10
            13
        14

BST after node 1 deletion(Case1) : 
    3
            4
        6
            7
8
    10
            13
        14

BST after node 14 deletion(Case2) : 
    3
            4
        6
            7
8
    10
        13

 

 

✏️ Case3. 삭제 하려는 노드의 자식노드가 2개인 경우

        // Case3. 삭제하려는 데이터의 자식 노드가 2개인 경우
        else
        {
            // 오른쪽 서브트리의 가장 작은 값을 탐색
            Node *min_right = root->right;
            while (min_right->left != NULL)
            {
                min_right = min_right->left;
            }
            // 그 값을 root값으로 설정!
            root->data = min_right->data;
            // 오른쪽 서브트리에서 min_right(가장 작은 값) 삭제
            root->right = delete(root->right, min_right->data);
        }

Case 3

삭제하려는 노드의 자식 노드가 2개인 경우, 조금 복잡하다

왼쪽 서브트리의 가장 큰 값 또는 오른쪽 서브트리의 가장 작은값와 교체해주면 BST 규칙에 어긋나지 않고 최소한의 이동으로 노드를 교체할 수 있다.

해당 코드는 오른쪽 서브트리의 가장 큰값과 루트 노드를 교체한 코드이다.

 

루트의 오른쪽서브트리의 왼쪽서브트리가 NULL값이 아닐 때 까지(끝까지) 탐색한다.

탐색이 끝나면, 그 값이 오른쪽 서브트리 전체의 최솟값(min_right)이 될 것이다.

 

그럼 그 값을 root로 설정해주고

오른쪽 서브트르에서 min_right 데이터를 삭제해주면 된다.

 

BST : 
        1
    3
            4
        6
            7
8
    10
            13
        14

BST after node 1 deletion(Case1) : 
    3
            4
        6
            7
8
    10
            13
        14

BST after node 14 deletion(Case2) : 
    3
            4
        6
            7
8
    10
        13

BST after node 8 deletion(Case3) : 
    3
            4
        6
            7
10
    13

기존 루트 8이 오른쪽 서브노드의 가장 작은값 10와 교체된 걸 확인할 수 있다.

 

📄 BST.c

#include <stdio.h>
#include <stdlib.h>

// typeof 자료형에 새로운 이름을 부여하는 키워드
// sturct node를 'Node' 라는 새로운 자료형으로 정의 함 
typedef struct node
{
    int data;
    struct node *left; // 왼쪽 서브트리를 가리키는 포인터
    struct node *right; // 오른쪽 서브트리를 가리키는 포인터
} Node;

// 새로운 노드 생성 함수
Node* createNode(int data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// BST에 노드 삽입하는 함수
Node *insert(Node *root, int data)
{
    // BST가 비어있으면 삽입하는 노드가 root 노드가 됨.
    if (root == NULL)
    {
        root = (Node*)malloc(sizeof(Node));
        root->data = data;
        root->left = NULL;
        root->right = NULL;
        return root;
    }
    // BST가 비어 있지 않다면, 크기를 비교해 재귀적으로 삽입
    // 루트노드보다 작다면, 왼쪽 서브트리쪽으로 노드 연결됨.
    if (data < root->data)
    {
        root->left = insert(root->left, data);
    }
    // 루트노드보다 크다면, 오른쪽 서브트리쪽으로 노드가 연결됨.
    else{
        root->right = insert(root->right, data);
    }
    return root; // root 노드가 반환되면 BST 전체 구조가 반환됨.
}

// BST에서 노드 삭제하는 함수
Node *delete(Node *root, int data)
{
    // 삭제하려는 데이터가 BST에 없는 경우, NULL값 반환
    if (root == NULL)
    {
        return NULL;
    }
    // 삭제하려는 데이터가 root보다 작으면 
    // 왼쪽 서브트리가 root값이 되면서 재귀적 탐색
    if (data < root->data)
    {
        root->left = delete(root->left, data);
    }
    // 삭제하려는 데이터가 root보다 크면 
    // 오른쪽 서브트리가 root값이 되면서 재귀적 탐색
    else if (data > root->data)
    {
        root->right = delete(root->right, data);
    }
    else {
        // Case1. 삭제 하려는 데이터의 자식 노드가 없는 경우
        if (root->left == NULL && root->right == NULL)
        {
            free(root); // 삭제하려는 데이터의 메모리 할당을 해제해 그냥 삭제
            return NULL; // NULL값을 리턴해준다.
        }
        // Case2. 삭제 하려는 데이터의 자식 노드가 1개인 경우
        else if (root->left == NULL)
        {
            Node *temp = root->right; // 삭제하려는 노드의 오른쪽 자식을 가리키는 주소값을 temp에 저장
            free(root); // 삭제하려는 노드의 메모리 할당 해제
            return temp; // 자식노드의 메모리 주소값을 return함으로 써 연결을 변경해준다.
        }
        else if (root->right == NULL)
        {
            Node *temp = root->left; // 삭제하려는 노드의 오른쪽 자식을 가리키는 주소값을 temp에 저장
            free(root); // 삭제하려는 노드의 메모리 할당 해제
            return temp; // 자식노드의 메모리 주소값을 return함으로 써 연결을 변경해준다.
        }
        // Case3. 삭제하려는 데이터의 자식 노드가 2개인 경우
        else
        {
            // 오른쪽 서브트리의 가장 작은 값을 탐색
            Node *min_right = root->right;
            while (min_right->left != NULL)
            {
                min_right = min_right->left;
            }
            // 그 값을 root값으로 설정!
            root->data = min_right->data;
            // 오른쪽 서브트리에서 min_right(가장 작은 값) 삭제
            root->right = delete(root->right, min_right->data);
        }
    }
    return root;
}

// BST 를 중위 순회하며 값을 출력하는 함수
void print(Node *node, int level)
{
    if (node == NULL)
    {
        return;
    }
    print(node->left, level + 1);
    for(int i = 0; i < level; i++)
    {
        printf("    ");
    }
    printf("%d\n", node->data);
    print(node->right, level + 1);
}

int main()
{
    Node *root = NULL;

    // BST에 값을 삽입
    root = insert(root, 8);
    root = insert(root, 3);
    root = insert(root, 10);
    root = insert(root, 1);
    root = insert(root, 6);
    root = insert(root, 4);
    root = insert(root, 7);
    root = insert(root, 14);
    root = insert(root, 13);

    // BST 출력
    printf("BST : \n");
    print(root, 0);
    printf("\n");

    // BST에서 5, 15, 18 삭제
    root = delete(root, 1);
    // BST 출력
    printf("BST after node 1 deletion(Case1) : \n");
    print(root, 0);
    printf("\n");
    
    root = delete(root, 14);
    // BST 출력
    printf("BST after node 14 deletion(Case2) : \n");
    print(root, 0);
    printf("\n");
    
    root = delete(root, 8);
    // BST 출력
    printf("BST after node 8 deletion(Case3) : \n");
    print(root, 0);
    printf("\n");
}
저작자표시

'알고리즘' 카테고리의 다른 글

자료구조, rbtree insert  (0) 2023.04.06
자료구조, AVL Left-Rotate & Right-Rotate 구현  (0) 2023.04.04
자료 구조, Linked List  (0) 2023.04.02
재귀함수, 하노이의 탑  (0) 2023.03.07
DFS 관련 연산 문제  (0) 2023.03.07

'알고리즘' Related Articles

티스토리툴바