[자료구조/정리] 이진 탐색 트리(Binary Search Tree)

[ 이진 탐색 트리(Binary Search Tree) ]

자식이 최대 2개 존재할 수 있음.
작으면 왼쪽, 크면 오른쪽.

          30
     15       50
  10   25 40  80
                    100

장점 : 탐색이 빠름.
         예) 40을 찾을 경우, 
              30 < 40 30 왼쪽 버림.
              50 > 40 50 오른쪽 버림.

Root : 트리의 최상위 노드. 
리프노드 : 가장 끝에 있는 노드. 자식이 없는 노드.
서브트리 : 큰 트리의 일부분.
편향트리 : 한쪽으로 치우친 트리. 예) 10 - 20 - 30 - 40 - 50
               편향트리가 나오는 것을 주의해야 함. 이진탐색트리의 장점이 사라짐.

 

Value : 실제 저장할 값. 
Key : 탐색할 때 사용하는 값.

 

[ 전체 코드 ]

BinaryTree.h

#pragma once

#include <assert.h>

template <typename Key, typename Value>
class CBinaryTreeNode
{
    template <typename Key, typename Value>
    friend class CBinaryTree;
    template <typename Key, typename Value>
    friend class CBinaryTreeIterator;
private:
    CBinaryTreeNode()  // 생성자.
    {
        m_pLeft = nullptr;
        m_pRight = nullptr;
        m_pParent = nullptr;
        m_pNext = nullptr;
        m_pPrev = nullptr;
    }
    ~CBinaryTreeNode()  // 소멸자.
    {
    }
private:
    CBinaryTreeNode<Key, Value>* m_pLeft;
    CBinaryTreeNode<Key, Value>* m_pRight;
    CBinaryTreeNode<Key, Value>* m_pParent;
    CBinaryTreeNode<Key, Value>* m_pNext;
    CBinaryTreeNode<Key, Value>* m_pPrev;
public:
    Key first;
    Value second;
};

template <typename Key, typename Value>
class CBinaryTreeIterator
{
    template <typename Key, typename Value>
    friend class CBinaryTree;
public:
    CBinaryTreeIterator()
    {
        m_pNode = nullptr;
    }
    ~CBinaryTreeIterator()
    {
    }
private:
    CBinaryTreeNode<Key, Value>* m_pNode;
public:
    bool operator == (const CBinaryTreeIterator<Key, Value>& iter) const
    {
        return m_pNode == iter.m_pNode;
    }
    bool operator != (const CBinaryTreeIterator<Key, Value>& iter) const
    {
        return m_pNode != iter.m_pNode;
    }
    void operator ++ ()
    {
        m_pNode = m_pNode->m_pNext;
    }
    void operator ++ (int)
    {
        m_pNode = m_pNode->m_pNext;
    }
    void operator -- ()
    {
        m_pNode = m_pNode->m_pPrev;
    }
    void operator -- (int)
    {
        m_pNode = m_pNode->m_pPrev;
    }
    CBinaryTreeNode<Key, Value>* operator -> () const
    {
        return m_pNode;
    }
};

template <typename Key, typename Value>
class CBinaryTree
{
public:
    CBinaryTree()
    {
        m_pRoot = nullptr;
        m_pBegin = new Node;
        m_pEnd = new Node;

        // begin과 end연결.
        m_pBegin->m_pNext = m_pEnd;
        m_pEnd->m_pPrev = m_pBegin;

        m_iSize = 0;
    }
    ~CBinaryTree()
    {
        clear();
        delete m_pBegin;
        delete m_pEnd;
    }
private:
    typedef CBinaryTreeNode<Key, Value> Node;
    typedef CBinaryTreeNode<Key, Value>* PNode;
public:
    typedef CBinaryTreeIterator<Key, Value> iterator;
private:
    PNode m_pRoot;
    PNode m_pBegin;
    PNode m_pEnd;
    int m_iSize;
public:
    // 추가 (1. 반복문 이용 2. 재귀함수 이용) >> 재귀함수 이용.
    void insert(const Key& key, const Value& value)
    {
        if (!m_pRoot)  // root가 null일 경우(처음 노드를 추가하는 경우)
        {
            m_pRoot = new Node;  // root 생성.

            m_pRoot->first = key;  // key 저장.
            m_pRoot->second = value;  // value 저장.

            // root와 end를 연결.
            m_pRoot->m_pNext = m_pEnd;  
            m_pEnd->m_pPrev = m_pRoot;

            // root와 begin을 연결.
            m_pRoot->m_pPrev = m_pBegin;
            m_pBegin->m_pNext = m_pRoot;
        }
        else
        {
            PNode pNewNode = insert(key, value, m_pRoot);
        }

        ++m_iSize;
    }

