이진 탐색 트리 (3)

이진 탐색 트리 정보

• 우리는 이진 탐색 트리에서 중위 순회가 중요하다.
  • 정렬시켜서 절반씩 날리는 구조를 만들어야 O(logN)이 나오기 때문이당.
• 이진 탐색 트리는 루트 노드만 알면 모든 노드에 접근이 가능하다.
• 그런데 iterator에 begin을 구현할떄는 어떻게 누구를 begin으로 할건지가 고민이다.
  • 트리형태를 가지고 있어서 begin과 end가ㅚ 모호해진다.
  • 규칙이 있어야되는데 애매함.
• begin iterator은 중외 순외 기준 젤 작은값(젤 아래 왼쪽값, 더이상 왼쪽으로 갈수 없을떄)를 가리켜야 한다.
• end iterator은 젤 오른쪽으로 가서 갈 곳이 없는곳에 다음이다.

begin iterator 만들기.

	class iterator;
	iterator begin();
	iterator end();

• class iterator는 이너 클래스라 BST클래스 안에 있는데 이게 iterator 클래스는 구현부는 아래에 있어서 선언만 앞에서 해둬야 오류 안뜬다.
• iterator begin 함수 선언
• iterator end() 함수 선언

	class iterator						
	{
	private:
		BST* m_Owner;					// 1
		BSTNode<T1, T2>* m_TargetNode;	// 2
        
  	};

• iterator을 실제 구현하는 코드를 담을 함수 영역이다.
• 1번은 해당 객체를 소유하고있는(본인) 컨테이너를 가리키고있는 주소값이다.
• 2번은 BSTNode에서 BSTPair<T1, T2> pair를 호출해서 BSTPair에 있는 (T1 first, T2 second) 주소값을 전달받는다.
• 1번과 2번은 맴버들은 노드로 연결이 되어 있는거라 연결형 리스트쪽 iterator이랑 객체가 비슷하다.

	public:
		iterator()
			:m_Owner(nullptr)
			, m_TargetNode(nullptr)
		{}

		iterator(BST* _Owner, BSTNode<T1, T2>* _Node)
			:m_Owner(_Owner)
			, m_TargetNode(_Node)
		{}

• iterator 클래스 내부에 iterator 기본생성자와 인자를 받아서 그 받은 인자로 초기화해주는 생성자를 만들었다.

public:
	class iterator;
	iterator begin()
	{
		assert(m_Root);						// 1

		BSTNode<T1, T2>* pNode = m_Root;	// 2
        
		while (pNode->pLeftChild)			// 3
		{
			pNode = pNode->pLeftChild;		// 4
		}

		return iterator(this, pNode);		// 5
	};

• iterator 클래스 안에서 begin함수를 구현할것이다.
• 1번은 루트 노드가 없다면 assert 걸어서 막아줌.
• 2번은 노드 하나 생성해서 루트 노드에 대입함.
• 3번은 while문으로 노드를 왼쪽으로 계속 보낸다.
  • 왼쪽 자식이 없다면 조건이 거짓이 되서 반복문 안 돌아감.
• 4번은 왼쪽노드 담는 코드
• 5번은 begin iterator에 pNode에 담긴 처음 노드를 반환해준다.

	BST<int, float>::iterator myiter = bst.begin();

• begin 함수 테스트..

~BST(소멸자) 만들려면?

inline void BST<T1, T2>::Circit(BSTNode<T1, T2>* _Node)
{
	if (nullptr == _Node)
	{
		return;
	}
	//delete _Node;					// 1
	Circit(_Node->pLeftChild);
	//delete _Node;					// 2
	Circit(_Node->pRightChild);
	//delete _Node;					// 3
}

• 재귀함수 방식으로 모든 함수를 지울려면 1,2,3번중에 3번에 두어야 모든 노드를 삭제한다.
• 2번에 두면 왼쪽의 노드들만 지우고 오른쪽을 못지운다.
• 1번에 두면 방문하기도전에 루트 노드가 날라가서 나머지 아래 노드들을 삭제못시킨다.
• 재귀함수를 이용한 지우는건 직접 해보깅. delete Node구현해서 직접 해보깅.(주말)

