Chapter 11. 이진 탐색 트리(Binary Search Tree)

Def) 이진 탐색 트리(BST, Binary Search Tree)

  자료의 효율적인 관리(삽입, 탐색, 삭제)를 위한 이진 트리 기반의 자료구조.

  자료의 계층적인 구조를 표현하기 위해 트리를 사용하는 것이 아님.

  

Note) 이진 탐색 트리의 특징

  - 모든 노드 N에 대해, 왼쪽 서브 트리에 있는 모든 노드의 키값은

    노드 N의 키값보다 작음.

  - 오른쪽 서브 트리에 있는 모든 노드의 키값은 노드 N의 키값보다 큼.

  - 자료의 탐색, 삽입, 삭제가 모두 O(logN)의 시간 복잡도로 동작.

  - 중위 순회시, 오름차순으로 정렬된 값을 얻을 수 있음.

 

Note) 이진 탐색 트리 구현 코드(삽입, 탐색)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

enum {
    ...
};

typedef struct Node {
    ...
} Node_t;

void preorder(Node_t* _pCurrentNode);
void inorder(Node_t* _pCurrentNode);
void postorder(Node_t* _pCurrentNode);
int LCA(int _nNodeData1, int _nNodeData2);
int distance(int _nNodeData1, int _nNodeData2);

void insertBST(Node_t* _pRootNode, int _nData);
void insertRecursively(Node_t* _pCurrentNode, int _nData);
Node_t* findBST(Node_t* _pCurrentNode, int _nData);
void deleteBST(Node_t* _pCurrentNode);

int main(void)
{
    size_t i, uLen;
    int nInput;
    Node_t* pRoot = (Node_t*)malloc(sizeof(Node_t));
    pRoot->nData = 1;
    pRoot->pLeft = NULL;
    pRoot->pRight = NULL;

    scanf("%zu", &uLen);
    for (i = 0; i < uLen; ++i)
    {
        scanf("%d", &nInput);
        insertBST(pRoot, nInput);
    }

    inorder(pRoot);
    printf("\n");

    if (NULL != findBST(pRoot, 12))
    {
        printf("12 is found.\n");
    }
    else
    {
        printf("12 is not found.\n");
    }

    insertBST(pRoot, 12);

    if (NULL != findBST(pRoot, 12))
    {
        printf("12 is found.\n");
    }
    else
    {
        printf("12 is not found.\n");
    }

    inorder(pRoot);
    printf("\n");

    deleteBST(pRoot);

    return 0;
}

...

void insertBST(Node_t* _pRootNode, int _nData)
{
    // 루트 노드가 없으면 삽입을 아에 멈춰야함.
    // 루트 노드의 자손 노드들은 존재 하지 않을 경우 그 자리에 삽입됨.
    // 따라서 삽입용 재귀 함수가 따로 필요함.
    assert(NULL != _pRootNode);

    insertRecursively(_pRootNode, _nData);
}

void insertRecursively(Node_t* _pCurrentNode, int _nData)
{
    if (_nData < _pCurrentNode->nData)
    {
        if (NULL == _pCurrentNode->pLeft)
        {
            _pCurrentNode->pLeft = (Node_t*)malloc(sizeof(Node_t));
            _pCurrentNode->pLeft->nData = _nData;
            _pCurrentNode->pLeft->pLeft = NULL;
            _pCurrentNode->pLeft->pRight = NULL;
        }
        else
        {
            insertRecursively(_pCurrentNode->pLeft, _nData);
        }
    }
    else
    {
        if (NULL == _pCurrentNode->pRight)
        {
            _pCurrentNode->pRight = (Node_t*)malloc(sizeof(Node_t));
            _pCurrentNode->pRight->nData = _nData;
            _pCurrentNode->pRight->pLeft = NULL;
            _pCurrentNode->pRight->pRight = NULL;
        }
        else
        {
            insertRecursively(_pCurrentNode->pRight, _nData);
        }
    }
}

Node_t* findBST(Node_t* _pCurrentNode, int _nData)
{
    if (NULL == _pCurrentNode)
    {
        return NULL;
    }

    if (_nData == _pCurrentNode->nData)
    {
        return _pCurrentNode;
    }
    else
    {
        if (_nData < _pCurrentNode->nData)
        {
            return findBST(_pCurrentNode->pLeft, _nData);
        }
        else
        {
            return findBST(_pCurrentNode->pRight, _nData);
        }
    }
}

void deleteBST(Node_t* _pCurrentNode)
{
    if (NULL != _pCurrentNode)
    {
        deleteBST(_pCurrentNode->pLeft);
        deleteBST(_pCurrentNode->pRight);
        free(_pCurrentNode);
        _pCurrentNode = NULL;
    }
}

 

Def) 후속 노드(Successor Node)

  어떤 노드의 데이터 다음으로 큰 데이터를 가진 노드.

  후속 노드는 자식이 없거나, 오른쪽 자식만 있음.

  왼쪽 자식이 있는 경우에는 후속 노드가 아님이 자명함.

  반대로 다음으로 작은 데이터를 가진 노드를 Predecessor Node라 함.

  

 