    // 크기.
    int size() const
    {
        return m_iSize;
    }

    // 비어있는지 확인.
    bool empty() const
    {
        return m_iSize == 0;
    }
	
    // 모두 지움.
    void clear()
    {
        PNode pNode = m_pBegin->m_pNext;  // begin의 다음 노드로  설정.

        while (pNode != m_pEnd)  // end가 아닐 동안 실행.
        {
            PNode pNext = pNode->m_pNext;  // 지울 노드의 next를 저장.

            delete pNode;  // 지움.

            pNode = pNext;  // 지울 노드 바꿔줌.
        }

        // begin과 end 연결.
        m_pBegin->m_pNext = m_pEnd;
        m_pEnd->m_pPrev = m_pBegin;

        m_iSize = 0;

        m_pRoot = nullptr;
    }

    // 첫 노드 리턴.
    iterator begin() const
    {
        iterator iter;

        iter.m_pNode = m_pBegin->m_pNext;

        return iter;
    }

    // 끝 노드 리턴.
    iterator end() const
    {
        iterator iter;

        iter.m_pNode = m_pEnd;

        return iter;
    }

    // 찾기.
    iterator find(const Key& key) const
    {
        assert(m_iSize != 0);  // 노드가 존재하지 않는 경우, 경고창을 띄우고 종료 시킴.

        return find(key, m_pRoot);
    }

