자료구조 이진 탐색 트리(Binary Search Tree)

이전 시간에 트리에 대해 공부했습니다. (참고 : 자료구조 트리)

이번 시간에는 이진 탐색 트리에 대해 공부해보겠습니다.

♪ 이진 탐색 트리(Binary Search Tree) : 노드기반(Node-Based) 이진 트리 자료구조입니다.

♪ 특징(Properties) : 

☞ 좌측 하위 트리(Left Subtree)의 노드들은 상위 노드보다 작거나 같은 값입니다.

☞ 우측 하위 트리(Right Subtree)의 노드들은 상위 노드보다 큰 값입니다.

☞ 좌측 및 우측 하위트리 역시 이진 탐색 트리입니다. (하위트리의 하위트리들도 모두 위 특징에 해당합니다)

♪ 탐색(Search) : 

☞ 탐색의 시작은 루트 노드(Root Node)에서 시작합니다. 만약 탐색하려는 값이 루트 노드의 값이라면 루트 노드의 값을 반환합니다.

☞ 만약 탐색하려는 값이 루트 노드의 값보다 작다면 좌측 하위 트리로 이동해서 탐색을 반복합니다.

☞ 만약 탐색하려는 값이 루트 노드의 값보다 크다면 우측 하위 트리로 이동해서 탐색을 반복합니다.

# 탐색 - 소스코드(C/C++)

struct node* search(struct node* root, int key) // 키 값 : 탐색하려는 값

{

if (root == NULL || root->key == key) // 루트 노드가 없거나 루트 노드의 값이 키 값인 경우

return root; // 루트 노드 반환

    

if (root->key < key) // 키 값이 루트 노드의 값보다 크다면

return search(root->right, key); // 우측 하위 트리 탐색

 

// 키 값이 더 작다면

return search(root->left, key); // 좌측 하위 트리 탐색

}

♪ 삽입(Insertion) : 새로운 노드는 항상 잎(Leaf) 노드에서 발생합니다.

☞ 루트 노드에서 탐색을 시작합니다. 만약 루트 노드가 없다면 노드를 삽입합니다.

☞ 잎(Leaf) 노드를 만날 때 까지 탐색을 시작합니다.

☞ 잎(Leaf) 노드를 만났다면 새로운 노드를 삽입합니다.(새 노드 값이 작다면 좌측, 크다면 우측)

# 삽입 - 소스코드(C/C++)

struct node *newNode(int item) // 새로운 노드 생성 함수

{

    struct node *temp =  (struct node *)malloc(sizeof(struct node)); // 새로운 노드를 동적할당

    temp->key = item; // 키 값을 설정

    temp->left = temp->right = NULL; // 좌측 및 우측 노드 null로 초기화

    return temp;

}

  

struct node* insert(struct node* node, int key) // 삽입 함수; node는 root노드, key는 삽입하려는 값

{

    if (node == NULL) return newNode(key); // 루트 노드가 없다면 바로 삽입

 

    if (key < node->key) // 새 노드가 루트노드 값보다 작다면

        node->left  = insert(node->left, key); // 좌측 서브트리로 이동해서 반복

    else if (key > node->key) // 새 노드가 루트노드 값보다 크다면

        node->right = insert(node->right, key); // 우측 서브트리로 이동해서 반복

 

    return node;

}

♪ 삭제(Delete) :  설명은 소스코드 주석으로 대체합니다.

# 삭제 - 소스코드(C/C++)

struct node * minValueNode(struct node* node) // 가장 작은 노드 반환 함수

{

    struct node* current = node; // 루트 노드 복사

 

    while (current->left != NULL) // 좌측 서브트리가 없을 때 까지 반복

        current = current->left;

 

    return current; 

}

 

struct node* deleteNode(struct node* root, int key) // 삭제 함수

{

    if (root == NULL) return root; // 루트 노드 null이라면 루트 노드 반환

 

    if (key < root->key) // 삭제하려는 노드의 값이 루트노드의 값보다 작다면

        root->left = deleteNode(root->left, key); // 좌측 서브트리로 이동해서 반복

 

    else if (key > root->key) // 크다면

        root->right = deleteNode(root->right, key); // 우측 서브트리로 이동해서 반복

    else // 삭제하려는 노드가 루트 노드

    {

        if (root->left == NULL) // 좌측 서브트리가 없는 경우

        {

            struct node *temp = root->right; // 우측 서브트리 복사

            free(root); // 루트 노드 삭제

            return temp; // 우측 서브트리 반환

        }

        else if (root->right == NULL) // 우측 서브트리가 없는 경우

        {

            struct node *temp = root->left; // 좌측 서브트리 복사

            free(root); // 루트 노드 삭제

            return temp; // 좌측 서브트리 반환

        }

 

        // 좌, 우측 서브트리 모두 있을 경우

        struct node* temp = minValueNode(root->right); // 우측 서브트리 중 가장 작은 값 복사

 

        root->key = temp->key; // 복사 한 값을 루트 노드에 복사

 

        root->right = deleteNode(root->right, temp->key); // 루트의 우측 서브트리 이동해서 반복

    }

    return root;

}

정보가 유익하셨다면 아래 공감버튼 눌러주시면 감사하겠습니다.

질문사항은 댓글로 달아주시면 성의껏 답변해드리겠습니다.