이진 탐색 트리(Binary Search Tree)

오늘은 이진 트리에 대해서 작성해보겠습니다.

이진 트리는 일정한 규칙을 유지한 체 트리의 형태를 갖는 자료구조입니다. 현재 노드를 기준으로 왼쪽은 작은 값 오른쪽엔 큰 값이 배치되는데요! 미리 정렬 되어 있고 메모리 중앙에도 단번에 접근 가능해야 사용할 수 있는 이진 탐색과 달리 메모리가 동적으로 변해도 탐색이 가능한 자료구조입니다.

 

먼저 트리의 용어에 대해 볼까요?

• 노드의 크기: 자신을 포함한 노드가 갖는 자식의 수를 의미합니다.
• 노드의 차수(degree): 하위 (자식의  수)간선의 수를 의미합니다.
• 깊이: 루트 노드에서 해당 노드까지 거쳐야되는 간선의 수를 의미합니다.
• 레벨: 특정 깊이의 노드들의 집합을 의미합니다.
• 트리의 차수: 노드가 갖는 최대 간선의 수를 의미합니다.
• 트리의 높이: 루트 노드에서 가장 깊숙히 있는 깊이를 의미합니다.
• Root Node: 트리에서 최상위 노드를 의미합니다.
• Parent Node: 현재 노드의 상위 노드를 의미합니다.
• Sibling Node: Parent 노드와 같은 레벨의 노드를 의미합니다.
• Child Node: Parent의 자식 노드를 의미합니다.
• Leaf Node: 자식이 없는 최하위 노드를 의미합니다.
• Full Binary Tree(포화이진트리) 모든 레벨에 자식이 가득찬 트리를 의미합니다.
• Complete Binary Tree(완전 이진 트리): Leaf 노드를 제외한 레벨의 모든 노드가 가득찬 트리를 의미합니다. Leaf 노드가 가득찰 수 도 있고, 빌 때는 오른쪽 부터 빈 상태여야합니다. 

기본적인 연산으로 insert, search, remove, destroy 연산이 있습니다. 하나씩 차근차근 살펴보겠습니다.

insert는 tree에 새로운 노드를 추가,
search는 tree에서 해당 데이터가 있는지 탐색,
remove는 해당 데이터가 존재하는 지 탐색해서 제거,
destroy는 사용한 메모리를 해제하는 함수입니다.

이진 트리를 먼저 정의해보죠! 구현의 편의를 위해 데이터는 int 형 데이터 타입만 정의하였습니다.

struct Tree
{
    Tree* pLeft;
    Tree* pRight;
    int data;
};

이진트리기 때문에 구조체는 자식 노드를 저장하는  Tree pointer type의 포인터 변수가 2개 정의합니다. 

struct Tree* allocate(int data)
{
    Tree* pNode = (Tree*)malloc(sizeof(Tree));
    pNode->pLeft = nullptr;
    pNode->pRight = nullptr;
    pNode->data = data;

    return pNode;
}

위의 코드는 Tree의 노드를 동적으로 생성하고 구조체의 멤버 변수를 초기화하는 코드입니다. 노드를 생성하였으면 트리의 적절한 위치에 노드를 추가해야되는데요. 이진 트리에 추가를 할 땐 이진 트리의 규칙이 위배 되지 않도록 추가하는 것이 중요합니다.

void insert(Tree* pTree, Tree* pNewNode)
{
    if (pTree->data > pNewNode->data)
    {
        if (pTree->pLeft)
            insert(pTree->pLeft, pNewNode);
        else
            pTree->pLeft = pNewNode;

    }
    else if (pTree->data < pNewNode->data)
    {
        if (pTree->pRight)
            insert(pTree->pRight, pNewNode);
        else
            pTree->pRight = pNewNode;
    }
}

위의 코드에서 insert 함수는 data(key) 값과 현재 노드를 비교해서 nullptr가 나올 때 까지 탐색을 재귀적으로 진행합니다. 탐색한 Tree node가 nullptr 이라면 leaf 노드라고 간주하구 할당한 노드를 추가합니다. 추가를 했으니 트리의 노드를 순회하면서 key(data)값을 출력해보겠습니다. 이진 트리의 순회 방식엔 크게 3가지가 있습니다.

 

Preorder: 데이터를 순회하자마자 먼저 출력을 하는 방식입니다.

Inorder: Left Node까지만 재귀적으로 탐색을 수행한 후 Right Node를 호출하기 직전에 출력하는 방식입니다. 

