이진 탐색 트리 (4)

Yama·2024년 1월 8일
C/C++어소트락 취업반
0

어소트락 수업

목록 보기
37/55

CArr.h에서 ++,-- 전위후위 구현 과제 코드

전위 ++

		iterator& operator ++()
		{
			if (m_pOwner && -1 == m_Idx)
			{
				assert(nullptr);				// 1
			}

			++m_Idx;

			if (m_pOwner->m_CurCount <= m_Idx)	// 2
			{
				m_Idx = -1;
			}

			return (*this);
		}
  • 1번은 end iterator에서 ++함수를 호출한 경우
  • 2번은 end iterator - iterator 가 컨테이너가 보유한 데이터의 마지막 다음을 가리키는 상태

후위 +++

		iterator operator ++(int)
		{
			iterator copyiter = (*this);
			++(*this);
			return copyiter;
		}

전위 --

		iterator& operator --()
		{
			assert(m_pOwner && m_Idx);				// 1

			if (-1 == m_Idx)						// 2
			{
				assert(m_pOwner->m_CurCount);		// 3

				// 가장 마지막 데이터를 가리킨다.
				m_Idx = m_pOwner->m_CurCount - 1;	// 4		
            }
			else
			{
				--m_Idx;							// 5
			}

			return (*this);
		}
  • 1번은 iterator가 정상적인 상태가 아니거나, begin iterator인 경우
    • 정상적인 상태가 아니다는 담당 컨테이너가 없다.(어떤 요소도 없다.)
    • m_Idx가 begin인 이유는 어차피 인덱스가 0이면 begine iterator이니까 assert에 걸린다.
  • 2번은 만약 end iterator 에게 --를 호출한 경우
    • 4번은 가장 마지막 데이터를 가리킨다.
      • 3번은 데이터가 하나도 없는데 마지막 데이터를 가리킬려고 하는 경우를 assert로 막는다.
  • 5번은 일반적인 경우 걍 인덱스 -- 시킨다.

후위 --

		iterator operator --(int)
		{
			iterator copyiter = *this;
			--(*this);
			return copyiter;
		}

참고: 전위 순회(PreOrder), 중위 순회(In Order), 후위 순회(Post Order)

중위 후속자 : In Order successor : 중위순회 기준 후속 노드.

end iterator 조건

  • m_Owner 가 nullptr이 아니고 m_TargetNode가 nullptr 일떄

iteratro에 operator == 구현

		bool operator ==(const iterator& _otheriter)
		{
			if (m_Owner == _otheriter.m_Owner && m_TargetNode == _otheriter.m_TargetNode)
			{
				return true;
			}
			return false;
		}
  • 기존과, 타켓순번도 같아야 같다는거다.
  • 내 기존 맴버랑 기존맴버가 일치하고 내가 가리키고 잇는 대상의 주소값이랑 _otheriter가 가리키는 타켓노드의 주소값이 같으면 같은 iterator 상태다.

iterator operator != 구현

		bool operator !=(const iterator& _otheriter)
		{
			return !((*this) == _otheriter);
		}
  • 전체 비교 연산의 결과를 뒤집으면 된다.

end iterator 만들기.