재귀함수를 이용한 해제 단점 + 반복문 사용하는 이유

1. 효율성 문제: 재귀 함수를 사용하면 편리할 수 있지만, 이는 많은 연산을 필요로 하여 비효율적일 수 있습니다. 특히, 데이터의 양이 많을 경우, 각 데이터에 대해 함수 호출이 발생하므로 처리 효율이 떨어질 수 있습니다.

2. 반복문 사용의 이유: 소멸자(destructor)에서 모든 데이터에 접근하여 처리해야 하는 상황에서 반복문을 사용하는 것이 더 적절할 수 있습니다. 이는 재귀 함수를 사용할 때 발생하는 다수의 함수 호출을 줄임으로써 최적화를 가능하게 합니다.

3. 데이터 양의 불확실성: 데이터의 양이 불확실한 상황에서는 반복문을 사용하는 것이 더 유연하고 효율적인 해결책이 될 수 있습니다. 재귀 함수는 데이터 양에 따라 성능이 크게 달라질 수 있기 때문입니다.

레벨 순회

1. 레벨 순회의 개념: 레벨 순회는 트리의 각 레벨을 순서대로 방문하는 순회 방식입니다. 이는 트리의 루트 노드부터 시작하여, 각 레벨의 모든 노드를 왼쪽에서 오른쪽으로 방문합니다.

2. 구현 방법: 레벨 순회를 구현하기 위해 간단한 리스트 또는 큐(queue) 자료구조를 사용합니다. 루트 노드를 리스트의 첫 번째 요소로 넣고, 이 노드를 처리한 후 해당 노드의 자식 노드들을 리스트에 추가합니다. 이 과정을 모든 노드가 처리될 때까지 반복합니다.

3. 예시:

   • 루트 노드를 리스트에 넣습니다.
   • 루트 노드를 꺼내어 처리하고, 루트의 자식 노드들을 리스트에 추가합니다.
   • 다음 노드(루트의 첫 번째 자식)를 꺼내어 처리하고, 해당 노드의 자식을 리스트에 추가합니다.
   • 이러한 과정을 계속 반복하여 트리의 모든 레벨을 순회합니다.

4. 큐 자료구조의 중요성: 레벨 순회를 효율적으로 수행하기 위해서는 큐 자료구조가 필요합니다. 큐는 선입선출(FIFO: First-In, First-Out)의 특성을 가지며, 이 특성은 각 레벨의 노드를 순차적으로 처리하는 데 적합합니다.

• 레벨 순회는 트리의 각 레벨을 시스템적이고 체계적으로 방문할 수 있게 해주며, 이는 트리 구조의 데이터를 다루는 데 있어 중요한 순회 방법 중 하나입니다.

pop_front 함수 구현

• List.h 파일에 class List 안에서 구현중

T pop_front();

T pop_back();

• 맨앞의 데이터 펑하고 사리지게(삭제)하는것(백은 맨뒤)
• 데이터가 없어져버리는거니까 레퍼런스로 줄 수가 없다 줄 대상이 없어져서 복사로 밖에 못준다.

template<typename T>
T List<T>::pop_front()
{
	assert(m_pHead);
    
	T data = m_pHead->Data;

	if (nullptr == m_pHead->pNext)
	{
		delete m_pHead;
		m_pHead = nullptr;
		m_pTail = nullptr;
	}
	else
	{
		m_pHead = m_pHead->pNext;

		delete m_pHead->pPrev;

		m_pHead->pPrev = nullptr;
	}
	//m_pHead = m_pHead->pNext;
    
	//delete = m_pHead->pPrev;
	//m_pHead->pPrev = nullptr;

	--m_CurCount;

	return data;
}

• 코드 구현부분.

template<typename T>
T List<T>::pop_front()
{
	
}

• 구현할 코드를 넣을 공간이당.

	assert(m_pHead);

• 데이터를 삭제할건대 데이터 없으면 안되니까 그 경우 assert

	T data = m_pHead->Data;

• 헤드 노드가 들고있는 데이터를 지역변수(data)에 복사해둔다.(헤드 노드를 삭제할거니까.)

	m_pHead = m_pHead->pNext

• 지우기전에 헤드 주소를 다음 노드로 갱신한다.

	delete m_pHead->pPrev;