Thm) 이진 탐색 트리에서의 삭제

  - 해당 노드를 삭제한 후에는 BST 특징을 유지할 수 있어야 함.

    따라서 다른 적절한 노드를 찾아 해당 노드를 대체하는 방식.

  - 이때 삭제 연산의 시간 복잡도는 O(logN) 혹은O(h)이라 할 수 있음.

Case 1. 자식 노드가 없음.	Case 2. 자식 노드 하나 있음.	Case 3. 자식 노드 두 개 있음.
- 해당 노드 삭제 - 엣지 삭제(NULL 대입)	- 해당 노드 삭제 - 부모 노드의 포인터가   해당 노드의 자식 노드 주소를 저장	- 후속 노드의 값을 현재 노드로 복사 - 후속 노드 삭제

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

enum {
    ...
};

typedef struct Node {
    ...
} Node_t;

void preorder(Node_t* _pCurrentNode);
void inorder(Node_t* _pCurrentNode);
void postorder(Node_t* _pCurrentNode);
int LCA(int _nNodeData1, int _nNodeData2);
int distance(int _nNodeData1, int _nNodeData2);

void insertBST(Node_t* _pRootNode, int _nData);
void insertRecursively(Node_t* _pCurrentNode, int _nData);
Node_t* findBST(Node_t* _pCurrentNode, int _nData);
void deleteBST(Node_t* _pCurrentNode);
Node_t* eraseBST(Node_t* _pCurrentNode, int _nData);
Node_t* findSuccessor(Node_t* _pCurrentNode);

int main(void)
{
    size_t i, uLen;
    int nInput;
    Node_t* pRoot = (Node_t*)malloc(sizeof(Node_t));
    pRoot->nData = 1;
    pRoot->pLeft = NULL;
    pRoot->pRight = NULL;

    scanf("%zu", &uLen);
    for (i = 0; i < uLen; ++i)
    {
        scanf("%d", &nInput);
        insertBST(pRoot, nInput);
    }

    inorder(pRoot);
    printf("\n");

    if (NULL != findBST(pRoot, 12))
    {
        printf("12 is found.\n");
    }
    else
    {
        printf("12 is not found.\n");
    }

    insertBST(pRoot, 12);

    if (NULL != findBST(pRoot, 12))
    {
        printf("12 is found.\n");
    }
    else
    {
        printf("12 is not found.\n");
    }

    inorder(pRoot);
    printf("\n");

    eraseBST(pRoot, 4);
    inorder(pRoot);
    printf("\n");

    eraseBST(pRoot, 18);
    inorder(pRoot);
    printf("\n");

    eraseBST(pRoot, 14);
    inorder(pRoot);
    printf("\n");

    insertBST(pRoot, 15);
    eraseBST(pRoot, 10);
    inorder(pRoot);

    deleteBST(pRoot);

    return 0;
}

...

Node_t* eraseBST(Node_t* _pCurrentNode, int _nData)
{
    if (NULL == _pCurrentNode)
    {
        return NULL;
    }

    if (_nData < _pCurrentNode->nData)
    {
        _pCurrentNode->pLeft = eraseBST(_pCurrentNode->pLeft, _nData);
    }
    else if (_pCurrentNode->nData < _nData)
    {
        _pCurrentNode->pRight = eraseBST(_pCurrentNode->pRight, _nData);
    }
    else
    {
        if (NULL != _pCurrentNode->pLeft && NULL != _pCurrentNode->pRight)
        {
            Node_t* pSuccessorNode = findSuccessor(_pCurrentNode);
            _pCurrentNode->nData = pSuccessorNode->nData;
            _pCurrentNode->pRight = eraseBST(_pCurrentNode->pRight, pSuccessorNode->nData);
        }
        else
        {
            Node_t* pTemp = NULL == _pCurrentNode->pLeft ? _pCurrentNode->pRight : _pCurrentNode->pLeft;
            free(_pCurrentNode);
            _pCurrentNode = NULL;
            return pTemp;
        }
    }

    return _pCurrentNode;
}

Node_t* findSuccessor(Node_t* _pCurrentNode)
{
    Node_t* pCurrentNode = _pCurrentNode->pRight;
    while (NULL != pCurrentNode && NULL != pCurrentNode->pLeft)
    {
        pCurrentNode = pCurrentNode->pLeft;
    }
    return pCurrentNode;
}

Note) 이진 탐색 트리의 문제점

  - 원소의 삽입 순서에 따라 이진 탐색 트리가 한쪽으로

    치우친 형태로 구성될 수도 있음.

  - 이럴 경우 트리의 높이 h = n - 1 형태로 구성됨.

    즉, 삽입/탐색/삭제 시간 복잡도 O(h) == O(n)으로 결정됨.

 

Note) 해결 방법

  - 한쪽으로 치우친 트리의 구성을 변경하여

    균형 잡힌 트리 형태로 변경할 수 있음.

  - ex. AVL 트리, 레드-블랙 트리(Red-Black Tree),

      B 트리, 스플레이 트리(Splay Tree) 등등