Postorder: Left Node와 Right Node를 모두 재귀적으로 탐색을 한 후 출력하는 방식입니다.

void preorder(Tree* pTree)
{
    printf("%d ", pTree->data);

    if (pTree->pLeft)
        preorder(pTree->pLeft);

    if (pTree->pRight)
        preorder(pTree->pRight);
}

void inorder(Tree* pTree)
{
    if (pTree->pLeft)
        inorder(pTree->pLeft);

    printf("%d ", pTree->data);

    if (pTree->pRight)
        inorder(pTree->pRight);
}

void postorder(Tree* pTree)
{
    if (pTree->pLeft)
        postorder(pTree->pLeft);

    if (pTree->pRight)
        postorder(pTree->pRight);

    printf("%d ", pTree->data);
}

다음은 search 코드입니다.

int search(Tree* ptree, int data)
{
    if (ptree->data > data)
    {
        if (ptree->pLeft)
            return search(ptree->pLeft, data);
    }
    else if (ptree->data < data)
    {
        if (ptree->pRight)
            return search(ptree->pRight, data);
    }
    else {
        return data;
    }

    return -1;
}

입력한 data와 key 값을 비교하면서 키 값과 동일한 데이터를 찾은 경우 해당 키 값을 반환합니다. 만약에 key에 해당하는 데이터가 존재하지 않는 경우는 leaf 노드를 만나기 때문에 -1을 return하게 됩니다.

 

다음은 remove에 대해서 이야기해보겠습니다. 이진 탐색트리에서 가장 주의해야될 연산은 insert와 remove 인데요! 새로운 노드가 추가됨으로 해서 이진 트리의 규칙이 위배될 수 있기 때문에 이진 트리의 규칙이 무너지지 않게 뒤처리를 하는 작업이 굉장히 중요합니다. 트리에서 노드를 삭제하는 상황을 가정해보면 마주칠 수 있는 상황은 크게 3가지 입니다.

 

1. 삭제할 노드가 leaf 노드인 경우
2. 삭제할 노드의 자식이 1개만 있는 경우
3. 삭제할 노드의 자식이 2개인 경우

1), 2)인 경우에는 문제가 간단합니다. 1) 삭제할 노드가 leaf 노드라면 단순히 해당 노드를 삭제한 후 부모와 연결된 간선 노드만 nullptr로 처리하면 됩니다. 2) 삭제할 노드의 자식이 1개 있는 경우 라면 삭제할 노드의 자식의 노드를 부모와 연결된 간선 노드애 연결시키기만 하면 됩니다.

 

반면에 3)인 경우는 상황이 조금 복잡합니다! 해당 키 값을 트리에서 삭제하면 삭제된 위치에는 어떤 노드가 대체 되어야 할지 고민해봅시다. Left에 위치한 노드들과 오른쪽에 위치한 노드들의 중간 값이 저장되어야하니 오른쪽 트리의 최소 노드를 부모에 대체시키면 됩니다. 

Tree* findMinNode(Tree* pParent, Tree* pTree)
{
    Tree* pCur = pTree;
    Tree* pLocalParent = pTree;

    while (pCur->pLeft) {
        pParent = pCur;
        pCur = pCur->pLeft;
    }

    if (pCur == pTree) {
        pParent->pRight = nullptr;
    }
    else {
        pParent->pLeft = nullptr;
    }

    return pCur;
}