• 삭제시킨다. m_pHead의 pPrev지워버린다.

	m_pHead->pPrev = nullptr;

• 헤드의 프리뷰를 널로 막는다.
• 이전이 없어야 첫번쨰니까.

	if (nullptr == m_pHead->pNext)	// 1
	{
		delete m_pHead;				// 2

		m_pHead = nullptr;			// 3
		m_pTail = nullptr;			// 4
	}

• 위의 주석이 걸렸던 코드들을 다시 분기처리해서 나눔.
• 1번은 삭제할 헤드노드의 다음이 존재하지 않는다면(데이터가 1개였다)
• 2번은 헤드노드를 삭제한다
• 3,4번은 헤드와 테일 포인터를 nullptr로 막는다
  • 삭제한후 데이터는 0개니까 헤드와 테일 둘다 없는 상태.

	else
	{
		m_pHead = m_pHead->pNext;	// 1

		delete m_pHead->pPrev;		// 2

		m_pHead->pPrev = nullptr;	// 3
	}

• else는 1개 다음이 존재햇다면이라는 의미.
• 1번은 삭제할 헤드의 다음을 새로운 헤드로 지정한다.
• 2번은 새로지정한 헤드의 이전이 삭제할 원래 해드노드였다.
• 3번은 새로 지정한 헤드의 이전을 nullptr 만들었다.

	--m_CurCount;

• 데이터의 개수를 하나 줄인다.

	return data;

• 삭제한 헤드노드에 저장해두었던 데이터를 반환해준다.

우리가만든 리스트를 사용해서 레벨순회하기.

#include "List.h"

• BST.h에 우리가 만든 List.h에 리스트쓸거니 참조한다.

	~BST()
	{
		// 모든 노드들을 삭제
		List<BSTNode<T1, T2>*> queue;

		queue.push_back(m_Root);
        
		while (!queue.empty)
		{
			BSTNode < T1, T2 >* pNode = queue.pop_front();

			if (nullptr != pNode->pLeftChild)
				queue.pop_front(pNode->pLeftChild);

			if (nullptr != pNode->pRightChild)
				queue.pop_front(pNode->pRightChild);

			delete pNode;
		}

	}

• 코드 완성부분.

	List<BSTNode<T1, T2>*> queue;

• queue라는 리스트 객체를 만듬.
• 리스트에 저장할 데이터의 자료형이 BSTNode에 포인터 타입(주소)가 저장된다.

	queue.push_back(m_Root);

• 루트노드의 주소를 푸쉬_백해서 저장한다.

	// 6.2
	bool empty()
	{
      	// 1
		if (0 == m_CurCount)
			return true;
		else
			return false;
		// 2
		bool bReturn = false;
		0 == m_CurCount ? return true : return false;
		return bReturn;

		// 3
        return 0 == m_CurCount ? true : false;

	}

• List.h파일에 class List에 구현되어있는 empty함수
• 데이터가 0개면 true를 반환 1개 이상이면 false반환.
• 2번은 1번의 삼항연산자 버전
• 3번은 2번을 임시객체로 만들어서 그냥 리턴해버린것.

삼항연산자

• 체크문 ? 체크문 참이면 반환 : 체크문 거짓이면 반환

		while (!queue.empty)								// 1
		{
			BSTNode < T1, T2 >* pNode = queue.pop_front();	// 2
			if (nullptr != pNode->pLeftChild)				// 3
				queue.pop_front(pNode->pLeftChild);			// 4

			if (nullptr != pNode->pRightChild)				// 5
				queue.pop_front(pNode->pRightChild);		// 6

			delete pNode;									// 7
		}

• 반복문 도는 조건 queue(리스트객체)가 비어 있지 않을때
• 1번은 비어있지않다면 while문 돌고, 비어있다면 while끝낸다.
• 2번은 pop_front를해서 노드를 꺼내서 pNode지역변수에 대입하고 삭제한다.
• 3,4번은 왼쪽자식이 비어있지 않다면 왼쪽 노드를 삭제시킨다
• 5,6번은 오른쪽 자식이 비어있지 않다면 오른쪽 노드 삭제시킨다
• 7번 노드 삭제.

