C++ 이진 탐색 트리 구현

map 사용법

#include<iostream>
#include<vector> //백터 사용하기 위한 참조
#include<list> //리스트 사용하기 위해서 선언
#include"CArr.h"
#include "test.h"
#include "CList.h"
#include<time.h>
#include<set>
#include<map>
#include<string>
#include<string.h>
#include "CBST.h"
 
using namespace std;
using std::vector; // std쓰기 귀찮아서 
using std::list;
#define MAN  1
#define WOMAN  2
struct info
{
    char ss[20];
    int age;
    int gender;
 
    info()
        :ss{}
        , age(0)
        , gender(0)
    {
 
    }
    info(const char* s, int age, int gender)
        :ss{}
        , age(age)
        , gender(gender)
    {
        strcpy_s(ss, s); // 문자열 복사
    }
};
 
int main()
{
    map<const char*, info> mapData;  // 키값 , 데이터 값
 
    info student("홍길동", 18, MAN);
    info student2("이지혜", 25, WOMAN);
 
    mapData.insert(make_pair("홍길동", student)); // make_pair함수가 묶어서 만들어줌 노드 안에는 pair가 들어있음
    mapData.insert(make_pair("이지혜", student2)); // pair안에는 키값인 이름과 정보들이 들어 있음
 
    map<const char*, info>::iterator iter;
    iter = mapData.find("홍길동");
    cout << "이름 : " << iter->second.ss << "\n";
    cout << "나이 : " << iter->second.age << "\n";
    cout << "성별 : ";
    if (MAN == iter->second.gender)
    {
        cout << "남자";
    }
    else {
        cout << "여자";
    }
 
 
    return 0;
}
 
 

 

직접 구현 해보기

insert 구현

#pragma once
template <typename T1, typename T2>
struct tpair //데이터 파트 구조체
{
    T1    first;
    T2    second;
};
 
template <typename T1, typename T2> // map형식인 키값 데이터값 두개의 템플릿 
struct Node { //노드를 저장하는 구조체
    tpair<T1, T2>   pair; //데이터 파트  first,second
 
    Node*    Parent; // 부모노드
    Node*    Leftchild; //왼쪽자식노드
    Node*    Rightchild; //오른쪽자식노드
 
    Node()
    {}
};
 
template <typename T1, typename T2>
class CBST
{
private:
    Node<T1, T2>*   Root; //루트 노드 주소
    int                count; //데이터 개수
public:
    CBST()
        : Root(nullptr)
        , count(0)
    {}
    CBST(Node<T1, T2>* Root)
        :Root(Root)
    {}
public:
    bool insert(const tpair<T1, T2>& _pair);
};
 
template<typename T1, typename T2>
inline bool CBST<T1, T2>::insert(const tpair<T1, T2> & _pair)
{
    Node<T1, T2>* pnew = new Node<T1, T2>();
    pnew->pair = _pair;
    pnew->Leftchild = nullptr;
    pnew->Rightchild = nullptr;
    pnew->Parent = nullptr;
 
    // 첫번째 데이터이면
 
    if (nullptr == Root)
    {
        Root = pnew;
    }
    else
    { Node<T1, T2>* pnode = Root; // Root는 수정되면 안됨
        while (true)
        {      
            if (pnode->pair.first < pnew->pair.first) // 첫번째 데이터보다 들어온 데이터가 작으면 
            {
                if (nullptr == pnode->Rightchild) // 오른쪽 자식이 없으면 거기에 데이터가 들어가야함
                {
                    pnode->Rightchild = pnew; // 오른쪽 자식에다 동적할당된 값을 넣어주고
                    pnew->Parent = pnode; // 그 부모를 서로 연결해줌
                    break; // while문 빠져나감
                }
                else {
                    pnode = pnode->Rightchild; // 널포인트가 아니면 계속 반복실행
                }
 
            }
            else if (pnode->pair.first > pnew->pair.first)  //위에랑 반대
            {
                if (nullptr == pnode->Leftchild)
                {
                    pnode->Leftchild = pnew;
                    pnew->Parent = pnode;
                    break;
                }
                else {
                    pnode = pnode->Leftchild;
                }
            }
            else { // 키값이 같으면 
                return false; // 
            }
        }
 
        count++;
    }
 
    return true;
}
 

 

 