end iterator 조건

  • m_Owner 가 nullptr이 아니고 m_TargetNode가 nullptr 일떄
	iterator end()
	{
		return iterator(this, nullptr);
	}
  • 해당 컨테이너를 this로 가리키면서 실제 데이터 노드는 nullptr을 가리키고 있다면 end다.
	for (; myiter != bst.end(); ++myiter)
	{
		cout << (*myiter).first << endl;
  • 반복문돌면서 출력하기.
    • 구현을 안해놔서 오류.
// 클래스 iterator에 구현되있다.
		const BSTPair<T1, T2>& operator* ()
		{
			assert(m_Owner && m_TargetNode);

			return m_TargetNode->pair;
		}

  • 근데 우리 이진탐색트리는 기존의 동적 배열이랑 리스트랑 다르게 템플릿형식으로 짝지어서 2개 받았다(pair)

  • iterator 입장에서도 *(별)을 붙이면 다른 iterator랑 다르게 pair형태로 반환을 해줘야한다.

  • 반환타입을 그래서 BSTPair<T1, T2>로 주고 원본자체를 받을거니까 &(레퍼런스)로 했다.

  • const로 수정을 못하게한 이유

    			//			    100(xx) 30
			//		 50				150
			//	  25	75		125		170
    • 100을 30으로 수정을 한다면 입력되면서 정렬되었던게 다 깨져버리기 때문에 const로 수정을 막는다.

  • 복사된 비용을 레퍼런스로 최적화 시키고 const로 막아서 원본 수정못하게 한다.

  • assert는 end iterator이거나 m_Owner가 nullptr일떄 *(별)을 호출하면 말 안되니까 둘중하나라도 0이면 assert를 걸었다.

  • 구현을 했기 때문에 위의 오류가 해결된다.

중위 후속자 operator ++ 코드 수정

		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;

				// 1.1
				// 부모의 왼쪽 자식일때 까지 올라가서 그때 부모가 나의 중위 후속자
				while (true)
				{
					// 루트 노드라면 if문 나가기.
					// 본인이 이미 루트 노드라면 나는 end iterator였다.
					if (pNextNode->IsRoot())
					{
						// 현재 노드가 가장 마지막 노드이다(중위 후속자를 찾기전에 루트노드에 도달)
						// end iterator
						m_TargetNode = nullptr;
						return (*this);
					}
					// 올라갈수잇는 상황이고 본인이 왼쪽 자식인지 확인하고 내가 왼쪽이네 그러면 중위후속자다.
					else if(pNextNode->IsLeftChild())
					{
						m_TargetNode = pNextNode->pParent;
						break;
					}
					// 그것도 아니라면 왼쪽까지 계속 올라가서 올라간다.
					else
					{
						pNextNode = pNextNode->pParent;
					}
				} 

					m_TargetNode = pNextNode->pParent;
			}

			return (*this);
		}
  • 이진 탐색 트리 (3)에 있는 코드에서 else이후부터 수정.

find 함수

// BST 클래스 안에 있다.
	iterator find(const T1& _key);
  • 이진 탐색 트리에서 데이터가 있냐 없냐
  • 데이터를 꺼내올수도 있어야 된다.
  • find는 있으면 그 iterator 없다면 end iterator 반환했었당.
    • 반환타입을 iterator로 주면 두가지 상황을 다 커버할수 있다.
  • 입력인자로는 정렬의 기준이 이 T1타입으로 되있기 때문에 내가 찾을려는 T1 타입의 값을 인자로 알아야 한다.
  • insert랑 비슷하다 들어간 값이랑 비교를했고 find은 키값이랑 비교하기 때문에 과정이 유사하다.
template<typename T1, typename T2>
typename BST<T1, T2>::iterator BST<T1, T2>::find(const T1& _key)
{
	BSTNode<T1, T2>* pNode = m_Root;

	while (pNode)
	{
		if (_key < pNode->pair.first)
		{
			pNode = pNode->pLeftChild;
		}
		else if (pNode->pair.first < _key)
		{
			pNode = pNode->pRightChild;
		}
		else
		{
			break;
		}
	}
	return iterator(this, pNode);
}
  • 실제 함수 정의부분.
	m_Root->pair.first; 
    _key;
  • 저 정의부분은 first랑 인자로 받아온 _key의 값이랑 비교하면 된다.
	BSTNode<T1, T2>* pNode = m_Root;
  • 노드 포인터 하나(pNode) 만들어서 그걸 루트부터 출발시킨다.
		if (nullptr == pNode)
		{
			return end();
		}
  • 더이상 내려갈 데가 없다면 end 이터레이터 주면된다.
		if (_key < pNode->pair.first)
		{
			pNode = pNode->pLeftChild;
		}
  • 키값이 입력으로 들어온 값이 pNode첫번째 값보다 작다면.
  • pNode 왼쪽 노드값(작은값)으로 갱신시킨다.
		else if (pNode->pair.first < _key)
		{
			pNode = pNode->pRightChild;
		}
  • 키값이 입력으로 들어온 값이 pNode첫번째 값보다 크다면
  • pNode의 오른쪽(큰값)으로 pNode를 갱신 시킨다.
while(true)
{
		if (nullptr == pNode)
		{
			return end();
		}
        else if (_key < pNode->pair.first)
		{
			pNode = pNode->pLeftChild;
		}
        else if (pNode->pair.first < _key)
		{
			pNode = pNode->pRightChild;
		}
}