스택을 썻다면

		1
   2		3
4	 5    6    7

• 1을 꺼내고 역순으로 3,2번 (1 3 2)
• 스택이니까 2번을 끄낸다(역순)
• 2를 꺼내면 5,4번 (1 3 2 5 4)
• 4번을 끄내면 넣을게 없다
• 5번도 넣을게 없다
• 3번은 7번 6번을 넣는다.(1 3 2 5 4 7 6)
• 6번을 꺼내도 넣을게 없다
• 7번을 꺼내도 넣을게 없다.
• 접근하는 순서가 (1 2 4 5 3 6 7)이고 재귀함수랑 전휘랑 접근 방식이 유사하다.
• 깊이 우선탐색이당.
  • 리스트에 pop_back을 사용하면 스택처럼 사용가능

큐를 썻을떄.

• 레벨순회
  • 리스트에 pop_front를 사용하면 된다.
• 넓이 우선 탐색이라 본다.

a-stra 탐색 알고리즘

• 넓이 우선탐색(큐) + 깊이 우선 탐색(스택)의 장점만 취해서 만든 알고리즘이다.
  • 게임에서 길찾기 알고리즘.

iterator의 입장에서 ++ 구현하깅

• 중위 순회 기준으로 다음에 접근한다는게 쉽지만은 않다.
  • 규칙 찾기가 힘들다.

	public:
		iterator& operator ++()
		{
			if (m_TargetNode->HasRightChild())
			{
				BSTNode<T1, T2>* pNextNode = m_TargetNode->pRightChild;

				while (pNextNode->pLeftChild) { pNextNode = pNextNode->pLeftChild; }
				m_TargetNode = pNextNode;
			}
			else
			{
				BSTNode<T1, T2>* pNextNode = m_TargetNode;

				do {
					if (pNextNode->IsRoot())
					{
						// end iterator
						break;
					}
					else
					{
						pNextNode = pNextNode->pParent;
					}
				} while (!pNextNode->IsLeftChild())

					m_TargetNode = pNextNode->pParent;
			}
			return (*this);
		}

• 이진 탐색 트리의 중위순회 iterator다.

	iterator& operator ++()
    {
		return (*this);
	}
    iterator& operator --()
    {
    	return (*this);
    }

• 스스로를 리턴해야되서 iterator& 리턴은 자신을 넘김.
  • ++은 지금 --는 나중에 --도 심각하다.
• 규칙 찾기
  1. 오른쪽 자식으로 간다.
     1.1 왼쪽자식이 없을 떄 까지 내려간다.
  2. 오른쪽 자식이 없다면
     2.1 본인이 부모의 왼쪽 자식일떄 까지 올라간다.

	m_TargetNode = m_TargetNode->pParent->pLeftChild;

• 이런식으로 규칙을 하나하나 다 작성할거 아니면 저런 규칙하나하나를 노드에다 맴버함수로 만들어서 사용하자.

	// 1
	bool HasRightChild() { return pRightChild; }
	bool HasLeftChild() { return pLeftChild; }
	// 2
	bool IsLeftChild() { return pParent->pLeftChild == this; }
	bool IsRightChild() { return pParent->pRightChild == this; }
	// 3
	bool IsRoot() { return !pParent; }

• 1번은 내가 부모의 너가 오른쪽 자식이 있냐? 왼쪽 자식이 있냐? 물어보는것.
• 2번은 너가 부모의 왼쪽 자식이냐? 너가 부모의 오른쪽 자식이냐?
  • 부모의 왼쪽자식으로 가서 this랑 같으면 참 반환. 아니면 거짓 반환.
• 3번은 너 루트 노드냐? 부모의 존재 여부로 체크하면된다. 없으면 루트 노드다.

		if (m_TargetNode->HasRightChild())											// 1	
		{
			BSTNode<T1, T2>* pNextNode = m_TargetNode->pRightChild;					// 2

			while (pNextNode->pLeftChild) { pNextNode = pNextNode->pLeftChild; }	// 3 
			m_TargetNode = pNextNode;												// 4
		}