enum클래스 사용해서 insert구현해보기

#pragma once
 
enum class Node_Type //열거형 클래스를 만드러줌
{
    PARENT, //0
    LCHILD, // 1
    RCHILD, // 2
    END,    // 3
};
template <typename T1, typename T2>
struct tpair //데이터 파트 구조체
{
    T1    first;
    T2    second;
};
 
template <typename T1, typename T2> // map형식인 키값 데이터값 두개의 템플릿 
struct Node { //노드를 저장하는 구조체
 
    tpair<T1, T2>   pair; //데이터 파트  first,second
 
    Node*        arrNode[(int)Node_Type::END]; //열거형을 쓸때에는 자료형을 붙어줘야함
 
 
public:
    Node()
        :pair()
        , arrNode{}
    {}
 
    Node(const tpair<T1, T2>& _piar, Node* _Parent, Node* _Lchild, Node* _Rchild)
        :pair(_piar)
        ,arrNode{ _Parent,_Lchild,_Rchild }
    {}
};
 
template <typename T1, typename T2>
class CBST
{
private:
    Node<T1, T2>*   Root; //루트 노드 주소
    int                count; //데이터 개수
public:
    CBST()
        : Root(nullptr)
        , count(0)
    {}
public:
    bool insert(const tpair<T1, T2>& _pair);
};
 
template<typename T1, typename T2>
inline bool CBST<T1, T2>::insert(const tpair<T1, T2> & _pair)
{
    Node<T1, T2>* pnew = new Node<T1, T2>(_pair, nullptr, nullptr, nullptr);
 
    // 첫번째 데이터이면
 
    if (nullptr == Root)
    {
        Root = pnew;
    }
    else
    {
        Node<T1, T2>* pnode = Root; // Root는 수정되면 안됨
        Node_Type node_type = Node_Type::END; // 타입을 정해준다.
        while (true)
        {
             if (pnode->pair.first < pnew->pair.first) // 첫번째 데이터보다 들어온 데이터가 작으면 
            {
                 node_type = Node_Type::RCHILD; // 타입은 오른쪽 자식타입
            }
            else if (pnode->pair.first > pnew->pair.first)  //첫번째 데이터보다 들어온 데이터가 크면 
            {
                 node_type = Node_Type::LCHILD; //타입은 왼쪽 자식타입
            }
            else { // 키값이 같으면 
                return false;
            }
 
            if (nullptr == pnode->arrNode[(int)node_type]) // 널포인트가 아니면 그에맞는 데이터 타입이 들어감
            {
                pnode->arrNode[(int)node_type] = pnew; // 그 타입에 자식에다가 새로운 동적할당값을 넣어줌
                pnew->arrNode[(int)Node_Type::PARENT] = pnode; // 부모랑 자식 연결
                break; // while문 빠져나감
            }
            else {
                pnode = pnode->arrNode[(int)node_type]; // 널포인트가 아니면 계속 반복실행
            }
            
        }
    }
    count++;
    return true;
}
 

코드로 배열로 받았기 때문에 그낭하고 간결해진다

 

최종코드

#pragma once
#include <assert.h>
enum class Node_Type //열거형 클래스를 만드러줌
{
    PARENT, //0
    LCHILD, // 1
    RCHILD, // 2
    END,    // 3
};
template <typename T1, typename T2>
struct tpair //데이터 파트 구조체
{
    T1    first;
    T2    second;
public:
    tpair(const T1& _first, const T2& _second)
        :first(_first)
        ,second(_second)
    {}
};
 
template <typename T1, typename T2>
tpair<T1, T2> make(const T1& _first, const T2& _second) //map의 make_pair함수 구현
{
 
    return tpair<T1,T2>(_first,_second);
}
 