    // 삭제.
    iterator erase(const Key& key)
    {
        assert(m_iSize != 0);  // 노드가 존재하지 않는 경우, 경고창을 띄우고 종료 시킴.
    
        iterator iter = find(key, m_pRoot);  // 지울 노드가 있는 지 확인.

        if (iter.m_pNode == m_pEnd)  // 지울 노드를 못 찼았을 경우.
            return iter;  // 그냥 리턴.

        // 자식이 없는 노드일 경우, 그냥 지움.
        if (!iter.m_pNode->m_pLeft && !iter.m_pNode->m_pRight)  // left와 right가 없으면 자식 노드가 없다는 것을 의미.
        {
            PNode pNext = iter.m_pNode->m_pNext;  // 지울 노드의 next 저장.
            PNode pPrev = iter.m_pNode->m_pPrev;  // 지울 노드의 previous 저장,

            // 지울 노드의 next와 prevoius를 연결.
            pPrev->m_pNext = pNext;  
            pNext->m_pPrev = pPrev;

            if (!iter.m_pNode->m_pParent)  // 부모 노드가 없을 경우.
                m_pRoot = nullptr;  // root를 null로 초기화.
            else  // 부모 노드가 있을 경우.
            {
                if (iter.m_pNode->m_pParent->m_pLeft == iter.m_pNode)  // 지울 노드가 부모의 왼쪽 자식 노드일 경우.
                    iter.m_pNode->m_pParent->m_pLeft = nullptr;  // 지울 노드 부모의 왼쪽 자식 노드를 null로 초기화.
                else  // 지울 노드가 부모의 오른쪽 자식 노드일 경우.
                    iter.m_pNode->m_pParent->m_pRight = nullptr;  // 지울 노드 부모의 오른쪽 자식 노드를 null로 초기화. 
            }

            delete iter.m_pNode;  // 노드 지움.

            iter.m_pNode = pNext;  // pNode를 지운 노드의 next로 지정.

            --m_iSize;

            return iter;
        }

        PNode pDeleteNode = nullptr;  // 지울 노드.
        bool bFindLeft = false;

        if (iter.m_pNode->m_pLeft)  // 지울 노드의 left가 있을 경우.
        {
            pDeleteNode = LeftMax(iter.m_pNode->m_pLeft);  // LeftMax로 왼쪽에서 가장 큰 노드를 찾음.
            bFindLeft = true;
        }
        else  // 지울 노드의 right가 있을 경우.
        {
            pDeleteNode = RightMin(iter.m_pNode->m_pRight);  // RightMin로 오른쪽에서 가장 작은 노드를 찾음.
        }

        // 지울 노드의 값으로 현재 노드를 대체.
        iter.m_pNode->first = pDeleteNode->first;
        iter.m_pNode->second = pDeleteNode->second;

        // 지울 노드의 자식노드가 있을 경우 지울 노드의 자리를 대체.
        if (bFindLeft)  // 지울 노드가 왼쪽에 있을 경우. 
        {
            if (pDeleteNode->m_pParent->m_pLeft == pDeleteNode)  // 지울 노드가 부모의 왼쪽에 있을 경우.
                pDeleteNode->m_pParent->m_pLeft = pDeleteNode->m_pLeft;  // 지울 노드의 부모 노드와 지울 노드의 left를 연결. (지울 노드의 부모의 left를 지울 노드의 left로 설정.)
            else  // 지울 노드가 부모의 오른쪽에 있을 경우.
                pDeleteNode->m_pParent->m_pRight = pDeleteNode->m_pLeft;  // 지울 노드의 부모 노드와 지울 노드의 left를 연결. (지울 노드의 부모의 right를 지울 노드의 left로 설정.)

            if (pDeleteNode->m_pLeft)  // 지울 노드의 left가 있는 경우.
                pDeleteNode->m_pLeft->m_pParent = pDeleteNode->m_pParent;  // 지울 노드를 대체할 노드의 부모를 지울 노드의 부모와 연결. (지울 노드의 left의 부모를 지울 노드의 부모로 설정.)
        }
        else  // 지울 노드가 오른쪽에 있을 경우.
        {
            if (pDeleteNode->m_pParent->m_pLeft == pDeleteNode)  // 지울 노드가 부모의 왼쪽에 있을 경우.
                pDeleteNode->m_pParent->m_pLeft = pDeleteNode->m_pRight;  // 지울 노드의 부모 노드와 지울 노드의 right를 연결. (지울 노드의 부모의 left를 지울 노드의 right로 설정.)
            else  // 지울 노드가 부모의 오른쪽에 있을 경우.
                pDeleteNode->m_pParent->m_pRight = pDeleteNode->m_pRight;  // 지울 노드의 부모 노드와 지울 노드의 right를 연결. (지울 노드의 부모의 right를 지울 노드의 right로 설정.)

            if (pDeleteNode->m_pRight)  // 지울 노드의 right가 있는 경우.
                pDeleteNode->m_pRight->m_pParent = pDeleteNode->m_pParent;  // 지울 노드를 대체할 노드의 부모를 지울 노드의 부모와 연결. (지울 노드의 right의 부모를 지울 노드의 부모로 설정.)
        }

        PNode pNext = pDeleteNode->m_pNext;  // 지울 노드의 next를 저장.
        PNode pPrev = pDeleteNode->m_pPrev;  // 지울 노드의 previous를 저장.

        // 지울 노드의 next와 previous를 연결.
        pNext->m_pPrev = pPrev;
        pPrev->m_pNext = pNext;

        if (bFindLeft)  // 지울 노드가 왼쪽에 있을 경우. 
            iter.m_pNode = iter.m_pNode->m_pNext;  // pNode를 pNode의 next로 설정.
        else  // 지울 노드가 오른쪽에 있을 경우. 
            iter.m_pNode = iter.m_pNode;  // pNode를 pNode로 설정.

        delete pDeleteNode;  // 노드 지움.

        --m_iSize;

        return iter;
    }

private:
    PNode insert(const Key& key, const Value& value, PNode pNode)
    {
        // key값이 pNode(중심값)보다 작을 경우. 즉, 왼쪽에 배치하는 경우.
        if (pNode->first >= key)  
        {
            if (!pNode->m_pLeft)  // 왼쪽 자식 노드가 없을 경우.
            {
                PNode pNewNode = new Node;  // 새 노드 생성.

                pNewNode->first = key;  // key값 저장.
                pNewNode->second = value;  // value값 저장.

                pNode->m_pLeft = pNewNode;  // pNode의 left로 새 노드 설정.
                pNewNode->m_pParent = pNode;  // 새 노드의 부모로  pNode 설정.

                PNode pPrev = pNode->m_pPrev;  // 새 노드의 부모노드의 이전노드를 얻어옴. 

                pPrev->m_pNext = pNewNode;  // 부모노드의 이전노드의 next를 새 노드로 설정.
                pNewNode->m_pPrev = pPrev;  // 새 노드의 previous를 부모노드의 이전노드로  설정.

                pNewNode->m_pNext = pNode;  // 새 노드의 next로 pNode 설정.
                pNode->m_pPrev = pNewNode;  // pNode의 previous로 새 노드 설정.

                return pNewNode;
            }
            else  // 자식 노드가 있을 경우
            {
                return insert(key, value, pNode->m_pLeft);  // 기준 노드를 pNode의 left로 줌. 
            }
        }
		
		// 오른쪽에 배치할 경우
        // 오른쪽 자식 노드가 없을 경우 오른쪽 자식으로 만들어준다.
        if (!pNode->m_pRight)
        {
            PNode pNewNode = new Node;  // 새 노드 생성.

            pNewNode->first = key  ;// key값 저장.
            pNewNode->second = value  ;// value값 저장.

            pNode->m_pRight = pNewNode;  // pNode의 right로 새 노드 설정.
            pNewNode->m_pParent = pNode; // 새 노드의 부모로  pNode 설정.

            PNode pNext = pNode->m_pNext;  // 새 노드의 부모노드의 다음노드를 얻어옴. 

            pNext->m_pPrev = pNewNode;  // 부모노드의 다음노드의 previous를 새 노드로 설정.
            pNewNode->m_pNext = pNext;  // 새 노드의 next를 부모노드의 다음노드로  설정.

            pNewNode->m_pPrev = pNode;  // 새 노드의 previous로 pNode 설정.
            pNode->m_pNext = pNewNode;// pNode의 next로 새 노드 설정.

            return pNewNode;
        }

        // 오른쪽 자식 노드가 있을 경우 오른쪽 자식노드를 넣어주어서 다시 탐색.
        return insert(key, value, pNode->m_pRight);
    }