• 1번은 너 오른쪽 자식이 존재하면 if구문 실행
• 2번은 오른쪽 노드로 한번 내려간다.
• 3번은 왼쪽자식이 없을떄까지 내려가게 하는 반복문
• 4번은 모든 작업이 끝나면 내가 다음으로 가리켜야하는 노드니까 타켓노드를 다음 노드로 갱신한다.

			else
			{
				BSTNode<T1, T2>* pNextNode = m_TargetNode;
                // 1
				do {
					if (pNextNode->IsRoot())
					{
						// end iterator		// 2
						break;
					}
					else
					{
						pNextNode = pNextNode->pParent;
					}
				} while (!pNextNode->IsLeftChild())

					m_TargetNode = pNextNode->pParent;
			}

• else는 오른쪽 자식이 없을떄 실행한다.
• 1번은 부모의 왼쪽 자식일떄 까지 올라가서 그떄 부모가 나의 후속자.
• end iteraotr는 다음 수업떄 구현.

BST 클래스의 iterator& operator ++() 함수는 이진 탐색 트리에서 중위 순회(Inorder Traversal)를 수행하며 다음 노드로 이동하는 기능을 합니다. 중위 순회는 왼쪽 자식 - 현재 노드 - 오른쪽 자식 순서로 노드를 방문합니다. 이 함수의 로직은 다음과 같이 상세하게 설명될 수 있습니다:

iterator& operator ++() 정리

1. 현재 노드에 오른쪽 자식이 있는 경우

• 목표
  • 현재 노드(m_TargetNode)의 오른쪽 서브트리에서 중위 순회의 다음 노드를 찾습니다.
• 과정
  • m_TargetNode를 그 오른쪽 자식 노드로 이동합니다.
  • 이 노드로부터 시작하여, 계속 왼쪽 자식 노드로 이동합니다. 이 과정은 오른쪽 서브트리에서 가장 작은 값을 찾기 위한 것입니다.
  • 이동을 멈춘 노드가 중위 순회에서 현재 노드의 다음에 방문할 노드가 됩니다.

2. 현재 노드에 오른쪽 자식이 없는 경우

• 목표
  • 오른쪽 자식이 없다면, 중위 순회의 다음 노드는 현재 노드의 "상위" 노드 중 하나가 됩니다.
• 과정
  • 현재 노드에서 시작하여, 부모 노드를 향해 올라갑니다.
  • 올라가는 과정에서 현재 노드가 부모 노드의 왼쪽 자식이 되는 순간을 찾습니다. 이 순간의 부모 노드가 중위 순회에서 다음에 방문할 노드입니다.
  • 만약 루트 노드까지 도달한다면 (즉, 더 이상 올라갈 부모 노드가 없다면), 순회가 끝났음을 의미하고, 이터레이터는 "end" 상태가 됩니다.

예외 처리

• 루트 노드 처리
  • 만약 pNextNode가 루트 노드이면, 이는 순회가 끝났음을 나타내고, 반복문을 중단합니다.

함수 반환

• 함수는 수정된 m_TargetNode를 포함하는 this 이터레이터의 참조를 반환합니다. 이렇게 함으로써 이터레이터는 중위 순회의 다음 노드를 가리키게 됩니다.

강의 코드

#include <iostream>

#include "BST.h"

#include <set>
#include <map>
using std::set;
using std::map;
using std::make_pair;

int main()
{
	set<int> intset;

	intset.insert(100);

	intset.insert(150);
	intset.insert(170);
	intset.insert(125);

	intset.insert(80);
	intset.insert(90);
	intset.insert(50);

	set<int>::iterator iter = intset.find(125);
	iter = intset.find(124);
	if (iter != intset.end())
	{

	}
	else
	{

	}

	// map 사용
	map<int, int> intmap;

	intmap.insert(make_pair(100, 1));

	intmap.insert(make_pair(150, 2));
	intmap.insert(make_pair(170, 3));
	intmap.insert(make_pair(125, 4));

	intmap.insert(make_pair(80, 5));
	intmap.insert(make_pair(90, 6));
	intmap.insert(make_pair(50, 7));

	map<int, int>::iterator mapiter = intmap.find(50);

	if (mapiter != intmap.end())
	{
		(*mapiter).first;
		(*mapiter).second;
	}

	// BST insert 테스트
	BST<int, float> bst;
	bst.insert(make_bstpair(100, 1.1f));
	bst.insert(make_bstpair(150, 2.2f));
	bst.insert(make_bstpair(50, 2.2f));
	bst.insert(make_bstpair(170, 1.1f));
	bst.insert(make_bstpair(125, 2.2f));
	bst.insert(make_bstpair(25, 2.2f));
	bst.insert(make_bstpair(75, 2.2f));

	bst.Circit();
    // main에 추가된 코드 단 한줄.
	BST<int, float>::iterator myiter = bst.begin();


	return 0;
}