return iterator();
  • 저걸 반복해야되니 반복문을 쓴다.
	else
    {
    	return iterator(this, pNode)
	}
  • else인 경우 pNode->pair.first == _key 같다는 조건인데 else라 걍 생략.
while(true)
{
		if (nullptr == pNode)
		{
			return end();
		}
        else if (_key < pNode->pair.first)
		{
			pNode = pNode->pLeftChild;
		}
        else if (pNode->pair.first < _key)
		{
			pNode = pNode->pRightChild;
		}
        else
    	{
    		return iterator(this, pNode)
		}
}

return iterator();
  • 이런식의 코드지만 저 맨아래 return은 필요가없어짐 그래서 걍 while수정
	while (pNode)
	{
		if (_key < pNode->pair.first)
		{
			pNode = pNode->pLeftChild;
		}
		else if (pNode->pair.first < _key)
		{
			pNode = pNode->pRightChild;
		}
		else
		{
			break;
		}
	}
	
    return iterator(this, pNode);
  • 이렇게 수정가능
	myiter = bst.find(75);
    myiter = bst.find(74);
  • find 함수 테스트
    • 타켓노드가 75잘 가르키고잇다.
    • 타켓노드가 end iterator가르키고있당.

지금까지 우리가 정한 규칙으로 end를 나타냈기때문에 가독성을 위해 메모리 조금 더 쓸수 있다.

// iterator 안에 있다.
	private:
		BST*				m_Owner;
		BSTNode<T1, T2>*	m_TargetNode;
		wchar_t				m_szDesc[6];		// 1
  • 설명할 문자열 공간을 추가한다. 
	public:
		iterator()
			: m_Owner(nullptr)
			, m_TargetNode(nullptr)
			, m_szDesc{}
		{
			wcscpy_s(m_szDesc, L"None");
		}
  • 기본 생성자 생성될떄 None가 추가됨.
		iterator(BST* _Owner, BSTNode<T1, T2>* _Node)
			: m_Owner(_Owner)
			, m_TargetNode(_Node)
			, m_szDesc{}
		{
			if (nullptr != m_Owner && nullptr == m_TargetNode)
			{
				wcscpy_s(m_szDesc, L"End");
			}
		}
  • end 이터레이터 일떄 보여주는것. 구현해서 가독성을 늘려줌.

이진 탐색 트리의 erase 만들깅.

  • erase함수가 iterator타입을 을 반환시킨 이유
    • 데이터를 삭제시키고 삭제시킨 다음 데이터의 iterator을 줘서 다음에 쓸수있게 하기위해서.
  • 리스트는 삭제가 쉬웠당 트리구조에서는 뭔가 모호하다.
    • 기준이 있어야 한다.
    • 자식의 수로 기준을 잡을 것.
  • 자식이 0,1,2개던 erase하고 나서 후속조치를 했을떄 중위순회를 했을 경우 여전히 정렬 규칙이 깨지면 안된다.
// BST 클래스 public내부에 선언
	iterator erase(const iterator& _target);
  • 선언부.
	friend class BST<T1, T2>;
  • 이너클래스인 iterator이니까 iterator클래스안에 BST친구로 허용해서 private접근하게해준다.
// struct BSTNode 안에 있다.
	// 1
	bool IsLeaf() { return !(pLeftChild || pRightChild); }
	// 2
	bool IsFull() { return pLeftChild&& pRightChild; }
  • 1번은 말단 노드일떄 ||로 엮어서 둘다 0,0이여야 0이 되서 역을해서 말단 노드인걸 전달함.
  • 2번은 자식이 둘다 있을떄를 반환함.
template<typename T1, typename T2>
typename BST<T1, T2>::iterator BST<T1, T2>::erase(const iterator& _target)
{
	// 삭제할 노드가 리푸노드인 경우 (자식이 0개)
	if (_target.m_TargetNode->IsLeaf())
	{

	}
	// 자식이 2개 있는 경우
	else if (_target.m_TargetNode->IsFull())
	{

	}
	// 자식이 1개 있는 경우
	else
	{

	}

	return iterator();
}
  • 자식이 1개인 경우는 조건이 너무 많고복잡(거지같아서)해서 자식0개일때 2개일떄만 조건 처리해놓고 else로 처리해버린다.

