BST

서론

BST : Binary Search Tree

이진 트리의 구조를 이용해 노드를 이진 탐색할 수 있는 자료구조.

한 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 노드들로 구성된다.

반대로 오른쪽 서브 트리는 해당 노드의 값보다 큰 노드들로 구성된다.

이진탐색트리의 노드는 키 값(Key Value)과 좌우 자식 노드를 가리키는 포인터를 가진다.

구현

삽입

삽입하려는 노드의 키 값을 해당 트리의 값들과 비교하여 자리를 찾아 추가한다. 

키 값이 크면 오른쪽, 작으면 왼쪽으로 이동하며(검색 방법) NULL을 만나게 되면 새로운 노드를 삽입한다.

삭제

첫 번째 방법 - 제거하려는 노드가 자식 노드가 없는 경우이다. 해당 노드를 제거하면 된다.

두 번째 – 제거하려는 노드가 한 개의 자식 노드를 가지는 경우이다. 해당 노드의 자식 노드를 부모 노드와 연결해주면 된다.

세 번째 – 제거하려는 노드가 두 개의 자식 노드를 가지는 경우이다. 

왼쪽 서브 트리 중 가장 큰 값을 갖는 노드 또는 오른쪽 서브 트리 중 가장 작은 값을 갖는 노드를 

후계자 노드로 하여 그 위치에 대체한다. 

구현

#pragma once
 
// 이진 탐색 트리
template <typename T>
class BinarySearchTree
{
    // 맴버 변수
private:
    // 노드 선언
    typedef struct Node
    {
        // 데이터
        T data;
        // 왼쪽 노드
        Node* left; 
        // 오른쪽 노드
        Node* right; 
    }NODE, *LPNODE, **LLPNODE;
 
    // 루트 노드 선언
    LPNODE m_root; 
 
    // 생성자 소멸자
public:
    // 생성자
    BinarySearchTree()
    {
        // 루트 노드 초기화
        m_root = NULL;
    }
 
    // 소멸자
    ~BinarySearchTree()
    {
        // 트리 삭제
        releaseTree(m_root);
    }
 
    // 외부 인터페이스
public:
    // 노드 삽입
    void addNode(T data)
    {
        // 노드 생성
        LPNODE temp = new Node;
        temp->data = data;
        temp->left = NULL;
        temp->right = NULL;
 
        // 노드 넣기
        recursiveInsert(m_root, temp);
    }
 
    // 노드 삭제
    void deleteNode(T data)
    {
        // 지울 노드 찾기
        LPNODE temp = recursiveDelete(m_root, NULL, data);
 
        // 노드 지움
        if(temp != NULL)
        {
            delete temp;
        }
    }
 
    // 전위 순회
    void preorderTraverse(void)
    {
        // 재귀호출
        recursivePreorder(m_root);
        cout<<endl;
    }
 
    // 중위 순회
    void inorderTraverse(void)
    {
        // 재귀호출
        recursiveInorder(m_root);
        cout<<endl;
    }
 
    // 후위 순회
    void postorderTraverse(void)
    {
        // 재귀호출
        recursivePostorder(m_root);
        cout<<endl;
    }
 
    // 내부 함수
protected:
    // 노드 검색
    LPNODE searchNode(LPNODE node, T data)
    {
        // 널 체크
        if(node == NULL)
        {
            return NULL;
        }
 
        // 같으면 바로 리턴
        if(node->data == data)
        {
            return node;
        }
        // 해당 데이터가 찾는 데이터보다 크다면
        else if(node->data > data)
        {
            // 오른쪽 자식 노드로 재귀호출
            return searchNode(node->left, data);
        }
        else if(node->data < data)
        {
            // 왼쪽 자식 노드로 재귀호출
            return searchNode(node->right, data);
        }
        else
        {
            // 있을 수 없는 접근
            return NULL;
        }
    }
 
    // 서브트리의 가장 작은 노드 검색
    LPNODE minimumNode(LPNODE minNode)
    {
        // 널 체크
        if(minNode == NULL)
        {
            return NULL;
        }
 
        // 왼쪽 자식이 널이면
        if(minNode->left == NULL)
        {
            return minNode;
        }
        // 왼쪽 자식이 널이 아니라면
        else
        {
            // 다시 제일 작은 노드를 검색하기 위해 재귀호출
            return minimumNode(minNode->left);
        }
    }
 
    // 트리 삭제
    void releaseTree(LPNODE root)
    {
        // 자식들이 널이 아닐때 재귀 호출
        if(root->right != NULL)
        {
            releaseTree(root->right);
        }
 
        // 이하동문
        if(root->left != NULL)
        {
            releaseTree(root->left);
        }
 
        // 널처리
        root->left = NULL;
        root->right = NULL;
 
        // 예외처리
        if (root != NULL)
        {
            delete root;
        }
    }
 