BST.h

#pragma once

#include <iostream>
#include <assert.h>

#include "List.h"



// Binary Search Tree(BST)
template<typename T1, typename T2>
struct BSTPair
{
	T1 first;
	T2 second;

	BSTPair()
	{}

	BSTPair(const T1& _first, const T2& _second)
		: first(_first)
		, second(_second)
	{
	}
};

template<typename T1, typename T2>
struct BSTNode
{
	BSTPair<T1, T2> pair;

	BSTNode* pParent;
	BSTNode* pLeftChild;
	BSTNode* pRightChild;

	bool HasRightChild() { return pRightChild; }
	bool HasLeftChild() { return pLeftChild; }

	bool IsLeftChild() { pParent->pLeftChild == this; }
	bool IsRightChild() { pParent->pRightChild == this; }

	bool IsRoot() { return !pParent; }


	BSTNode()
		: pParent(nullptr)
		, pLeftChild(nullptr)
		, pRightChild(nullptr)
	{}

	BSTNode(const BSTPair<T1, T2>& _pair, BSTNode* _Parent = nullptr, BSTNode* _LeftChild = nullptr, BSTNode* _RightChild = nullptr)
		: pair(_pair)
		, pParent(_Parent)
		, pLeftChild(_LeftChild)
		, pRightChild(_RightChild)
	{}
};

template<typename T1, typename T2>
class BST
{
private:
	BSTNode<T1, T2>* m_Root;		// 루트 노드 주소
	int					m_CurCount;	// 현재 데이터 개수

public:
	void insert(const BSTPair<T1, T2>& _pair);

public:
	void Circit()
	{
		Circit(m_Root);
	}

private:
	void Circit(BSTNode<T1, T2>* _Node);

public:
	class iterator;
	iterator begin()
	{
		assert(m_Root);

		BSTNode<T1, T2>* pNode = m_Root;

		while (pNode->pLeftChild) { pNode = pNode->pLeftChild; }

		return iterator(this, pNode);
	}

	//iterator end();
	//iterator find(const T1& _key);



public:
	BST()
		: m_Root(nullptr)
		, m_CurCount(0)
	{}

	~BST()
	{
		// 모든 노드들을 삭제
		// 재귀함수		

		// 레벨순회
		List<BSTNode<T1, T2>*> queue;

		queue.push_back(m_Root);

		while (!queue.empty())
		{
			BSTNode<T1, T2>* pNode = queue.pop_front();

			if (nullptr != pNode->pLeftChild)
				queue.push_back(pNode->pLeftChild);

			if (nullptr != pNode->pRightChild)
				queue.push_back(pNode->pRightChild);

			delete pNode;
		}
	}


	class iterator
	{
	private:
		BST* m_Owner;
		BSTNode<T1, T2>* m_TargetNode;

	public:
		iterator& operator ++()
		{
			// 오른쪽 자식이 있으면 
			if (m_TargetNode->HasRightChild())
			{
				// 오른쪽 자식으로 간다.
				BSTNode<T1, T2>* pNextNode = m_TargetNode->pRightChild;

				// 왼쪽자식이 없을 때 까지 내려간다.
				while (pNextNode->pLeftChild) { pNextNode = pNextNode->pLeftChild; }
				m_TargetNode = pNextNode;
			}

			// 오른쪽 자식이 없으며
			else
			{
				BSTNode<T1, T2>* pNextNode = m_TargetNode;

				// 부모의 왼쪽 자식일때 까지 올라가서 그때 부모가 나의 후속자
				do {
					if (pNextNode->IsRoot())
					{
						// end iterator
						break;
					}
					else
					{
						pNextNode = pNextNode->pParent;
					}
				} while (!pNextNode->IsLeftChild())

					m_TargetNode = pNextNode->pParent;
			}

			return (*this);
		}