void remove(Tree* pTree, Tree* pParent, int data)
{
    if (pTree) {
        if (pTree->data > data)
        {
            if (pTree->pLeft)
                remove(pTree->pLeft, pTree, data);
        }
        else if (pTree->data < data)
        {
            if (pTree->pRight)
                remove(pTree->pRight, pTree, data);
        }
        else {
            if (pTree->pLeft == nullptr && pTree->pRight == nullptr) {
                // 현재 노드를 삭제하고 부모가 갖는 left or right에 해당하는 곳엔 nullptr 추가

                if (root == pTree) {
                    root = nullptr;
                }
                else {
                    if (pParent->pLeft == pTree) {
                        pParent->pLeft = nullptr;
                    }
                    else {
                        pParent->pRight = nullptr;
                    }
                }

                free(pTree);
            }
            else if (pTree->pLeft == nullptr || pTree->pRight == nullptr) {
                // 현재 노드를 삭제하고 자식을 부모의 left or right에 해당하는 곳에 추가.
                Tree* pNode = nullptr;
                if (pTree->pLeft) {
                    pNode = pTree->pLeft;
                }
                else {
                    pNode = pTree->pRight;
                }

                if (root == pTree) {
                    root = pNode;
                }
                else {
                    if (pParent->pLeft == pTree) {
                        pParent->pLeft = pNode;
                    }
                    else {
                        pParent->pRight = pNode;
                    }
                }

                free(pTree);
            }
            else if (pTree->pLeft && pTree->pRight) {
                // 1) 오른쪽 트리의 최소 자식을 찾는다.
                Tree* pMinNode = findMinNode(pTree, pTree->pRight);

                if (root == pTree) {
                    root = pMinNode;
                }
                else {
                    // 2) 부모에 단다.
                    if (pParent->pLeft == pTree) {
                        pParent->pLeft = pMinNode;
                    }
                    else {
                        pParent->pRight = pMinNode;
                    }
                }

                pMinNode->pLeft = pTree->pLeft;
                pMinNode->pRight = pTree->pRight;

                // 3) 현재 노드를 삭제한다.
                free(pTree);
            }
        }
    }
}

가장 먼저 삭제할 노드를 탐색해야 되기 때문에 search 코드를 일부 사용합니다. key 값에 대한 data를 찾았다면 삭제를 진행하게 되는데 탐색한 데이터가 1) 삭제할 노드가 leaf 노드인 경우 해당 노드를 삭제하고 부모와 연결된 간선을 nullptr로 초기화 하면 됩니다. Leaf 노드를 탐색한 상황엔 부모 노드에 접근할 방법이 없기 때문에 인자에 parent 노드의 주소도 함께 전달해야합니다. 만약에 현재 탐색한 노드가 pParent의 Left와 같다면 parent의 왼쪽 자식에서 함수가 불린 것이고 그렇지 않다면 오른쪽 자식에서 함수가 불린 것입니다. 어디서 불렸는지를 확인하여 부모의 간선도 nullptr로 초기화를 진행합니다. 

 

만약에 탐색한 데이터가 2) 삭제할 노드의 자식이 1개만 있는 경우 타겟 노드를 삭제하기 전에 자식의 노드를 다른 포인터 변수에 저장을 시킵니다. 그런 다음 parent의 left 혹은 right 중 어디서 불렸는지를 확인하여 마찬가지로 nullptr로 초기화를 합니다.

 

만약에 탐색한 데이터가 3) 삭제할 노드의 자식이 2개가 있는 경우, 오른쪽 자식에서 최소 노드를 탐색합니다. findMinNode란 함수는 현재의 노드를 기점으로 왼쪽 방향의 최소 노드를 찾는 함수입니다. minNode로 탐색된 노드의 부모 노드를 반드시 nullptr로 초기화 해야합니다. 그렇지 않으면 leaf 노드가 다시 target 노드로 링크되어 문제가 발생 할 수 있습니다. minNode를 찾아 삭제될 node될 자리에 그대로 대체시킵니다,

 

다음은 동적할당한 node를 de-allocation하는 함수입니다.

void destroy(Tree* pTree)
{
    if (pTree->pLeft)
        postorder(pTree->pLeft);

    if (pTree->pRight)
        postorder(pTree->pRight);

    free(pTree);
}

탐색을 먼저 수행한 이후에, leaf 노드 부터 de-allocation을 진행하면 메모리를 해제시킬 수 있습니다.

 

다음은 전체코드입니다.

#include <iostream>
using namespace std;

struct Tree
{
    Tree* pLeft;
    Tree* pRight;
    int data;
};

Tree* root;

struct Tree* allocate(int data)
{
    Tree* pNode = (Tree*)malloc(sizeof(Tree));
    pNode->pLeft = nullptr;
    pNode->pRight = nullptr;
    pNode->data = data;

    return pNode;
}

void insert(Tree* pTree, Tree* pNewNode)
{
    if (pTree->data > pNewNode->data)
    {
        if (pTree->pLeft)
            insert(pTree->pLeft, pNewNode);
        else
            pTree->pLeft = pNewNode;

    }
    else if (pTree->data < pNewNode->data)
    {
        if (pTree->pRight)
            insert(pTree->pRight, pNewNode);
        else
            pTree->pRight = pNewNode;
    }
}

int search(Tree* ptree, int data)
{
    if (ptree->data > data)
    {
        if (ptree->pLeft)
            return search(ptree->pLeft, data);
    }
    else if (ptree->data < data)
    {
        if (ptree->pRight)
            return search(ptree->pRight, data);
    }
    else {
        return data;
    }

    return -1;
}