template <typename T1, typename T2> // map형식인 키값 데이터값 두개의 템플릿 
struct Node { //노드를 저장하는 구조체
 
    tpair<T1, T2>   pair; //데이터 파트  first,second
 
    Node*        arrNode[(int)Node_Type::END]; //열거형을 쓸때에는 자료형을 붙어줘야함
 
 
public:
    Node()
        :pair()
        , arrNode{}
    {}
 
    Node(const tpair<T1, T2>& _piar, Node* _Parent, Node* _Lchild, Node* _Rchild)
        :pair(_piar)
        , arrNode{ _Parent,_Lchild,_Rchild }
    {}
public:
    bool IsRoot()
    {
        if (arrNode[(int)Node_Type::PARENT] == nullptr)
        {
            return true;
            return false;
        }
    }
 
    bool isLeftChild()
    {
        if(arrNode[(int)Node_Type::PARENT]->arrNode[(int)Node_Type::LCHILD] == this)
            return true;
        return false;
    }
    bool isRightChild()
    {
        if (arrNode[(int)Node_Type::PARENT]->arrNode[(int)Node_Type::RCHILD] == this)
            return true;
        return false;
    }
    
    bool IsLeaf() // 자식이 한개도 없는 경우
    {
        if (arrNode[(int)Node_Type::LCHILD] == nullptr && nullptr == arrNode[(int)Node_Type::RCHILD])
            return true;
        return false;
    }
    bool IsFull() // 자식이 두개다 꽉찬 경우
    {
        if (arrNode[(int)Node_Type::LCHILD] != nullptr && nullptr != arrNode[(int)Node_Type::RCHILD])
            return true;
        return false;
    }
};
 
template <typename T1, typename T2>
class CBST
{
private:
    Node<T1, T2>*   Root; //루트 노드 주소
    int                count; //데이터 개수
public:
    CBST()
        : Root(nullptr)
        , count(0)
    {}
public:
    bool insert(const tpair<T1, T2>& _pair);
    Node<T1, T2>* GOS(Node<T1, T2>* pNode);
    Node<T1, T2>* GOP(Node<T1, T2> pNode);
 
 
    class iterator;
    iterator begin();
    iterator end();
    iterator find(const T1& _find);
    iterator erase(const iterator& _node);
private:
    Node<T1, T2>* DeleteNode(Node<T1, T2>* _node);
public:
    // inner클래스
    class iterator {
    private:
        CBST<T1, T2>*     bst;
        Node<T1, T2>*     _Node; // null인 경우 ned iterator
    public:
        iterator()
            :bst(nullptr)
            , _Node(nullptr)
        {}
        iterator(CBST<T1, T2>* bst, Node<T1, T2>* _Node)
            :bst(bst)
            , _Node(_Node)
        {}
    public:
        bool operator ==(const iterator& other)
        {
            if (bst == other.bst && _Node == other._Node)
                return true;
            return false;
        }
 
        bool operator !=(const iterator& other)
        {
            return !(*this == other);
        }
 
 
        const tpair<T1, T2>& operator *()
        {
            // _Node nullptr 체크 (end iterator 인지 아닌지)
            if (_Node == nullptr)
            {
                assert(false);
            }
            return _Node->pair;
        }
 
        const tpair<T1, T2>* operator ->()
        {
            // _Node nullptr 체크 (end iterator 인지 아닌지)
            if (_Node == nullptr)
            {
                assert(false);
            }
            return &_Node->pair;
        }
 
        iterator& operator ++()
        {
            _Node = bst->GOS(_Node);
            return *this;
        }
        friend class CBST<T1, T2>;
    };
};
 