강의코드

main.cpp

#include <iostream>

using std::cout;
using std::endl;

#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<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();
	BST<int, float>::iterator myiter = bst.begin();
	for (; myiter != bst.end(); ++myiter)
	{
		cout << (*myiter).first << endl;
	}

	myiter = bst.find(74);

	BST<int, float>::iterator TestIter;

	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() { return pParent->pLeftChild == this; }
	bool IsRightChild() { return pParent->pRightChild == this; }

	bool IsRoot() { return !pParent; }
	bool IsLeaf() { return !(pLeftChild || pRightChild); }
	bool IsFull() { return pLeftChild && pRightChild; }

	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 Circit()
	{
		Circit(m_Root);
	}

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

public:
	class iterator;

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

	iterator find(const T1& _key);

	iterator erase(const iterator& _target);

	iterator begin()
	{
		assert(m_Root);

		BSTNode<T1, T2>* pNode = m_Root;

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

		return iterator(this, pNode);
	}

	iterator end()
	{
		return iterator(this, nullptr);
	}


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;
		wchar_t				m_szDesc[6];	// 설명 정보
		// end iterator 조건
		// m_Owner 가 nullptr 이 아니고 m_TargetNode 가 nullptr 이면...

	public:
		const BSTPair<T1, T2>& operator* ()
		{
			assert(m_Owner && m_TargetNode);

			return m_TargetNode->pair;
		}


		bool operator == (const iterator& _otheriter)
		{
			if (m_Owner == _otheriter.m_Owner && m_TargetNode == _otheriter.m_TargetNode)
			{
				return true;
			}
			return false;
		}

		bool operator != (const iterator& _otheriter)
		{
			return !((*this) == _otheriter);
		}


		iterator& operator ++()
		{
			// 중위 후속자(InOrder Successor)

			// 오른쪽 자식이 있으면 
			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;

				// 부모의 왼쪽 자식일때 까지 올라가서 그때 부모가 나의 중위 후속자
				while (true)
				{
					if (pNextNode->IsRoot())
					{
						// 현재 노드가 가장 마지막 노드이다(중위 후속자를 찾기전에 루트노드에 도달)
						// end iterator
						m_TargetNode = nullptr;
						wcscpy_s(m_szDesc, L"End");
						return (*this);
					}
					else if (pNextNode->IsLeftChild())
					{
						m_TargetNode = pNextNode->pParent;
						break;
					}
					else
					{
						pNextNode = pNextNode->pParent;
					}
				};
			}

			return (*this);
		}

		iterator& operator--()
		{
			// 중위 선행자(InOrder Predecessor)


			return (*this);
		}

	public:
		iterator()
			: m_Owner(nullptr)
			, m_TargetNode(nullptr)
			, m_szDesc{}
		{
			wcscpy_s(m_szDesc, L"None");
		}

		iterator(BST* _Owner, BSTNode<T1, T2>* _Node)
			: m_Owner(_Owner)
			, m_TargetNode(_Node)
			, m_szDesc{}
		{
			if (nullptr != m_Owner && nullptr == m_TargetNode)
			{
				wcscpy_s(m_szDesc, L"End");
			}
		}
		friend class BST<T1, T2>;
	};
};

// 입력된 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);
}

template<typename T1, typename T2>
typename BST<T1, T2>::iterator BST<T1, T2>::find(const T1& _key)
{
	BSTNode<T1, T2>* pNode = m_Root;

	while (pNode)
	{
		if (_key < pNode->pair.first)
		{
			pNode = pNode->pLeftChild;
		}
		else if (pNode->pair.first < _key)
		{
			pNode = pNode->pRightChild;
		}
		else
		{
			break;
		}
	}
	return iterator(this, pNode);
}

template<typename T1, typename T2>
typename BST<T1, T2>::iterator BST<T1, T2>::erase(const iterator& _target)
{
	// 삭제할 노드가 리프노드인 경우 (자식이 0개)
	if (_target.m_TargetNode->IsLeaf())
	{

	}

	// 자식이 2개 있는 경우
	else if (_target.m_TargetNode->IsFull())
	{

	}

	// 자식이 1개 있는 경우
	else
	{

	}

	return iterator();
}

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

profile
Yama
:D
이전 포스트

이진 탐색 트리 (3)

0개의 댓글