void preorder(Tree* ptree)
{
    printf("%d ", ptree->data);

    if (ptree->pLeft)
        preorder(ptree->pLeft);

    if (ptree->pRight)
        preorder(ptree->pRight);
}

void inorder(Tree* ptree)
{
    if (ptree->pLeft)
        inorder(ptree->pLeft);

    printf("%d ", ptree->data);

    if (ptree->pRight)
        inorder(ptree->pRight);
}

void postorder(Tree* ptree)
{
    if (ptree->pLeft)
        postorder(ptree->pLeft);

    if (ptree->pRight)
        postorder(ptree->pRight);

    printf("%d ", ptree->data);
}

Tree* findMinNode(Tree* pParent, Tree* pTree)
{
    Tree* pCur = pTree;
    Tree* pLocalParent = pTree;

    while (pCur->pLeft) {
        pParent = pCur;
        pCur = pCur->pLeft;
    }

    if (pCur == pTree) {
        pParent->pRight = nullptr;
    }
    else {
        pParent->pLeft = nullptr;
    }

    return pCur;
}

void remove(Tree* pTree, Tree* pParent, int data)
{
    if (pTree) {
        if (pTree->data > data)
        {
            if (pTree->pLeft)
                remove(pTree->pLeft, pTree, data);
        }
        else if (pTree->data < data)
        {
            if (pTree->pRight)
                remove(pTree->pRight, pTree, data);
        }
        else {
            if (pTree->pLeft == nullptr && pTree->pRight == nullptr) {
                // 현재 노드를 삭제하고 부모가 갖는 left or right에 해당하는 곳엔 nullptr 추가

                if (root == pTree) {
                    root = nullptr;
                }
                else {
                    if (pParent->pLeft == pTree) {
                        pParent->pLeft = nullptr;
                    }
                    else {
                        pParent->pRight = nullptr;
                    }
                }

                free(pTree);
            }
            else if (pTree->pLeft == nullptr || pTree->pRight == nullptr) {
                // 현재 노드를 삭제하고 자식을 부모의 left or right에 해당하는 곳에 추가.
                Tree* pNode = nullptr;
                if (pTree->pLeft) {
                    pNode = pTree->pLeft;
                }
                else {
                    pNode = pTree->pRight;
                }

                if (root == pTree) {
                    root = pNode;
                }
                else {
                    if (pParent->pLeft == pTree) {
                        pParent->pLeft = pNode;
                    }
                    else {
                        pParent->pRight = pNode;
                    }
                }

                free(pTree);
            }
            else if (pTree->pLeft && pTree->pRight) {
                // 1) 오른쪽 트리의 최소 자식을 찾는다.
                Tree* pMinNode = findMinNode(pTree, pTree->pRight);

                if (root == pTree) {
                    root = pMinNode;
                }
                else {
                    // 2) 부모에 단다.
                    if (pParent->pLeft == pTree) {
                        pParent->pLeft = pMinNode;
                    }
                    else {
                        pParent->pRight = pMinNode;
                    }
                }

                pMinNode->pLeft = pTree->pLeft;
                pMinNode->pRight = pTree->pRight;

                // 3) 현재 노드를 삭제한다.
                free(pTree);
            }
        }
    }
}

void destroy(Tree* pTree)
{
    if (pTree->pLeft)
        postorder(pTree->pLeft);

    if (pTree->pRight)
        postorder(pTree->pRight);

    free(pTree);
}

int main()
{
    root = allocate(50);

    Tree* pNode = allocate(40);
    insert(root, pNode);
    pNode = allocate(60);
    insert(root, pNode);
    pNode = allocate(25);
    insert(root, pNode);
    pNode = allocate(30);
    insert(root, pNode);
    pNode = allocate(55);
    insert(root, pNode);
    pNode = allocate(70);
    insert(root, pNode);
    pNode = allocate(12);
    insert(root, pNode);
    pNode = allocate(27);
    insert(root, pNode);

    remove(root, root, 60);
    remove(root, root, 50);
    remove(root, root, 55);
    remove(root, root, 70);
    remove(root, root, 40);
    remove(root, root, 25);

    if (root) {
        preorder(root);
        //inorder(root);
        //postorder(root);
    }
    else {
        printf("no data in tree\n");
    }
    
    destroy(root);

    return 0;
}

자 오늘은 여기까지!