		iterator& operator--()
		{



			return (*this);
		}






	public:
		iterator()
			: m_Owner(nullptr)
			, m_TargetNode(nullptr)
		{}

		iterator(BST* _Owner, BSTNode<T1, T2>* _Node)
			: m_Owner(_Owner)
			, m_TargetNode(_Node)
		{}
	};
};

// 입력된 T1, T2 타입의 데이터를 묶어서 BSTPair<T1, T2> 타입 구조체로 반환
template<typename T1, typename T2>
BSTPair<T1, T2> make_bstpair(const T1& _first, const T2& _second)
{
	return BSTPair<T1, T2>(_first, _second);
}


template<typename T1, typename T2>
void BST<T1, T2>::insert(const BSTPair<T1, T2>& _pair)
{
	BSTNode<T1, T2>* pNewNode = new BSTNode<T1, T2>(_pair);

	// 최초로 데이터가 입력된 상황
	if (nullptr == m_Root)
	{
		m_Root = pNewNode;
	}

	// 데이터가 2개 이상인 경우
	else
	{
		BSTNode<T1, T2>* pNode = m_Root;

		while (true)
		{
			// 입력된 first 값이 현재 노드의 first 값보다 작은 경우
			if (pNewNode->pair.first < pNode->pair.first)
			{
				// 왼쪽이 비어있으면
				if (nullptr == pNode->pLeftChild)
				{
					// 현재 노드의 왼쪽으로 연결
					pNode->pLeftChild = pNewNode;
					pNewNode->pParent = pNode;
					break;
				}

				// 왼쪽으로 내려간다.
				pNode = pNode->pLeftChild;
			}

			// 입력된 first 값이 현재 노드의 first 값보다 큰 경우
			else if (pNode->pair.first < pNewNode->pair.first)
			{
				// 현재 노드의 오른쪽이 비어있으며
				if (nullptr == pNode->pRightChild)
				{
					// 입력된 노드를 현재 노드의 오른쪽으로 연결
					pNode->pRightChild = pNewNode;
					pNewNode->pParent = pNode;
					break;
				}

				// 오른쪽으로 내려간다.
				pNode = pNode->pRightChild;
			}
		}
	}

	++m_CurCount;
}

template<typename T1, typename T2>
inline void BST<T1, T2>::Circit(BSTNode<T1, T2>* _Node)
{
	if (nullptr == _Node)
	{
		return;
	}

	Circit(_Node->pLeftChild);

	//std::cout << _Node->pair.first << std::endl;

	Circit(_Node->pRightChild);
}

List.h 일부분

// 클래스 내부
	T pop_front();
	T pop_back();

	bool empty()
	{
		return 0 == m_CurCount ? true : false;
	}
 // 클래스 내부
 
template<typename T>
T List<T>::pop_front()
{
	assert(m_pHead);

	// 헤드노드가 들고있는 데이터를 복사해둔다.
	T data = m_pHead->Data;

	// 삭제할 헤드노드의 다음이 존재하지 않는다면 (데이터가 1개였다)
	if (nullptr == m_pHead->pNext)
	{
		// 헤드노드를 삭제한다.
		delete m_pHead;

		// 헤드, 테일 포인터를 nullptr 로 만든다.
		m_pHead = nullptr;
		m_pTail = nullptr;
	}
	else
	{
		// 삭제할 헤드의 다음을 새로운 헤드로 지정한다.
		m_pHead = m_pHead->pNext;

		// 새로지정한 헤드의 이전이 삭제할 원래 해드노드였다.
		delete m_pHead->pPrev;

		// 새로 지정한 헤드의 이전을 nullptr 만든다.
		m_pHead->pPrev = nullptr;
	}

	// 데이터 개수를 하나 줄인다.
	--m_CurCount;

	// 삭제한 헤드노드에 저장해두었던 데이터를 반환해준다.
	return data;
}

template<typename T>
T List<T>::pop_back()
{

	return T();
}
    

1차 24.01.05
2차 24.01.09
3차 24.01.10
4차 24.01.11
5차 24.01.12