template<typename T1, typename T2>
inline bool CBST<T1, T2>::insert(const tpair<T1, T2> & _pair)
{
    Node<T1, T2>* pnew = new Node<T1, T2>(_pair, nullptr, nullptr, nullptr);
 
    // 첫번째 데이터이면
 
    if (nullptr == Root)
    {
        Root = pnew;
    }
    else
    {
        Node<T1, T2>* pnode = Root; // Root는 수정되면 안됨
        Node_Type node_type = Node_Type::END; // 타입을 정해준다.
        while (true)
        {
            if (pnode->pair.first < pnew->pair.first) // 첫번째 데이터보다 들어온 데이터가 작으면 
            {
                node_type = Node_Type::RCHILD; // 타입은 오른쪽 자식타입
            }
            else if (pnode->pair.first > pnew->pair.first)  //첫번째 데이터보다 들어온 데이터가 크면 
            {
                node_type = Node_Type::LCHILD; //타입은 왼쪽 자식타입
            }
            else { // 키값이 같으면 
                return false;
            }
 
            if (nullptr == pnode->arrNode[(int)node_type]) // 널포인트가 아니면 그에맞는 데이터 타입이 들어감
            {
                pnode->arrNode[(int)node_type] = pnew; // 그 타입에 자식에다가 새로운 동적할당값을 넣어줌
                pnew->arrNode[(int)Node_Type::PARENT] = pnode; // 부모랑 자식 연결
                break; // while문 빠져나감
            }
            else {
                pnode = pnode->arrNode[(int)node_type]; // 널포인트가 아니면 계속 반복실행
            }
 
        }
    }
    count++;
    return true;
}
 
template<typename T1, typename T2>
inline Node<T1, T2>* CBST<T1, T2>::GOS(Node<T1, T2>* pNode)
{
    Node<T1, T2>* pSuccessor = nullptr;
    //1 . 오른쪽 자식 있는 경우, 오른쪽 자식으로 가서, 왼쪽 자식이 없을때 까지 내려감
    if (pNode->arrNode[(int)Node_Type::RCHILD] != nullptr)
    {
        pSuccessor = pNode->arrNode[(int)Node_Type::RCHILD];
 
        while (pSuccessor->arrNode[(int)Node_Type::LCHILD])
        {
            pSuccessor = pSuccessor->arrNode[(int)Node_Type::LCHILD];
        }
    }
 
    //2. 부모로 부터 왼쪽자식일 떄 까지 위로 올라감
    //   그때 부모가 후속자
    else {
        pSuccessor = pNode;
        while (true) {
            // 더이상 위쪽으로 올라갈 수 없다. ==> 마지막 노드였다
            if (pSuccessor->IsRoot())
                return nullptr;
            //부모로 부터 왼쪽자식인지 체크
            if (pSuccessor->isLeftChild())
            {
                    //그때 부모가 후속자            
                pSuccessor = pSuccessor->arrNode[(int)Node_Type::PARENT];
                break;
            }
            else
            {
                pSuccessor = pSuccessor->arrNode[(int)Node_Type::PARENT];
            }
        }
    }
 
    return pSuccessor;
}
 
