[자료구조] 연결 리스트로 이진 탐색 트리 구현하기

이진 탐색 트리란?

1) 자식 노드를 최대 두 개 가지며

2) 부모보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 배치

3) 따라서 한쪽으로 쏠린 트리가 나온다면 검색 성능은 O(N), 기본적으로는 O(Nlogn)

 

이라는 자료구조로, 효율적인 검색 능력을 가지고 있다. 이를 연결 리스트로 구현해보자!

 

---

 

#include <iostream>
using namespace std;

struct Node
{
    int value;
    Node* left;
    Node* right;
};
Node* node = NULL;

Node* findMin(Node* cur)
{
    while(cur != NULL)
    {
        cur = cur->left;
    }
    return cur;
}

Node* addNode(Node* cur, int a)
{
    if (cur == NULL)
    {
        Node* newNode = new Node();
        newNode->value = a;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    else
    {
        // 값이 작다면, 계속해서 왼쪽으로 내려간다.
        if (a < cur->value)
        {
            cur->left = addNode(cur->left, a);
        }
        // 값이 크다면, 계속해서 오른쪽으로 내려간다.
        else if (a > cur->value)
        {
            cur->right = addNode(cur->right, a);
        }
    }
    // 현재 노드 반환
    return cur;   
}


Node* deleteNode(Node* cur, int d)
{
    if (cur == NULL)
    {
        cout << "지울 노드 " << d << "를 찾을 수 없습니다\n";
        return NULL;
    }
    
    if (d < cur->value)
    {
        cur->left = deleteNode(cur->left, d);
    }

    else if (d > cur->value)
    {
        cur->right = deleteNode(cur->right, d);
    }
    else
    {  
        // 자식 노드가 둘 중 하나 있거나 아예 없는 경우
        if (cur->right == NULL)
        {
            Node* tmp = cur->left;
            delete cur;
            return tmp;
        }
        else if (cur->left == NULL)
        {
            Node* tmp = cur->right;
            delete cur;
            return tmp;
        }
        else   
        {
            // 자식 노드가 모두 있다면, 오른쪽 자식에서 최솟값 노드를 찾아 지울 노드로 끌어올려야 한다.
            Node* tmp = findMin(cur->right);
            cur->value = tmp->value;
            
            // 오른쪽 자식에서 끌어올렸던 최솟값 노드를 지운다.
            cur->right = deleteNode(cur->right, tmp->value);
        }
    }
    // 현재 노드 반환
    return cur; 
}


void printNode(Node* cur)
{
    // 중위순회로 트리 출력
    if (cur != NULL)
    {
        printNode(cur->left);
        cout << cur->value << " ";
        printNode(cur->right);
    }
}

int main() 
{
    node = addNode(node, 5);
    node = addNode(node, 4);
    node = addNode(node, 7);
    node = addNode(node, 1);
    node = addNode(node, 3);
    deleteNode(node, 3);
    printNode(node);

    return 0;
}

 

 

간만에 초심으로 돌아가 클로드 없이 인터넷 컴파일러로 한글자씩 쳤다.

이럴 땐 AI가 오히려 방해되기 때문이다

 

코드 속 메서드로는 최솟값 노드를 찾는 findMin, 노드를 추가하는 addNode, 노드를 지우는 deleteNode, 노드를 중위순회로 출력하는 printNode가 있다.

 

 

 

1) findMin 메서드를 작성한 이유는?

Node* findMin(Node* cur)
{
    while(cur != NULL)
    {
        cur = cur->left;
    }
    return cur;
}

 

 

가령 해당 노드에서 50을 지워야 한다고 치자. 그럼 오른쪽 자식 노드 중 55가 위로 올라와야 한다.

그래야 왼쪽 자식은 부모 노드보다 작은 값, 오른쪽 자식은 큰 값이라는 규칙이 맞기 때문이다

 

// 자식 노드가 모두 있다면, 오른쪽 자식에서 최솟값 노드를 찾아 지울 노드로 끌어올려야 한다.
Node* tmp = findMin(cur->right);
cur->value = tmp->value;
            
// 오른쪽 자식에서 끌어올렸던 최솟값 노드를 지운다.
cur->right = deleteNode(cur->right, tmp->value);

 

따라서 지울 때만 1)현재 노드(=지울 노드)의 오른쪽 자식 주소를 전달하고

2) 지울 노드의 값을 그 최솟값으로 교체한 뒤

3) 해당 최솟값 노드를 지우기 위해 메서드를 재귀로 돌렸다

 

재귀로 돌려진다면 말단 최솟값 노드는 여기에 걸리게 되는데,

if (cur->right == NULL)
{
    Node* tmp = cur->left;
    delete cur;
    return tmp;
 }
else if (cur->left == NULL)
{
    Node* tmp = cur->right;
    delete cur;
    return tmp;
}

 

어차피 말단 최솟값 노드는 자식이 없기에 cur->left와 cur->right이 모두 NULL로 반환되고, 노드를 지운 뒤 NULL을 반환하게 된다.

 

 

2) 한쪽으로 쏠린 트리의 검색 결과가 O(N)이 되는 이유는?

Node* addNode(Node* cur, int a)
{
    else
    {
        // 값이 작다면, 계속해서 왼쪽으로 내려간다.
        if (a < cur->value)
        {
            cur->left = addNode(cur->left, a);
        }
        // 값이 크다면, 계속해서 오른쪽으로 내려간다.
        else if (a > cur->value)
        {
            cur->right = addNode(cur->right, a);
        }
    }
}

Node* deleteNode(Node* cur, int d)
{
    if (d < cur->value)
    {
        cur->left = deleteNode(cur->left, d);
    }

    else if (d > cur->value)
    {
        cur->right = deleteNode(cur->right, d);
    }
}

(설명을 위해 메서드 내용을 일부 생략)

노드 추가 메서드와 삭제 메서드가 재귀적으로 작동되기 때문이다. 쏠릴수록 그만큼 호출하는 숫자가 늘어나게 된다.

 

따라서 쏠린 트리면 O(N)이니까, 이럴 때는 배열이 낫지 않나? 인덱스로 접근하면 O(1)이니까? 하는 생각이 떠오를 수 있다. 하지만 트리는 추가와 삭제가 용이한 자료구조임을 잊지 말아야 한다

 

이를 보완하는 자료구조로는 레드 블랙 트리와 AVL 트리가 있다.

그럼 다음 시간에 구현을 해보도록 해요!