이진탐색
1. 정렬되어있는 데이터에 적용가능
이진탐색트리
1. 이진 탐색을 사용할 수 있게 고안된 이진트리
2. 데이터 입력 시 O(logN) 효율
3. 탐색 효율은 O(logN)
4. 트리의 모양이 밸런스가 유지되지 않으면 제대로 된 탐색 효율이 나오지 않는다.
- 자가균형 기능 필요(AVL, Red/Black)
- Tree 기능 알아보기
#include <iostream>
#include <map>
#include <set>
#include <string> // 기본적으로 제공되는 문자열 클래스를 사용하기 위해 선언
using std::wcout;
using std::endl;
using std::map;
using std::make_pair;
using std::set;
using std::wstring; // 주소값이 아닌 문자열로 비교를 하고 싶을 때 map의 첫번째 타입을
// 문자의 클래스 타입으로 넣어줘야 한다.
#define MAN 1
#define WOMAN 2
struct tStdInfo
{
wchar_t szName[20];
unsigned char age;
unsigned char gender;
tStdInfo()
: szName{}
, age(0)
, gender(0)
{
}
tStdInfo(const wchar_t* _pName, unsigned char _age, unsigned char _gender)
: szName{}
, age(_age)
, gender(_gender)
{
wcscpy_s(szName, _pName); // 원본을 저장할 목적지, 원본(받은 이름)
}
};
int main()
{
set<int> setInt; // 레드블랙 트리를 생각하면 된다.
// 자주 쓰이진 않는다. 이것 대신에 주로 map을 사용한다.
setInt.insert(100);
setInt.insert(50);
setInt.insert(150);
const wchar_t* pStr = L"문자열";
wchar_t szArr[100] = L"ab";
map<const wchar_t*, tStdInfo> mapData;
tStdInfo info(L"홍길동", 18, MAN);
tStdInfo info2(L"김이박", 24, WOMAN);
mapData.insert(make_pair(L"홍길동", info)); // 두 개를 하나의 짝으로 만들어 저장
mapData.insert(make_pair(L"김이박", info2));
map<const wchar_t*, tStdInfo>::iterator mapiter;
mapiter = mapData.find(L"홍길동"); // key(이름, 정확히 말하면 주소값) 값을 넣어서
// value(pair)를 가리키는 이터레이터를 반환한다.
// 이때 이테레이터가 가리키는 pair는
// 그냥 데이터가 아니라 구조체 형태이다.
// map<const wchar_t*, tStdInfo> <- 형태
// 따라서 구조체 안의 멤버에 각각 접근해야 한다.
// 구조체 + (.)으로 해당 멤버에 각각 접근
// (*mapiter).first;
// (*mapiter).second;
// 포인터는 아니지만 포인터처럼 -> 을 통해 역참조 가능
// mapiter->first;
_wsetlocale(LC_ALL, L"korean");
// 만약 key 값을 넣었을 때 이에 대응되는 주소의 pair가 없다면 (= 찾지 못했다면)
if (mapiter == mapData.end())
{
wcout << L"데이터를 찾을 수 없다." << endl;
}
else // 찾았다면
{
wcout << L"이름 : " << mapiter->second.szName << endl;
wcout << L"나이 : " << mapiter->second.age << endl;
wcout << L"성별 : " << endl;
if (MAN == mapiter->second.gender)
{
wcout << L"남자" << endl;
}
else if (WOMAN == mapiter->second.gender)
{
wcout << L"남자" << endl;
}
else
{
wcout << L"알 수 없음" << endl;
}
}
map<wstring, tStdInfo> mapStdInfo;
wstring str; // 문자열 클래스는 사용자가 넣어주는 문자를 자체적으로 들고 있다
str = L"abcdef";
str += L"hijk"; // 문자열 추가
str = L"ABCDEFGHIJKLMOP"; // 대입으로 이전 내용을 모두 덮어버림
// 이러한 추가, 대입이 자유롭게 가능하다는 것은
// wstring이 메모리 구조를 동적 할당으로 관리한다는 뜻
// 즉, 가변 배열과 비슷함
// 또한 키 값은 단순한 문자의 비교가 아닌 주소의 일치 여부에 따라 작동하기 때문에
// 사용자가 직접 만든 일반 가변 배열로는 find 함수로 값을 찾아 낼 수 없다.
// 비교 연산자가 구현되어 있는 클래스들만 map의 키로 사용할 수 있다.
// 그래야만 트리의 노드들 간의 크기를 비교해서 정렬 배치할 수 있기 때문이다.
// (이진 탐색 트리의 실행을 위한 선행 조건 : 데이터가 정렬 되어 있어야 한다.)
return 0;
}
struct pair
{
const wchar_t* first;
tStdInfo second;
};
- 이진 탐색 트리(map) 직접 구현하기
#pragma once
// <map 구현하기>
// map과 유사하게 만들려면 실제 key 값으로 사용할 타입을 지정받아야하고 (T1)
// 따로 넣어 줄 두 번째 세컨드 데이터 타입(pair)에 대한 타입 역시 지정 받아야 한다. (T2)
template <typename T1, typename T2>
struct tPair
{
T1 first;
T2 second;
};
template <typename T1, typename T2>
class tBSTNode
{
tPair<T1, T2> pair;
tBSTNode* pParent;
tBSTNode* pLeftChild;
tBTSNode* pRightChild;
// data
// 부모노드
// 자식노드
};
template <typename T1, typename T2>
class CBST
{
private:
tBSTNode<T1, T2>* m_pRoot; // 루트 노드 주소
int m_iCount; // 데이터 개수
public:
bool insert(const tPair<T1, T2>& _pair);
};
template<typename T1, typename T2>
inline bool CBST<T1, T2>::insert(const tPair<T1, T2>& _pair)
{
tBSTNode<T1, T2>* pNewNode = new tBSTNode<T1, T2>();
PNewNode->pair = _pair;
pNewNode->pParent = nullptr;
pNewNode->pLeftChild = nullptr;
pNewNode->pRightChild = nullptr;
// 첫번째 데이터라면 그것을 root 노드로 설정
if (nullptr == m_pRoot)
{
m_pRoot = pNewNode;
}
else // 이미 root 노드가 증가한다면 반복문을 이용해서 본인의 자리를 찾을 때까지 작업을 반복.
{
// 이때 root 노드의 값은 바뀌면 안되므로 지역 변수를 사용해 저장함
tBSTNode<T1, T2>* pNode = m_pRoot;
while (true)
{
// 현재 비교 중인 노드와의 우열 관계를 따지면서 계속 내려간다.
if (pNode->pair.first < pNewNode->pair.first) // 만약 현재 root 노드의 pair의 first 값보다
// 새로운 노드의 값이 큰 경우
{
if (nullptr == pNode->pRightChild)
{
pNode->pRightChild = pNewNode;
pNewNode->pParent = pNode;
break;
}
else
{
pNode = pNode->pRightChild; // 더 값이 큰 쪽이 오른쪽으로 가므로
// 오른쪽 포인터를 갱신한다.
}
}
else if (pNode->pair.first < pNewNode->pair.first) // 반대의 경우
{
if (nullptr == pNode->pLeftChild)
{
pNode->pLeftChild = pNewNode;
pNewNode->pParent = pNode;
break;
}
else
{
pNode = pNode->pLeftChild;
}
}
else // 각 노드가 서로 같은 값을 가진 경우
// map에서 이런 중복되는 키값의 허용 여부에 따라 종류가 나뉜다.
// 일반적인 맵은 중복키값을 허용하지 않는다. 허용하는 맵은 멀티맵이라고 한다.
{
// 일반 맵에서는 중복된 값을 트리 안에 넣지 않는 규칙이 있으므로
// 오류를 방지하기 위해 미리 find로 같은 키가 있는지 확인해보고
// 동일한 키가 있으면 값을 무시한다.
// 따라서 false 값을 리턴해준다.
return false;
}
}
}
// 데이터 개수 증가
++m_iCount;
}
현재 while문 내부를 보면 오른쪽, 왼쪽 노드로 나눠지는 부분이 비슷하게 대칭을 이루고 있는 것을 볼 수 있다.
이것을 더욱 간결하게 구현하기 위해서 enum을 사용해보자.
- enum
열거형이라고 부른다.
원하는 이름을 나열하면 컴파일러는 나열된 이름을 0부터 시작한 연속된 숫자로 받아들인다.
enum MY_TYPE
{
TYPE_1, // 0
TYPE_2, // 1
TYPE_3. // 2
};
따라서 선언된 enum 멤버를 호출하면 그 멤버에 대응되는 숫자가 대입된다.
int a = TYPE_3; // 2가 대입된다.
enum 안에 선언한 이름은 따로 값을 정해주는 것도 가능하다.
만약 지정된 숫자 이후에 오는 값들에 따로 값을 명시하지 않으면 이전에 명시한 이름부터 차례로 1씩 늘어난다.
enum MY_TYPE
{
TYPE_1, // 0
TYPE_2, // 1
TYPE_3, // 2
TYPE_4, // 3
TYPE_5 = 100,
TYPE_6, // 101 이 대입된다
};
또한 서로 다른 enum 간에는 멤버 이름의 중복이 허용된다.
단, 이 경우 이름만 호출했을 때 어느쪽 enum의 멤버인지 모호해져 재정의 오류가 발생한다.
이 때는 enum class 라는 것을 사용해 호출시 enum의 이름까지 함께 알려주어야 한다.
최근 컴파일러에서는 일반 enum 사용시 enum class를 사용할 것을 경고한다.
따라서 웬만해서는 enum class를 사용하도록 하자.
enum MY_TYPE
{
TYPE_1, // 0
TYPE_2, // 1
TYPE_3, // 2
TYPE_4, // 3
TYPE_5 = 100,
TYPE_6, // 101 이 대입된다
};
enum class OTHER_TYPE
{
TYPE_10,
};int a = MY_TYPE::TYPE_1;
주의해야 할 점은 enum은 별개의 새로운 자료형으로 보기 때문에, 안에 할당된 값을 정수로 바꾸고 싶을 때는
반드시 아래와 같이 명시적으로 캐스팅을 해주어야 한다.
int a = (int)MY_TYPE::TYPE_1;
enum의 모습은 언뜻 보면 이전에 사용했었던 #define 전처리기 매크로와 비슷해보인다.
이 때에도 다음과 같이 선언하면 해당되는 이름에 지정할 값을 넣어 줄 수 있었다.
#define CLASS_1 0
하지만 전처리기라는 것은 컴파일이 되기 이전에 먼저 실행되는 것이다.
그렇기 때문에 여기엔 그냥 타입이 적혀 있는 것이 아니라, 0이 적혀있는 것과 동일해진다.
int a = CLASS_1;
int a = 0;
하지만 앞서 보았듯 enum을 선언해서 변수에 대입했을 때는 enum이라는 정보 자체가 심볼 테이블에 남게 된다.
그래서 디버깅을 할때의 컴파일러는 변수에 단순히 0을 집어넣었다고 생각하지 않고
MYTYPE enum 타입의 TYPE_1이라는 것을 0으로 취급하긴 하지만, 이런 타입에 있는 값을 넣었다고 생각한다.
따라서 디버깅에 이런 타입의 서식 정보가 다 남아있으므로 컴파일러가 인식할 수 있다.
예외처리를 할 때 어떤 타입의 정보가 들어있는지 디버깅 시에 더 많은 것들을 얻을 수 있다.
반면 #define으로 선언한 값은 문제가 발생했을 때 디버깅에서 중단점을 걸어보아도 변수값만 숫자로 들어가 있기 때문에
사용자가 어떤 의미로 define을 사용한 건지 일일이 코드를 거슬러 올라가 확인하지 않으면 안된다.
이제 enum을 이용해서 이전 BST 코드를 개선해보자.
- map 구현 개선
#pragma once
// <map 구현하기>
enum class NODE_TYPE
{
PARENT, // 0
LCHILD, // 1
RCHILD, // 2
END, // 3
};
// map과 유사하게 만들려면 실제 key 값으로 사용할 타입을 지정받아야하고 (T1)
// 따로 넣어 줄 두 번째 세컨드 데이터 타입(pair)에 대한 타입 역시 지정 받아야 한다. (T2)
template <typename T1, typename T2>
struct tPair
{
T1 first;
T2 second;
};
template <typename T1, typename T2>
class tBSTNode
{
tPair<T1, T2> pair;
tBSTNode* arrNode[(int)NODE_TYPE.END];
tBSTNode()
: pair()
, arrNode{}
{}
tBSTNode(const tPair<T1, T2>& _pair, tBSTNode* _pParent, tBSTNode* _pLChild, tBSTNode* _pRChild)
: pair(_pair)
, arrNode{ _pParent, _pLChild, _pRChild }
{}
};
template <typename T1, typename T2>
class CBST
{
private:
tBSTNode<T1, T2>* m_pRoot; // 루트 노드 주소
int m_iCount; // 데이터 개수
public:
bool insert(const tPair<T1, T2>& _pair);
};
template<typename T1, typename T2>
inline bool CBST<T1, T2>::insert(const tPair<T1, T2>& _pair)
{
tBSTNode<T1, T2>* pNewNode = new tBSTNode<T1, T2>();
// 첫번째 데이터라면 그것을 root 노드로 설정
if (nullptr == m_pRoot)
{
m_pRoot = pNewNode;
}
else // 이미 root 노드가 증가한다면 반복문을 이용해서 본인의 자리를 찾을 때까지 작업을 반복.
{
// 이때 root 노드의 값은 바뀌면 안되므로 지역 변수를 사용해 저장함
tBSTNode<T1, T2>* pNode = m_pRoot;
NODE_TYPE node_type = NODE_TYPE::END; // 아직 아무것도 정해지지 않았으므로 END 지정
while (true)
{
// 현재 비교 중인 노드와의 우열 관계를 따지면서 계속 내려간다.
if (pNode->pair.first < pNewNode->pair.first)
node_type = NODE_TYPE::RCHILD;
else if (pNode->pair.first > pNewNode->pair.first)
node_type = NODE_TYPE::LCHILD;
else
return false;
// enum을 사용해 노드 포인터를 배열로 만들었기 때문에 노드를 선택할 수 있게 되었음
// 오른쪽이 비었다면 오른쪽으로, 왼쪽이 비었다면 왼쪽으로 노드를 연결함
if (nullptr == pNode->arrNodee[(int)node_type)]
{
pNode->arrNode[(int)node_type] = pNewNode;
pNewNode->arrNode[(int)NODE_TYPE::PARENT] = pNode;
break;
}
else
{
pNode = pNode->arrNode[(int)node_type];
}
}
}
// 데이터 개수 증가
++m_iCount;
}
노드를 추가하는 부분에 대한 코드 개선을 완료했다.
이제 노드를 이진 탐색하는 기능을 추가해보자.
이전에 배운 STL의 작동 방식을 떠올려보면, 할당된 컨테이너의 값을 받아오고 싶을 땐 find() 함수를 사용해 이테레이터로 받아왔었다. 값이 아무것도 없는 경우에는 그것은 end literator와 같았다.
이런식으로 find를 구현하려면 현재 BST 내부의 특정 데이터를 가리키는 역할을 하는 이터레이터가 있어야 한다.
현재 STL이 제공하는 make_pair 함수의 경우에는 알아서 pair 타입을 반환해주고 있다.
pair라는 구조체의 실제 이름을 몰라도 make_pair란 함수를 써서 insert하면 된다고 STL 함수를 제공하고 있기 때문에
사용자는 2개를 한 묶음으로 묶어서 전달해주는 반환 타입 pair의 구체적인 타입 이름을 알 필요는 없다.
하지만 우리는 이터레이터를 직접 구현하는 과정에서 insert를 할 때 기본으로 제공하는 make_pair 함수 대신 pair을 직접 만들어 사용중이기 때문에, map에 데이터를 집어 넣을 때 first, second가 한 묶음인 pair라는 단위를 사용한다는 사실을 알아야 한다. 이것이 무척 불편하기 때문에 내부에서 자체적으로 make_pair 함수를 만들어 본다.
- make_pair 함수 구현
template <typename T1, typename T2>
tPair<T1, T2> make_bstpair(const T1& _first, const T2& _second)
{
return tPair<T1, T2>{_first, _second};
}
함수의 사용법은 make_pair 함수와 동일한 방식으로 아래와 같다.
CBST<int, int> bstint;
bstint.insert(make_bstpair(100, 0));
- find 함수 구현
이번에는 컨테이너 내부의 값을 찾을 수 있는 find 함수를 만들어본다. 여기에는 이터레이터가 필요하므로 클래스를 생성해야 한다. BST 클래스의 inner class로 선언하도록 하자.
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::find(const T1& _find)
{
tBSTNode<T1, T2>* pNode = m_pRoot;
NODE_TYPE node_type = NODE_TYPE::END; // 아직 아무것도 정해지지 않았으므로 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 // 맞는 값을 찾았다면 바로 break하여서 지금 선택된 노드가 반환되도록 한다.
{
break;
}
// 맞는 값을 찾지 못했다면 node를 null로 만들어주고 종료한다.
if (nullptr == pNode->arrNodee[(int)node_type)]
{
pNode = nullptr
break;
}
else
{
pNode = pNode->arrNode[(int)node_type];
}
}
return iterator(this, pNode);
}
find 함수 자체는 직전에 구현한 make_pair 함수와 작동 원리는 비슷하기 때문에 맞는 값을 찾았을 때와 값을 찾지 못했을 때의 처리 정도만 바꿔주면 된다.
사용법은 다음과 같다.
CBST<int, int> bstint;
bstint.insert(make_bstpair(100, 0));
bstint.insert(make_bstpair(150, 0));
bstint.insert(make_bstpair(50, 0));
CBST<int, int>::iterator Iter = bstint.begin();
Iter = bstint.find(150);
- 중위 순회 구현하기 - 비교 연산자
BST는 중위 순위에 따라 트리 내부를 탐색한다. 중위 순회 방식으로 순회하려면 하려면 이터레이터끼리 서로 비교하는 기능이 필요하다. 따라서 필요한 연산자들을 구현해본다.
bool operator ==(const iterator& _other)
{
if (m_pBST == _other.m_pBST && m_pNode == _other, m_pNode)
return true;
return false;
}
bool operator != (const iterator& _other)
{
return !(*this == other);
}
// 역참조
const tPair<T1, T2>& operator *()
{
// m_pNode nullptr 체크 (end iterator 인지 아닌지)
assert(m_pNode);
return m_pNode->pair;
}
const tPair<T1, T2>& operator ->()
{
assert(m_pNode);
// 이터레이터가 특정 데이터를 가리킬 수 있도록 페어 쪽에 주소값을 전달
return m_pNode->pair;
}
이제 기본적인 연산자를 구현하였으니 중위 순위에 따라 순회하는 기능을 만들어보자.
중위 순위에서 현재 노드의 다음 노드를 중위 후속자, 현재 노드의 이전 노드는 중위 선행자라고 한다.
노드 탐색을 위해 두 노드를 왔다갔다 할 수 있도록 구현해보자.
#pragma once
#include <assert.h>
// <map 구현하기>
enum class NODE_TYPE
{
PARENT, // 0
LCHILD, // 1
RCHILD, // 2
END, // 3
};
// map과 유사하게 만들려면 실제 key 값으로 사용할 타입을 지정받아야하고 (T1)
// 따로 넣어 줄 두 번째 세컨드 데이터 타입(pair)에 대한 타입 역시 지정 받아야 한다. (T2)
template <typename T1, typename T2>
struct tPair
{
T1 first;
T2 second;
};
template <typename T1, typename T2>
tPair<T1, T2> make_bstpair(const T1& _first, const T2& _second)
{
return tPair<T1, T2>{_first, _second};
}
template <typename T1, typename T2>
class tBSTNode
{
tPair<T1, T2> pair;
tBSTNode* arrNode[(int)NODE_TYPE.END];
bool IsRoot()
{
if (nullptr == arrNode[(int)NODE_TYPE::PARENT]->arrNode[(int]NODE_TYPE::LCHILD] == this)
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;
}
tBSTNode()
: pair()
, arrNode{}
{}
tBSTNode(const tPair<T1, T2>& _pair, tBSTNode* _pParent, tBSTNode* _pLChild, tBSTNode* _pRChild)
: pair(_pair)
, arrNode{ _pParent, _pLChild, _pRChild }
{}
};
template <typename T1, typename T2>
class CBST
{
private:
tBSTNode<T1, T2>* m_pRoot; // 루트 노드 주소
int m_iCount; // 데이터 개수
public:
bool insert(const tPair<T1, T2>& _pair);
tBSTNode<T1, T2>* GetInOrderSuccessor(tBSTNode<T1, T2>* _pNode); // 후속자 노드를 준다
tBSTNode<T1, T2>* GetInOrderPredecessor(tBSTNode<T1, T2>* _pNode);
class iterator;
public:
iterator begin();
iterator end();
iterator find(const T1& _find);
public:
CBST()
: m_pRoot(nuulptr);
, m_iCount(0)
{}
// iterator
class iterator
{
private:
CBST<T1, T2>* m_pBST;
tBTSNode<T1, T2>* m_pNode; // NULL인 경우 END ITERATOR
public:
iterator()
: m_pBST(nullptr)
, m_pNode(nullptr)
{}
iterator(CBST < T1, T2)* _pBST, tBSTNode<T1, T2>* _pNode)
: m_pBST(_pBST)
, m_pNode(_pNode)
{}
bool operator ==(const iterator& _other)
{
if (m_pBST == _other.m_pBST && m_pNode == _other, m_pNode)
return true;
return false;
}
bool operator != (const iterator& _other)
{
return !(*this == other);
}
// 역참조
const tPair<T1, T2>& operator *()
{
// m_pNode nullptr 체크 (end iterator 인지 아닌지)
assert(m_pNode);
return m_pNode->pair;
}
const tPair<T1, T2>& operator ->()
{
assert(m_pNode);
// 이터레이터가 특정 데이터를 가리킬 수 있도록 페어 쪽에 주소값을 전달
return m_pNode->pair;
}
iterator& operator ++()
{
//m_pNode = m_pBST->GetInorderSuccessor(m_pNode);
return *this;
}
};
};
template<typename T1, typename T2>
inline bool CBST<T1, T2>::insert(const tPair<T1, T2>& _pair)
{
tBSTNode<T1, T2>* pNewNode = new tBSTNode<T1, T2>();
// 첫번째 데이터라면 그것을 root 노드로 설정
if (nullptr == m_pRoot)
{
m_pRoot = pNewNode;
}
else // 이미 root 노드가 증가한다면 반복문을 이용해서 본인의 자리를 찾을 때까지 작업을 반복.
{
// 이때 root 노드의 값은 바뀌면 안되므로 지역 변수를 사용해 저장함
tBSTNode<T1, T2>* pNode = m_pRoot;
NODE_TYPE node_type = NODE_TYPE::END; // 아직 아무것도 정해지지 않았으므로 END 지정
while (true)
{
// 현재 비교 중인 노드와의 우열 관계를 따지면서 계속 내려간다.
if (pNode->pair.first < pNewNode->pair.first)
node_type = NODE_TYPE::RCHILD;
else if (pNode->pair.first > pNewNode->pair.first)
node_type = NODE_TYPE::LCHILD;
else
return false;
// enum을 사용해 노드 포인터를 배열로 만들었기 때문에 노드를 선택할 수 있게 되었음
// 오른쪽이 비었다면 오른쪽으로, 왼쪽이 비었다면 왼쪽으로 노드를 연결함
if (nullptr == pNode->arrNodee[(int)node_type)]
{
pNode->arrNode[(int)node_type] = pNewNode;
pNewNode->arrNode[(int)NODE_TYPE::PARENT] = pNode;
break;
}
else
{
pNode = pNode->arrNode[(int)node_type];
}
}
}
// 데이터 개수 증가
++m_iCount;
}
// 위의 노드가 오른쪽 자식을 보유한 경우, 오른쪽 자식으로 가서 왼쪽 자식이 없을 때까지 이동
// 위의 노드가 왼쪽 자식인 경우, 부모가 중위 후속자
// 탐색할 노드가 오른쪽 자식이 없고 스스로 왼쪽 노드도 아닌 경우, 위로 올라감
// 이때 올라간 노드가 왼쪽 자식이 아닌 경우 또 위로 올라감.
// 2번 올라간 노드가 또 왼쪽 자식이 아닌 경우 또 올라감.
// 3번째 올라간 노드가 root 노드인 경우 더 이상 부모가 없으므로 해당 노드가 마지막 노드라는 뜻
// = end iterator
template<typename T1, typename T2>
inline tBSTNode<T1, T2>* CBST<T1, T2>::GetInOrderSuccessor(tBSTNode<T1, T2>* _pNode)
{
tBSTNode<T1, T2>* pSuccessor = nullptr;
// 1. 오른쪽 자식이 없는 경우, 오른쪽 자식으로 간 뒤 왼쪽 자식이 없을 때까지 내려감
if (nullptr != _pNode->arrNode[(int)NODE_TYPE::RCHILD])
{
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 tBSTNode<T1, T2>* CBST<T1, T2>::GetInOrderPredecessor(tBSTNode<T1, T2>* _pNode)
{
return NULL;
}
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::begin()
{
tBSTNode<T1, T2>* pNode = m_pRoot;
while (pNode->arrNode[(int]NODE_TYPE::LCHILD)
{
pNode = pNode->arrNode[(int)NODE_TYPE::LCHILD];
}
return iterator(this, pNode);
}
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)
{
tBSTNode<T1, T2>* pNode = m_pRoot;
NODE_TYPE node_type = NODE_TYPE::END; // 아직 아무것도 정해지지 않았으므로 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 // 맞는 값을 찾았다면 바로 break하여서 지금 선택된 노드가 반환되도록 한다.
{
break;
}
// 맞는 값을 찾지 못했다면 node를 null로 만들어주고 종료한다.
if (nullptr == pNode->arrNodee[(int)node_type)]
{
pNode = nullptr
break;
}
else
{
pNode = pNode->arrNode[(int)node_type];
}
}
return iterator(this, pNode);
}
- 삭제 기능 구현
이번에는 불필요한 특정 데이터를 제거하는 방법에 대해 알아보고 구현해보자.
BST에서 어떤 노드의 자식이 1개 인 경우 노드가 삭제되고 나면 그 자리를 아래에 있던 자식이 대체하면 된다.
그러나 노드가 2개인 경우는 두 자식 중에 하나가 그 자리를 대체하는 것이 아니라 중위 선행자나 후속자가 와야 트리의 균형이 유지된다.
CBST<int, int> bstint;
bstint.insert(make_bstpair(100, 0)); // 100
bstint.insert(make_bstpair(150, 0)); // 50 150
bstint.insert(make_bstpair(50, 0)); //25 75 125 175
bstint.insert(make_bstpair(25, 0));
bstint.insert(make_bstpair(75, 0));
bstint.insert(make_bstpair(125, 0));
bstint.insert(make_bstpair(175, 0));
CBST<int, int>::iterator Iter = bstint.begin();
Iter = bstint.find(25);
Iter = bstint.erase(Iter);
이 원리를 바탕으로 STL에서 제공하는 컨테이너의 값을 지우는 함수 erase를 직접 구현해본다.
#pragma once
#include <assert.h>
// <map 구현하기>
enum class NODE_TYPE
{
PARENT, // 0
LCHILD, // 1
RCHILD, // 2
END, // 3
};
// map과 유사하게 만들려면 실제 key 값으로 사용할 타입을 지정받아야하고 (T1)
// 따로 넣어 줄 두 번째 세컨드 데이터 타입(pair)에 대한 타입 역시 지정 받아야 한다. (T2)
template <typename T1, typename T2>
struct tPair
{
T1 first;
T2 second;
};
template <typename T1, typename T2>
tPair<T1, T2> make_bstpair(const T1& _first, const T2& _second)
{
return tPair<T1, T2>{_first, _second};
}
template <typename T1, typename T2>
class tBSTNode
{
tPair<T1, T2> pair;
tBSTNode* arrNode[(int)NODE_TYPE.END];
bool IsRoot()
{
if (nullptr == arrNode[(int)NODE_TYPE::PARENT]->arrNode[(int]NODE_TYPE::LCHILD] == this)
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 (nullptr == arrNode[(int)NODE_TYPE::LCHILD] && nullptr == arrNode[(int)NODE_TYPE::RCHILD])
return true;
return false;
}
bool IsFull()
{
if (arrNode[(int)NODE_TYPE::LCHILD] && nullptr == arrNode[(int)NODE_TYPE::RCHILD])
return true;
return false;
}
tBSTNode()
: pair()
, arrNode{}
{}
tBSTNode(const tPair<T1, T2>& _pair, tBSTNode* _pParent, tBSTNode* _pLChild, tBSTNode* _pRChild)
: pair(_pair)
, arrNode{ _pParent, _pLChild, _pRChild }
{}
};
template <typename T1, typename T2>
class CBST
{
private:
tBSTNode<T1, T2>* m_pRoot; // 루트 노드 주소
int m_iCount; // 데이터 개수
public:
bool insert(const tPair<T1, T2>& _pair);
tBSTNode<T1, T2>* GetInOrderSuccessor(tBSTNode<T1, T2>* _pNode); // 후속자 노드를 준다
tBSTNode<T1, T2>* GetInOrderPredecessor(tBSTNode<T1, T2>* _pNode);
class iterator;
public:
iterator begin();
iterator end();
iterator find(const T1& _find);
iterator erase(const iterator& _iter);
private:
tBSTNode<T1, T2>* DeleteNode(tBSTNode<T1, T2>* _pTargetNode);
public:
CBST()
: m_pRoot(nuulptr);
, m_iCount(0)
{}
// iterator
class iterator
{
private:
CBST<T1, T2>* m_pBST;
tBTSNode<T1, T2>* m_pNode; // NULL인 경우 END ITERATOR
bool operator ==(const iterator& _other)
{
if (m_pBST == _other.m_pBST && m_pNode == _other, m_pNode)
return true;
return false;
}
bool operator != (const iterator& _other)
{
return !(*this == other);
}
// 역참조
const tPair<T1, T2>& operator *()
{
// m_pNode nullptr 체크 (end iterator 인지 아닌지)
assert(m_pNode);
return m_pNode->pair;
}
const tPair<T1, T2>& operator ->()
{
assert(m_pNode);
// 이터레이터가 특정 데이터를 가리킬 수 있도록 페어 쪽에 주소값을 전달
return m_pNode->pair;
}
iterator& operator ++()
{
//m_pNode = m_pBST->GetInorderSuccessor(m_pNode);
return *this;
}
public:
iterator()
: m_pBST(nullptr)
, m_pNode(nullptr)
{}
iterator(CBST < T1, T2)* _pBST, tBSTNode<T1, T2>* _pNode)
: m_pBST(_pBST)
, m_pNode(_pNode)
{}
friend class CBST<T1, T2>;
};
};
template<typename T1, typename T2>
inline bool CBST<T1, T2>::insert(const tPair<T1, T2>& _pair)
{
tBSTNode<T1, T2>* pNewNode = new tBSTNode<T1, T2>();
// 첫번째 데이터라면 그것을 root 노드로 설정
if (nullptr == m_pRoot)
{
m_pRoot = pNewNode;
}
else // 이미 root 노드가 증가한다면 반복문을 이용해서 본인의 자리를 찾을 때까지 작업을 반복.
{
// 이때 root 노드의 값은 바뀌면 안되므로 지역 변수를 사용해 저장함
tBSTNode<T1, T2>* pNode = m_pRoot;
NODE_TYPE node_type = NODE_TYPE::END; // 아직 아무것도 정해지지 않았으므로 END 지정
while (true)
{
// 현재 비교 중인 노드와의 우열 관계를 따지면서 계속 내려간다.
if (pNode->pair.first < pNewNode->pair.first)
node_type = NODE_TYPE::RCHILD;
else if (pNode->pair.first > pNewNode->pair.first)
node_type = NODE_TYPE::LCHILD;
else
return false;
// enum을 사용해 노드 포인터를 배열로 만들었기 때문에 노드를 선택할 수 있게 되었음
// 오른쪽이 비었다면 오른쪽으로, 왼쪽이 비었다면 왼쪽으로 노드를 연결함
if (nullptr == pNode->arrNodee[(int)node_type)]
{
pNode->arrNode[(int)node_type] = pNewNode;
pNewNode->arrNode[(int)NODE_TYPE::PARENT] = pNode;
break;
}
else
{
pNode = pNode->arrNode[(int)node_type];
}
}
}
// 데이터 개수 증가
++m_iCount;
}
// 위의 노드가 오른쪽 자식을 보유한 경우, 오른쪽 자식으로 가서 왼쪽 자식이 없을 때까지 이동
// 위의 노드가 왼쪽 자식인 경우, 부모가 중위 후속자
// 탐색할 노드가 오른쪽 자식이 없고 스스로 왼쪽 노드도 아닌 경우, 위로 올라감
// 이때 올라간 노드가 왼쪽 자식이 아닌 경우 또 위로 올라감.
// 2번 올라간 노드가 또 왼쪽 자식이 아닌 경우 또 올라감.
// 3번째 올라간 노드가 root 노드인 경우 더 이상 부모가 없으므로 해당 노드가 마지막 노드라는 뜻
// = end iterator
template<typename T1, typename T2>
inline tBSTNode<T1, T2>* CBST<T1, T2>::GetInOrderSuccessor(tBSTNode<T1, T2>* _pNode)
{
tBSTNode<T1, T2>* pSuccessor = nullptr;
// 1. 오른쪽 자식이 없는 경우, 오른쪽 자식으로 간 뒤 왼쪽 자식이 없을 때까지 내려감
if (nullptr != _pNode->arrNode[(int)NODE_TYPE::RCHILD])
{
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 tBSTNode<T1, T2>* CBST<T1, T2>::GetInOrderPredecessor(tBSTNode<T1, T2>* _pNode)
{
return NULL;
}
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::begin()
{
tBSTNode<T1, T2>* pNode = m_pRoot;
while (pNode->arrNode[(int]NODE_TYPE::LCHILD)
{
pNode = pNode->arrNode[(int)NODE_TYPE::LCHILD];
}
return iterator(this, pNode);
}
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)
{
tBSTNode<T1, T2>* pNode = m_pRoot;
NODE_TYPE node_type = NODE_TYPE::END; // 아직 아무것도 정해지지 않았으므로 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 // 맞는 값을 찾았다면 바로 break하여서 지금 선택된 노드가 반환되도록 한다.
{
break;
}
// 맞는 값을 찾지 못했다면 node를 null로 만들어주고 종료한다.
if (nullptr == pNode->arrNodee[(int)node_type)]
{
pNode = nullptr
break;
}
else
{
pNode = pNode->arrNode[(int)node_type];
}
}
return iterator(this, pNode);
}
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::erase(const iterator& _iter)
{
// 삭제 될 노드가 오른쪽에 있는 경우
// 삭제를 하면 부모로 접근을 할 수 없기 때문에 부모로 접근하기 전에
// 부모의 오른쪽 자식이 있으면 그 노드 안의 부모의 위치를 가리키는 포인터로 접근해서
// 부모가 없다는 뜻으로 포인터를 NULL로 막아놓아야 한다.
// 반대로 삭제 될 노드가 왼쪽에 있는 경우
// 왼쪽의 노드로 접근하여 포인터를 NULL로 막아놓아야 한다.
assert(this == _iter.m_pBST);
tBSTNode<T1, T2>* pSuccessor = DeleteNode(_iter.m_pNode);
}
template<typename T1, typename T2>
inline tBSTNode<T1, T2>* CBST<T1, T2>::DeleteNode(tBSTNode<T1, T2>* _pTargetNode)
{
// 삭제 시킬 노드의 후속자 노드를 찾아둔다.
tBSTNode<T1, T2>* pSuccessor = GetInOrderSuccessor(_pTargetNode);
// 1. 자식이 하나도 없는 경우
if (_pTargetNode->IsLeaf())
{
// 삭제할 노드가 루트였다 (자식이 없고 루트 ==> BST 안에 데이터가 1개밖에 없었다.)
if (_pTargetNode == m_pRoot)
{
m_pRoot = nulltpr;
}
else
{
// 부모 노드로 접근, 삭제될 노드만 자식을 가리키는 포인터를 nullptr로 만든다.
if (_pTargetNode->IsChild())
_pTargetNode->arrNode[(int)NODE_TYPE::PARENT]->arrNode[(int)NODE_TYPE::LCHILD] = nullptr;
else
_pTargetNode->arrNode[(int)NODE_TYPE::PARENT]->arrNode[(int)NODE_TYPE::RCHILD] = nullptr;
}
delete _pTargetNode;
}
// 2. 자식이 2개인 경우
else if (_pTargetNode->IsFull)
{
pSuccessor = _pTargetNode;
// 삭제 될 자리에 중쥐 후속자의 값을 복사시킨다.
_pTargetNode->pair = pSuccessor->pair;
// 중위 후속자 노드를 삭제한다.
DeleteNode(pSuccessor);
// 삭제할 노드가 곧 중위 후속자가 되었다.
pSuccessor = _pTargetNode;
}
// 3. 자식이 1개인 경우
else
{
pSuccessor = GetInOrderSuccessor(_pTargetNode);
NODE_TYPE eChildType = NODE_TYPE::LCHILD;
if (_pTargetNode->arrNode[(int)]NODE_TYPE::RCHILD)
eChildType = NODE_TYPE::RCHILD;
// 삭제할 노드가 루트였다면
if (_pTargetNode == m_pRoot)
{
// 자식 노드(1개)를 루트로 만든다.
m_pRoot = _pTargetNode->arrNode[(int)eChildType]->arrNode[(int)NODE_TYPE::PARENT] = nullptr;
}
else
{
// 삭제될 노드의 부모와, 삭제될 노드의 자식을 연결해준다.
if (_pTargetNode->isLeftChild())
{
_pTargetNode->arrNode[(int)NODE_TYPE::PARENT]->arrNode[(int)NODE_TYPE::LCHILD] = _pTargetNode->arrNode[(int)eChildType];
}
else
{
_pTargetNode->arrNode[(int)NODE_TYPE::PARENT]->arrNode[(int)NODE_TYPE::RCHILD] = _pTargetNode->arrNode[(int)eChildType];
}
_pTargetNode->arrNode[(int)NODE_TYPE::PARENT]->arrNode[(int)NODE_TYPE::PARENT] = _pTargetNode->arrNode[(int)eChildType];
}
delete _pTargetNode;
// 데이터 개수 맞춰줌
--m_iCount;
}
return pSuccessor;
}'C,C++' 카테고리의 다른 글
| 오버라이딩 (0) | 2023.02.12 |
|---|---|
| 상속 (0) | 2023.02.11 |
| [C++] list iterator (0) | 2023.02.06 |
| [C++] iterator (0) | 2023.02.05 |
| [C++] STL(vector, list) (0) | 2023.02.03 |