template<typename T1, typename T2>
inline Node<T1, T2>* CBST<T1, T2>::GOP(Node<T1, T2> pNode)
{
    return NULL;
}
 
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::begin()
{
    Node<T1, T2>* pnew = Root; // 루트주소르 줌
 
    while (pnew->arrNode[(int)Node_Type::LCHILD]) // 루트부터 왼쪽자식이 널포인트까지
    {
        pnew = pnew->arrNode[(int)Node_Type::LCHILD]; // 왼쪽자식에 값을 계속준다. 그것이 중위순환에 첫번 쨰 노드
    }
    return iterator(this, pnew);
}
 
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::end()
{
    return iterator(this, nullptr);
}
 
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::find(const T1 & _find)
{
    Node<T1, T2>* pnode = Root; // Root는 수정되면 안됨
    Node_Type node_type = Node_Type::END; // 가야되는 방향은 미정 정해준다.
    while (true)
    {
        if (pnode->pair.first < _find) // 첫번째 데이터보다 들어온 데이터가 작으면 
        {
            node_type = Node_Type::RCHILD; // 타입은 오른쪽 자식타입
        }
        else if (pnode->pair.first > _find)  //첫번째 데이터보다 들어온 데이터가 크면 
        {
            node_type = Node_Type::LCHILD; //타입은 왼쪽 자식타입
        }
        else { // 키값이 같으면 
            //찾았다 pnode가 현재 찾으려는 노드다
            break;
        }
        if (nullptr == pnode->arrNode[(int)node_type]) // 널포인트가 아니면 그에맞는 데이터 타입이 들어감
        {
            //몾찾았다 . pnode = nullptr ==> enditerator
            pnode = nullptr;
            break;
        }
        else {
            pnode = pnode->arrNode[(int)node_type]; // 널포인트가 아니면 계속 반복실행
        }
 
    }
    return iterator(this, pnode);
}
 
 
template<typename T1, typename T2>
inline Node<T1, T2>* CBST<T1, T2>::DeleteNode(Node<T1, T2>* _node)
{
    //삭제시킬 노드의 후속자 노드를 찾아둔다
    Node<T1, T2>* pSuccessor = GOS(_node);
    //1. 자식이 하나도 없는 경우
    if (_node->IsLeaf())
    {
        
        // 삭제할 노드가 루트였다(자식이 없고 루트 ==>BST안에 데이터가 1개밖에 없었다.)
        if (_node == Root)
        {
            Root = nullptr;
        }
        else {
            //부모노드로 접근, 삭제될 노드인 자식을 가리키는 포인터를 nullptr로 만든다.
            if (_node->isLeftChild())
                _node->arrNode[(int)Node_Type::PARENT]->arrNode[(int)Node_Type::LCHILD] = nullptr;
            else
            {
                _node->arrNode[(int)Node_Type::PARENT]->arrNode[(int)Node_Type::RCHILD] = nullptr;
                
            }
            
        }
        delete _node;
        --count;
    }
    // 2. 자식이 2개인 경우
    else if (_node->IsFull())
    {
        // 삭제 될 자리에 중위 후속자의 값을 복사시킨다.
        _node->pair = pSuccessor->pair;
        // 중위 후속자 노드를 삭제한다.
        DeleteNode(pSuccessor);
        // 삭제할 노드가 중위후속자 노드가 됨
        pSuccessor = _node;
    }
    // 3. 자식이 1개인 경우
    else
    {
        Node_Type echildtype = Node_Type::LCHILD;
        if (_node->arrNode[(int)Node_Type::RCHILD])
            echildtype = Node_Type::RCHILD;
 
        // 삭제할 노드가 루트였다
        if (_node == Root)
        {
            //자식 노드의 부모와, 삭제될 노드의 자식을 연결해준다.
            Root = _node->arrNode[(int)echildtype];
            _node->arrNode[(int)echildtype]->arrNode[(int)Node_Type::PARENT] = nullptr;
        }
 
        // 삭제될 노드의 부모와, 삭제될 노드이 자식을 연결해준다.
        else {
            if (_node->isLeftChild())
            {
                _node->arrNode[(int)Node_Type::PARENT]->arrNode[(int)Node_Type::LCHILD] = _node->arrNode[(int)echildtype];
            }
            else
            {
                _node->arrNode[(int)Node_Type::PARENT]->arrNode[(int)Node_Type::RCHILD] = _node->arrNode[(int)echildtype];
            }
            _node->arrNode[(int)echildtype]->arrNode[(int)Node_Type::PARENT] = _node->arrNode[(int)Node_Type::PARENT];
            
        }
        delete _node;
        --count;
    }
    //데이터 개수 맞춰줌
    
    return pSuccessor;
}
 
 
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::erase(const iterator & _node)
{
    assert(this == _node.bst);
    Node<T1, T2>* pSuccessor = DeleteNode(_node._Node);
 
    return iterator(this, pSuccessor);
}

 

 

출처 : https://www.youtube.com/c/AssortRockGameAcademy