    iterator find(const Key& key, PNode pNode) const
    {
        if (!pNode)  // 찾을 노드가 없을 경우
            return end();  // end를 리턴.
        else if (pNode->first == key)   // 노드를 찾았을 경우.
        {
            iterator iter;
    
            iter.m_pNode = pNode;

            return iter;
        }
		
        if (pNode->first > key) // key값이 더 작을 경우, 왼쪽을 탐색.
            return find(key, pNode->m_pLeft);

        return find(key, pNode->m_pRight);  // 아닐 경우, 오른쪽 탐색.
    }

    // 왼쪽에서 가장 큰 노드 찾기.
    PNode LeftMax(PNode pNode)
    {
        if (!pNode->m_pRight)  // 오른쪽 자식 노드가 없을 경우.
            return pNode;  // 현재 노드가 가장 큰 것이기 때문에 현재 노드를 리턴.

        return LeftMax(pNode->m_pRight);  // 아닐 경우. 오른쪽 노드를 기준으로  다시 찾음.
    }

    // 오른쪽에서 가장 작은 노드 찾기.
    PNode RightMin(PNode pNode)
    {
        if (!pNode->m_pLeft)  // 왼쪽 자식 노드가 없을 경우.
            return pNode;  // 현재 노드가 가장 작은 것이기 때문에 현재 노드를 리턴.

        return RightMin(pNode->m_pLeft);  // 아닐 경우. 왼쪽 노드를 기준으로  다시 찾음.
    }
};

main.cpp

#include <iostream>
#include "BinaryTree.h"

int main()
{
    CBinaryTree<int, const char*> tree;

    int	iArr[8] = { 50, 40, 80, 30, 15, 25, 10, 100 };

    tree.insert(30, "가");
    tree.insert(15, "나");
    tree.insert(10, "다");
    tree.insert(25, "라");
    tree.insert(50, "마");
    tree.insert(40, "바");
    tree.insert(80, "사");
    tree.insert(100, "아");

    CBinaryTree<int, const char*>::iterator iter = tree.begin();
    CBinaryTree<int, const char*>::iterator iterEnd = tree.end();

    for (; iter != iterEnd; ++iter)
    {
        std::cout << "Key : " << iter->first << " Value : " << iter->second << std::endl;
    }
	
    std::cout << "======================= 찾기 =======================" << std::endl;

    iter = tree.find(200);

    if (iter == tree.end())
        std::cout << "찾는 대상이 없습니다." << std::endl;

    iter = tree.find(10);

    std::cout << "Find Key : " << iter->first << " Value : " << iter->second << std::endl;

    std::cout << "======================= 삭제 =======================" << std::endl;

    iter = tree.erase(50);
    std::cout << "erase 50 >> Next : " << iter->first << std::endl;
	
    for (int i = 0; i < 8; ++i)  // 50, 40, 80, 30, 15, 25, 10, 100 순으로 지움.
    {
        std::cout << std::endl << "Delete : " << iArr[i] << std::endl;
        iter = tree.erase(iArr[i]);

        if (iter != tree.end())
            std::cout << "Next : " << iter->first << std::endl;
    }

    iter = tree.begin();
    iterEnd = tree.end();

    std::cout << std::endl;
    for (; iter != iterEnd; ++iter)
    {
        std::cout << "Key : " << iter->first << " Value : " << iter->second << std::endl;
    }

    return 0;
}

 

[ 결과 ]

Key : 10 Value : 다
Key : 15 Value : 나
Key : 25 Value : 라
Key : 30 Value : 가
Key : 40 Value : 바
Key : 50 Value : 마
Key : 80 Value : 사
Key : 100 Value : 아
======================= 찾기 =======================
찾는 대상이 없습니다.
Find Key : 10 Value : 다
======================= 삭제 =======================
erase 50 >> Next : 80

Delete : 50

Delete : 40
Next : 80

Delete : 80
Next : 100

Delete : 30
Next : 100

Delete : 15
Next : 25

Delete : 25
Next : 100

Delete : 10
Next : 100

Delete : 100

 

[ 설명 ]