    // 노드 삽입
    void recursiveInsert(LPNODE node, LPNODE child)
    {
        // 최초 노드라면
        if(m_root == NULL)
        {
            // 바로 넣고 리턴
            m_root = child;
            return;
        }
 
        // 삽입 노드의 데이터가 더 큰 경우 오른쪽에 넣기
        if(node->data < child->data)
        {
            // 널인지 확인
            if(node->right == NULL)
            {
                node->right = child;
            }
            // 널이 아니라면 재귀 호출
            else
            {
                recursiveInsert(node->right, child);
            }
        }
        // 삽입 노드의 데이터가 더 작은 경우 왼쪽에 넣기
        else if(node->data > child->data)
        {
            // 널인지 확인
            if(node->left == NULL)
            {
                node->left = child;
            }
            // 널이 아니라면 재귀 호출
            else
            {
                recursiveInsert(node->left, child);
            }
        }
        // 같은 노드가 있다면
        else
        {
            cout<<"해당 키 값이 이미 존재합니다."<<endl;
        }
    }
 
    // 노드 재귀 삭제
    LPNODE recursiveDelete(LPNODE node, LPNODE parent, T data)
    {
        // 지울 노드 선언
        LPNODE delNode = NULL;
 
        // 현재 들어온 노드 널 체크
        if(node == NULL)
        {
            return NULL;
        }
 
        // 현재 노드의 데이터가 들어온 데이터보다 크다면?
        if(node->data > data)
        {
            // 지울 노드는 왼쪽 자식 노드로 재귀 호출
            delNode = recursiveDelete(node->left, node, data);
        }
        // 현재 노드의 데이터가 들어온 데이터보다 작다면?
        else if(node->data < data)
        {
            // 지울 노드는 오른쪽 자식 노드로 재귀 호출
            delNode = recursiveDelete(node->right, node, data);
        }
        // 지울 노드 찾음
        else
        {
            // 지울 노드 넣기
            delNode = node;
 
            // 1번 경우. 지울 노드의 자식이 없을 때.
            if(node->left == NULL && node->right == NULL)
            {
                // 부모가 널이라면 루트 노드
                if(parent == NULL)
                {
                    m_root = NULL;
                }
                // 부모의 왼쪽이 지울 노드라면
                else if(parent->left == node)
                {
                    // 부모의 왼쪽 자식 노드 끊기
                    parent->left = NULL;
                }
                // 부모의 오른쪽이 지울 노드라면
                else if(parent->right == node)
                {
                    // 부모의 오른쪽 노드 끊기
                    parent->right = NULL;
                }
                else
                {
                    // 올 수 없는 접근
                    return NULL;
                }
            }
            // 2번 경우. 하나의 자식을 가지고 있다면.
            else if((node->left != NULL && node->right == NULL)
                || (node->left == NULL && node->right != NULL))
            {
                // 이어줄 노드
                LPNODE linkNode = NULL;
 
                // 왼쪽 자식 노드가 널이 아닐 때
                if(node->left != NULL)
                {
                    // 이어줄 노드 저장
                    linkNode = node->left;
                }
                // 오른쪽 자식 노드가 널이 아닐 때
                else if(node->right != NULL)
                {
                    // 이어줄 노드 저장
                    linkNode = node->right;
                }
                else
                {
                    // 올 수 없는 접근
                    return NULL;
                }
 
                // 부모 노드가 널이면 루트니깐
                if(parent == NULL)
                {
                    // 루트와 이어준다.
                    m_root = linkNode;
                }
                // 부모 노드의 왼쪽 자식 노드가 지울 노드라면
                else if(parent->left == node)
                {
                    // 부모의 왼쪽에 이어줄 노드를 연결
                    parent->left = linkNode;
                }
                else if (parent->right == node)
                {
                    // 부모의 오른쪽에 이어줄 노드를 연결
                    parent->right = linkNode;
                }
                else
                {
                    // 올 수 없는 접근
                    return NULL;
                }
            }
            // 3번 경우. 두 개의 자식을 다 가지고 있을 때.
            else if(node->left != NULL && node->right != NULL)
            {
                // 우측 서브트리에서 가장 작은 노드를 찾는다.
                LPNODE minNode = minimumNode(node->right);
                // 지울 노드를 재귀로 가장 작은 노드 위치를 찾아 그것을 지울 노드로 지정한다.
                delNode = recursiveDelete(node, NULL, minNode->data);
                // 현재 노드의 데이터를 가장 작은 노드의 값만 바꾸고 최소 노드를 떼버린다.
                node->data = minNode->data;
                minNode->data = NULL;
            }
            else
            {
                // 올 수 없는 접근
                return NULL;
            }
        }
        return delNode;
    }
 
    // 전위 순회 재귀호출
    void recursivePreorder(LPNODE tree)
    {
        if(tree != NULL)
        {
            cout<< tree->data<< " ";
            recursivePreorder(tree->left);  
            recursivePreorder(tree->right); 
        }
    }
 
    // 중위 순회 재귀호출
    void recursiveInorder(LPNODE tree)
    {
        if(tree != NULL)
        {
            recursiveInorder(tree->left);  
            cout<< tree->data<< " ";
            recursiveInorder(tree->right); 
        }
    }
 
    // 후위 순회 재귀호출
    void recursivePostorder(LPNODE tree)
    {
        if(tree != NULL)
        {
            recursivePostorder(tree->left);  
            recursivePostorder(tree->right); 
            cout<< tree->data<< " ";      
        }
    }
};

결과