[C++] BST의 중위 후속자, 중위 선행자 및 BST의 삭제 구현
2024. 4. 4. 16:28ㆍProgramming Language/C++
아래 링크 클릭 시 해당 본문으로 이동
- 예시 1 (25 삭제)
- 예시 2 (100만 있는 경우)
- 예시 3 (자식이 1개 있는 경우 (75를 제외하고 50 삭제))
- 예시 4 (100, 150 빼고 다 제외, 100 삭제)
- 예시 5 (자식이 2개 있는 경우 (150 삭제))
- 예시 5-1 (자식이 2개 있는 경우 (100 삭제))
BST 중위 후속자, 중위 선행자 구현
▷ 예시
CBST.h
#pragma once
#include <assert.h>
// 서로를 가리킬 수 있는 노드 타입
enum class NODE_TYPE
{
PARENT, // 부모 노드 // 0
LCHILD, // 왼쪽 자식 // 1
RCHILD, // 오른쪽 자식 // 2
END, // 마감 // 3
};
// data 파트에 해당하는 구조체
template<typename T1, typename T2>
struct tPair
{
T1 first;
T2 second;
};
// make_pair() 함수
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>
struct tBSTNode
{
// data 파트를 가리키는 포인터
tPair<T1, T2> pair;
tBSTNode* arrNode[(int)NODE_TYPE::END]; // END가 3이니까 NODE_TYPE의 END를 이용하여 배열을 만든다.
// 루트 노드처럼 애초에 부모가 없다면?
// 때문에 루트인지부터 체크한다.
bool IsRoot()
{
if (nullptr == arrNode[(int)NODE_TYPE::PARENT])
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:
// BST는 루트 노드만 알면 된다.
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:
// begin iterator와 end iterator
iterator begin();
iterator end();
// find()
iterator find(const T1& _find); // T1 타입을 받는다.
public:
// 생성자
CBST()
: m_pRoot(nullptr)
, m_iCount(0)
{}
// iterator
class iterator
{
private:
// CBST를 알고 있으면 m_pRoot를 통해 루트 노드를 알 수 있다.
CBST<T1, T2>* m_pBST; // BST 본체 지정
// iterator는 가리키고 있는 노드를 알고 있어야 특정 트리에 있는 데이터를 가리킬 수 있다.
tBSTNode<T1, T2>* m_pNode; // null인 경우 end iterator
public:
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);
}
// 수정 가능하게 하면 안 되는 이유?
// first값이 바뀌어버리면 구조가 다 틀어진다.
// ex. 50 - 100(루트) - 150에서 150을 10으로 바꾸면 구조가 바뀌어버린다.
const tPair<T1, T2>& operator *()
// 역참조(*)해서 참조로 반환했기 때문에 되돌아온 것 자체가 pair이다.
// pair가 구조체이기 때문에 '.'을 통해서 세부적인 파트를 접근했다.
{
// end iterator일 경우
// 마지막의 다음을 가리키고 있어서 값을 꺼내올 수가 없다.
// m_pNode nullptr 체크(end iterator인지 아닌지)
assert(m_pNode);
return m_pNode->pair;
}
const tPair<T1, T2>* operator ->()
// 참조를 주는 것이 아니라 실제적인 *pair의 주소값*을 준다.
// pair의 주소를 받았기 때문에 한 번에 그곳에 있는 first나 second를 지칭할 수 있다.
{
assert(m_pNode);
return &m_pNode->pair;
}
// ++(전위)은 중위 순회(in order)를 기준으로 다음으로 가야 한다.
// 중위 선행자(in order predecessor) : 중위 순회 기준으로 현재의 이전이다.
// 중위 후속자(in order successor) : 중위 순회 기준으로 현재의 다음이다.
iterator& operator ++()
{
// 현재 노드의 중위 후속자를 가리킨다.
m_pNode = m_pBST->GetInOrderSuccessor(m_pNode);
return *this;
}
iterator& operator --()
{
// 현재 노드의 중위 선행자를 가리킨다.
m_pNode = m_pBST->GetInOrderPredecessor(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)
{}
};
};
template<typename T1, typename T2>
inline bool CBST<T1, T2>::insert(const tPair<T1, T2>& _pair)
{
// pair를 넣을 수 있는 노드를 동적 할당하여 만든다.
tBSTNode<T1, T2>* pNewNode = new tBSTNode<T1, T2>(_pair, nullptr, nullptr, nullptr);
// 첫 번째 데이터라면
if (nullptr == m_pRoot)
{
// 만들어진 노드가 루트 노드가 되어야 한다.
m_pRoot = pNewNode;
}
// 첫 번째 데이터가 아니라면
else
{
// 루트 노드 값은 바뀌거나 훼손되면 안 되니까 지역 변수를 사용한다.
tBSTNode<T1, T2>* pNode = m_pRoot; // 루트 노드 주소를 받는다.
// 가야 될 방향을 enum값 타입으로 지정
// 아무것도 정해지지 않은 상태기 때문에 END로 지정한다.
NODE_TYPE node_type = NODE_TYPE::END;
// 루트 노드와 들어온 데이터를 pair의 first끼리 비교한다.
// 언제까지 반복? => 들어온 데이터가 단말 노드가 될 때까지 비교하면서 내려간다.
while (true)
{
// pNewNode : 새로 들어온 노드 / pNode : 현재 노드
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;
// 두 개가 같다면 (first값이 똑같다면, key값이 같다면)
else
return false;
// 해당 방향이 비어있다면
// 현재 노드의 해당 방향에 새로운 노드를 넣어준다.
if (nullptr == pNode->arrNode[(int)node_type])
{
pNode->arrNode[(int)node_type] = pNewNode;
pNewNode->arrNode[(int)NODE_TYPE::PARENT] = pNode;
break;
}
// 해당 방향이 비어있지 않다면
// 노드를 해당 방향으로 갱신한다.
else
{
pNode = pNode->arrNode[(int)node_type];
}
// 위에서 오른쪽으로 갈지 왼쪽으로 갈지 정했기 때문에 왼쪽 부분을 만들 필요가 없다.
// 이는 노드 포인터(tBSTNode*)를 배열로 만들었기 때문에 가능하다. (배열 인덱스로 PARENT, LCHILD, RCHILD, END를 묶음.)
}
}
// 데이터 개수 증가
++m_iCount;
return true;
}
// 중위 후속자
template<typename T1, typename T2>
inline tBSTNode<T1, T2>* CBST<T1, T2>::GetInOrderSuccessor(tBSTNode<T1, T2>* _pNode)
{
// 왼쪽 자식은 부모가 중위 후속자이다.
// 오른쪽 자식을 가지고 있는 부모의 중위 후속자는 오른쪽 자식이다.
//
// ※ 정리
// 1. 오른쪽 자식 보유 여부
// 오른쪽 자식 있음. => 오른쪽 자식이 중위 후속자이다.
// 무조건 오른쪽 자식이 중위 후속자인 것은 아니다.
// 오른쪽 자식이 있는데 해당 자식이 더 이상 자식이 없다면 오른쪽 자식이 중위 후속자이다.
// 오른쪽 자식이 있는데 해당 자식에게 또 자식이 있다면?
// 오른쪽 자식으로 간 다음, 왼쪽 자식이 없을 때까지 왼쪽으로 내려간다.
// 왼쪽 자식이 없는 해당 자식이 중위 후속자이다.
// 오른쪽 자식 없음. => 부모로 올라간다.
// 2. 왼쪽 자식인지 아닌지
// 왼쪽 자식이면 => 부모가 중위 후속자이다.
// 왼쪽 자식이 아니면 => 그 윗 부모를 생각해야 한다.
// 맨 마지막(오른쪽 맨 아래이면서 오른쪽 자식)은 본인이 왼쪽 자식일 때까지 찾기 위해 끝까지 올라가도 없었다.
// 즉, 중위 후속자가 없으므로 end로 본다.
tBSTNode<T1, T2>* pSuccessor = _pNode;
// 1. 오른쪽 자식이 있으면 => 오른쪽 자식으로 간 다음, 왼쪽 자식이 없을 때까지 내려간다.
// ex. B → J, A → L, C → N
if (nullptr != _pNode->arrNode[(int)NODE_TYPE::RCHILD])
{
pSuccessor = _pNode->arrNode[(int)NODE_TYPE::RCHILD]; // 오른쪽 자식을 받는다.
// pSuccessor의 왼쪽 자식이 null일 때까지 반복한다.
while (pSuccessor->arrNode[(int)NODE_TYPE::LCHILD])
{
pSuccessor = pSuccessor->arrNode[(int)NODE_TYPE::LCHILD];
}
}
// 2. 오른쪽 자식이 없다면 => 부모로부터 왼쪽 자식일 때까지 위로 올라간다.
// 그때 부모가 중위 후속자
// ex. H → D, I → B, J → E, K → A, L → F, M → C, N → G
else
{
// 더이상 올라갈 부모가 없다면 다음은 없다는 의미로 nullptr를 반환한다.
// ex. O
//if (nullptr == pSuccessor->arrNode[(int)NODE_TYPE::PARENT])
// return nullptr;
// pSuccessor의 부모 쪽 포인터 접근 → 그쪽 노드의 왼쪽 자식 부분이 현재 노드랑 같은지 비교
// 일치한다면 pSuccessor가 부모가 왼쪽 자식이다.
//pSuccessor->arrNode[(int)NODE_TYPE::PARENT]->arrNode[(int)NODE_TYPE::LCHILD] == pSuccessor;
pSuccessor = _pNode;
while (true)
{
// 루트라면 애초에 부모가 없기 때문에 nullptr을 반환한다.
//
// 더이상 위쪽으로 올라갈 수 없다. ==> 마지막 노드였다.
if (pSuccessor->IsRoot())
return nullptr;
// 그게 아니라면 pSuccessor가 왼쪽 자식인지 물어본다.
// 왼쪽 자식이라면 부모가 내 후속자이다.
//
// 부모로부터 왼쪽 자식인지 체크
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)
{
tBSTNode<T1, T2>* pPredecessor = _pNode;
// 1. 왼쪽 자식이 있으면 => 왼쪽 자식으로 간 다음, 오른쪽 자식이 없을 때까지 오른쪽으로 내려간다.
// ex. C → M, A → K, B → I
if (nullptr != _pNode->arrNode[(int)NODE_TYPE::LCHILD])
{
pPredecessor = _pNode->arrNode[(int)NODE_TYPE::LCHILD]; // 왼쪽 자식을 받는다.
// pPredecessor의 오른쪽 자식이 null일 때까지 반복한다.
while (pPredecessor->arrNode[(int)NODE_TYPE::RCHILD])
{
pPredecessor = pPredecessor->arrNode[(int)NODE_TYPE::RCHILD];
}
}
// 2. 왼쪽 자식이 없다면 => 부모로부터 오른쪽 자식일 때까지 위로 올라간다.
// 그때 부모가 중위 선행자
// ex. I → D, J → B, K → E, L → A, M → F, N → C, O → G
else
{
// 더이상 올라갈 부모가 없다면 다음은 없다는 의미로 nullptr를 반환한다.
// ex. H
pPredecessor = _pNode;
while (true)
{
// 루트라면 애초에 부모가 없기 때문에 nullptr을 반환한다.
//
// 더이상 위쪽으로 올라갈 수 없다. ==> 마지막 노드였다.
if (pPredecessor->IsRoot())
return nullptr;
// 그게 아니라면 pSuccessor가 왼쪽 자식인지 물어본다.
// 왼쪽 자식이라면 부모가 내 후속자이다.
//
// 부모로부터 오른쪽 자식인지 체크
if (pPredecessor->IsRightChild())
{
// 그때 부모가 선행자
pPredecessor = pPredecessor->arrNode[(int)NODE_TYPE::PARENT];
break;
}
else
{
pPredecessor = pPredecessor->arrNode[(int)NODE_TYPE::PARENT];
}
}
}
return pPredecessor; // 선행자 반환
}
// 반환 타입이 클래스 내에 있는 이너 클래스인 경우 typename을 적어줘야 한다.
// inline도 헤더에 다 구현한다면 기본적으로 inline처리를 하기 때문에 생략해도 된다.
//
// begin() => 중위 순회를 기준으로 첫 번째
// 중위 순회를 기준으로 더이상 왼쪽 자식이 없을 때까지 루트부터 시작해서 왼쪽으로 쭉 내려가야 한다.
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::begin()
{
tBSTNode<T1, T2>* pNode = m_pRoot;
// 왼쪽 자식이 null이면 0이므로 while 입장에선 false이기 때문에 반복문이 끝난다.
while (pNode->arrNode[(int)NODE_TYPE::LCHILD])
{
pNode = pNode->arrNode[(int)NODE_TYPE::LCHILD]; // 현재 노드를 왼쪽 자식으로 갱신한다.
}
return iterator(this, pNode); // iterator가 가리키는 노드를 반환한다.
// this => iterator가 노드 자체를 알아야 된다.
}
// end() => null을 가리킨다.
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::end()
{
return iterator(this, nullptr);
}
// find() => 내가 찾고자 하는 노드를 가리키는 iterator를 만들어서 반환한다.
// 찾는 과정은 insert()와 비슷하다.
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::find(const T1& _find)
{
// 루트 노드 값은 바뀌거나 훼손되면 안 되니까 지역 변수를 사용한다.
tBSTNode<T1, T2>* pNode = m_pRoot; // 루트 노드 주소를 받는다.
// 가야 될 방향을 enum값 타입으로 지정
// 아무것도 정해지지 않은 상태기 때문에 END로 지정한다.
NODE_TYPE node_type = NODE_TYPE::END;
// 루트 노드와 들어온 데이터를 pair의 first끼리 비교한다.
// 언제까지 반복? => 들어온 데이터가 단말 노드가 될 때까지 비교하면서 내려간다.
while (true)
{
// pNewNode : 새로 들어온 노드 / pNode : 현재 노드
if (pNode->pair.first < _find)
// 노드 타입을 오른쪽으로 정한다.
// 오른쪽으로 간다.
node_type = NODE_TYPE::RCHILD;
else if (pNode->pair.first > _find)
// 노드 타입을 왼쪽으로 정한다.
// 왼쪽으로 간다.
node_type = NODE_TYPE::LCHILD;
// 두 개가 같다면 (first값이 똑같다면, key값이 같다면) 찾은 것이다.
else
{
// pNode가 현재 찾으려는 노드다.
break;
}
// 해당 방향이 비어있다(더이상 내려갈 곳이 없다.)면 찾고 싶은 것을 못 찾은 것이다.
if (nullptr == pNode->arrNode[(int)node_type])
{
// 노드 값을 null로 설정한다.
pNode = nullptr; // ==> end iterator
break;
}
// 해당 방향이 비어있지 않다면
// 노드를 해당 방향으로 갱신한다.
else
{
pNode = pNode->arrNode[(int)node_type];
}
}
return iterator(this, pNode);
}
main.cpp
#include <iostream>
#include <map> // Red/Black 이진 탐색 트리가 구현되어있는 자료구조
#include "CBST.h"
using std::cout;
using std::endl;
using std::make_pair;
enum class 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_1,
};
int main()
{
CBST<int, int> bstint;
//tPair<int, int> pair;
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();
{
// 리스트나 벡터는 넣어놓은 데이터 타입이 1개였기 때문에 *Iter처럼 '*'로 접근이 가능했다.
// 하지만 BST는 pair로 2개를 묶어놨기 때문에 '->'로 접근해야 한다.
//tPair<int, int> pair;
//tPair<int, int>* pPair = &pair;
//pPair->first;
//pPair->second;
// -> 구현
//(*Iter).first;
Iter->first;
//(*Iter).second;
Iter->second;
// tPair<T1, T2>* operator ->()가 아니라 tPair<T1, T2>& operator ->()였다면?
// 엄밀히 말하면 'Iter->'까지가 iterator가 가리키고 있는 노드의 pair의 주소값이고 다시 거기로 가서(->) second에 접근하는 것이기 때문에 Iter->->second;로 해야 된다.
// 하지만 tPair<T1, T2>* operator ->() 덕분에 -> 하나를 생략할 수 있다.
}
// 구현한 BST도 순회가 가능해야 한다.
cout << "BST 순회 결과" << endl;
for (Iter = bstint.begin(); Iter != bstint.end(); ++Iter)
{
cout << "키: " << Iter->first << ", 값: " << Iter->second << endl;
}
// 중위 후속자 출력
cout << "\n중위 후속자 출력" << endl;
Iter = bstint.find(100);
++Iter; // 중위 후속자로 이동
cout << "키: " << Iter->first << ", 값: " << Iter->second << endl;
// 중위 선행자 출력
// 루트인 100의 선행자 => 50
cout << "\n중위 선행자 출력" << endl;
for (Iter = bstint.begin(); Iter != bstint.end(); --Iter)
{
cout << "키: " << Iter->first << ", 값: " << Iter->second << endl;
}
return 0;
}▽ 출력 결과
BST 순회 결과
키: 50, 값: 0
키: 100, 값: 0
키: 150, 값: 0
중위 후속자 출력
키: 150, 값: 0
중위 선행자 출력
키: 50, 값: 0BST의 삭제
1. 삭제할 노드가 단말 노드(leaf node)인 경우
노드 단위로 동적할당 했기 때문에 노드 채로 delete()하면 된다.
해당 노드를 그냥 삭제해도 트리의 형태에 영향을 주지 않는다.
2. 삭제할 노드가 자식 노드를 1개 가진 경우(왼쪽 또는 오른쪽)
애초에 부모보다는 작았으니까 해당 위치에 있는 거라서 없앤 부모 자리를 자식으로 갱신해도 된다.
ex) 재벌 집안에서 외동인 자식이 부모가 돌아가시면 그 자리를 물려받는 것처럼
3. 삭제할 노드가 2개의 자식을 가진 경우
자식끼리 비교해서 더 큰 자식을 없앤 부모 자리로 갱신하면 중위 순회 순서에 문제가 발생한다.
B를 삭제했을 때 중위 순회를 기준으로 D나 E가 아니라 I나 J가 B 자리로 가야 중위 순회의 순서에 문제가 없다.
H → D → I → [B] → J → E → K → A → L → F → M → C → N → G → O
중위 순회 순서를 숫자로 나타낸 예시를 보면서 이해해 보자.
4가 삭제된다면 3이나 5가 4의 자리로 가야 한다.
중위 후속자를 옮긴다면 5를 복사해서 4를 덮어버리고 5가 있던 자리를 삭제하면 된다.
중위 선행자나 후속자는 자식이 2개 이상 있을 수가 없다.
중위 후속자의 경우 오른쪽 자식으로 가서 왼쪽 자식이 없을 때까지 내려갔기 때문에 적어도 오른쪽 자식 1개밖에 가질 수가 없다.
따라서 후속자나 선행자가 자식을 2개 가지면 어떡하지라는 걱정은 할 필요가 없다.
※ 정리
중위 선행자나 후속자를 삭제하려는 자리에 복사시키고 실제로 삭제되는 것은 선행자나 후속자이다.
▷ 예시
▷ CBST.h 전체 코드
#pragma once
#include <assert.h>
// 서로를 가리킬 수 있는 노드 타입
enum class NODE_TYPE
{
PARENT, // 부모 노드 // 0
LCHILD, // 왼쪽 자식 // 1
RCHILD, // 오른쪽 자식 // 2
END, // 마감 // 3
};
// data 파트에 해당하는 구조체
template<typename T1, typename T2>
struct tPair
{
T1 first;
T2 second;
};
// make_pair() 함수
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>
struct tBSTNode
{
// data 파트(map에서는 pair라고 함.)를 가리키는 포인터
tPair<T1, T2> pair;
tBSTNode* arrNode[(int)NODE_TYPE::END]; // END가 3이니까 NODE_TYPE의 END를 이용하여 배열을 만든다.
// 루트 노드처럼 애초에 부모가 없다면?
// 때문에 루트인지부터 체크한다.
bool IsRoot()
{
if (nullptr == arrNode[(int)NODE_TYPE::PARENT])
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;
}
// leaf 노드인가?
// = 자식이 하나도 없는가?
bool IsLeaf()
{
if (nullptr == arrNode[(int)NODE_TYPE::LCHILD] && nullptr == arrNode[(int)NODE_TYPE::RCHILD])
return true;
return false;
}
// 꽉 찬 상태인가?
// 자식을 2개 다 가지고 있는가?
bool IsFull()
{
if (arrNode[(int)NODE_TYPE::LCHILD] && arrNode[(int)NODE_TYPE::RCHILD])
return true;
return false;
}
// IsLeaf()와 IsFull()가 완전히 대칭 관계는 아니다.
// leaf 노드가 아니라고 해서 꼭 full은 아니기 때문이다.
// 기본 생성자
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:
// BST는 루트 노드만 알면 된다.
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:
// begin iterator와 end iterator
iterator begin();
iterator end();
// find()
iterator find(const T1& _find); // T1 타입을 받는다.
iterator erase(const iterator& _iter); // iterator가 가리키는 노드를 삭제한다.
private:
tBSTNode<T1, T2>* DeleteNode(tBSTNode<T1, T2>* _pTargetNode);
public:
// 생성자
CBST()
: m_pRoot(nullptr)
, m_iCount(0)
{}
// iterator
class iterator
{
private:
// CBST를 알고 있으면 m_pRoot를 통해 루트 노드를 알 수 있다.
CBST<T1, T2>* m_pBST; // BST 본체 지정
// iterator는 가리키고 있는 노드를 알고 있어야 특정 트리에 있는 데이터를 가리킬 수 있다.
tBSTNode<T1, T2>* m_pNode; // null인 경우 end iterator
public:
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);
}
// 수정 가능하게 하면 안 되는 이유?
// first값이 바뀌어버리면 구조가 다 틀어진다.
// ex. 50 - 100(루트) - 150에서 150을 10으로 바꾸면 구조가 바뀌어버린다.
const tPair<T1, T2>& operator *()
// 역참조(*)해서 참조로 반환했기 때문에 되돌아온 것 자체가 pair이다.
// pair가 구조체이기 때문에 '.'을 통해서 세부적인 파트를 접근했다.
{
// end iterator일 경우
// 마지막의 다음을 가리키고 있어서 값을 꺼내올 수가 없다.
// m_pNode nullptr 체크(end iterator인지 아닌지)
assert(m_pNode);
return m_pNode->pair;
}
const tPair<T1, T2>* operator ->()
// 참조를 주는 것이 아니라 실제적인 *pair의 주소값*을 준다.
// pair의 주소를 받았기 때문에 한 번에 그곳에 있는 first나 second를 지칭할 수 있다.
{
assert(m_pNode);
return &m_pNode->pair;
}
// ++(전위)은 중위 순회(in order)를 기준으로 다음으로 가야 한다.
// 중위 선행자(in order predecessor) : 중위 순회 기준으로 현재의 이전이다.
// 중위 후속자(in order successor) : 중위 순회 기준으로 현재의 다음이다.
iterator& operator ++()
{
// 현재 노드의 중위 후속자를 가리킨다.
m_pNode = m_pBST->GetInOrderSuccessor(m_pNode);
return *this;
}
iterator& operator --()
{
// 현재 노드의 중위 선행자를 가리킨다.
m_pNode = m_pBST->GetInOrderPredecessor(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)
{}
// private 멤버 접근을 위해 iterator 쪽에서 친구 선언
friend class CBST<T1, T2>;
};
};
template<typename T1, typename T2>
inline bool CBST<T1, T2>::insert(const tPair<T1, T2>& _pair)
{
// pair를 넣을 수 있는 노드를 동적 할당하여 만든다.
tBSTNode<T1, T2>* pNewNode = new tBSTNode<T1, T2>(_pair, nullptr, nullptr, nullptr);
// 첫 번째 데이터라면
if (nullptr == m_pRoot)
{
// 만들어진 노드가 루트 노드가 되어야 한다.
m_pRoot = pNewNode;
}
// 첫 번째 데이터가 아니라면
else
{
// 루트 노드 값은 바뀌거나 훼손되면 안 되니까 지역 변수를 사용한다.
tBSTNode<T1, T2>* pNode = m_pRoot; // 루트 노드 주소를 받는다.
// 가야 될 방향을 enum값 타입으로 지정
// 아무것도 정해지지 않은 상태기 때문에 END로 지정한다.
NODE_TYPE node_type = NODE_TYPE::END;
// 루트 노드와 들어온 데이터를 pair의 first끼리 비교한다.
// 언제까지 반복? => 들어온 데이터가 단말 노드가 될 때까지 비교하면서 내려간다.
while (true)
{
// pNewNode : 새로 들어온 노드 / pNode : 현재 노드
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;
// 두 개가 같다면 (first값이 똑같다면, key값이 같다면)
else
return false;
// 해당 방향이 비어있다면
// 현재 노드의 해당 방향에 새로운 노드를 넣어준다.
if (nullptr == pNode->arrNode[(int)node_type])
{
pNode->arrNode[(int)node_type] = pNewNode;
pNewNode->arrNode[(int)NODE_TYPE::PARENT] = pNode;
break;
}
// 해당 방향이 비어있지 않다면
// 노드를 해당 방향으로 갱신한다.
else
{
pNode = pNode->arrNode[(int)node_type];
}
// 위에서 오른쪽으로 갈지 왼쪽으로 갈지 정했기 때문에 왼쪽 부분을 만들 필요가 없다.
// 이는 노드 포인터(tBSTNode*)를 배열로 만들었기 때문에 가능하다. (배열 인덱스로 PARENT, LCHILD, RCHILD, END를 묶음.)
}
}
// 데이터 개수 증가
++m_iCount;
return true;
}
// 중위 후속자
template<typename T1, typename T2>
inline tBSTNode<T1, T2>* CBST<T1, T2>::GetInOrderSuccessor(tBSTNode<T1, T2>* _pNode)
{
// 왼쪽 자식은 부모가 중위 후속자이다.
// 오른쪽 자식을 가지고 있는 부모의 중위 후속자는 오른쪽 자식이다.
//
// ※ 정리
// 1. 오른쪽 자식 보유 여부
// 오른쪽 자식 있음. => 오른쪽 자식이 중위 후속자이다.
// 무조건 오른쪽 자식이 중위 후속자인 것은 아니다.
// 오른쪽 자식이 있는데 해당 자식이 더 이상 자식이 없다면 오른쪽 자식이 중위 후속자이다.
// 오른쪽 자식이 있는데 해당 자식에게 또 자식이 있다면?
// 오른쪽 자식으로 간 다음, 왼쪽 자식이 없을 때까지 왼쪽으로 내려간다.
// 왼쪽 자식이 없는 해당 자식이 중위 후속자이다.
// 오른쪽 자식 없음. => 부모로 올라간다.
// 2. 왼쪽 자식인지 아닌지
// 왼쪽 자식이면 => 부모가 중위 후속자이다.
// 왼쪽 자식이 아니면 => 그 윗 부모를 생각해야 한다.
// 맨 마지막(오른쪽 맨 아래이면서 오른쪽 자식)은 본인이 왼쪽 자식일 때까지 찾기 위해 끝까지 올라가도 없었다.
// 즉, 중위 후속자가 없으므로 end로 본다.
tBSTNode<T1, T2>* pSuccessor = _pNode;
// 1. 오른쪽 자식이 있으면 => 오른쪽 자식으로 간 다음, 왼쪽 자식이 없을 때까지 내려간다.
// ex. B → J, A → L, C → N
if (nullptr != _pNode->arrNode[(int)NODE_TYPE::RCHILD])
{
pSuccessor = _pNode->arrNode[(int)NODE_TYPE::RCHILD]; // 오른쪽 자식을 받는다.
// pSuccessor의 왼쪽 자식이 null일 때까지 반복한다.
while (pSuccessor->arrNode[(int)NODE_TYPE::LCHILD])
{
pSuccessor = pSuccessor->arrNode[(int)NODE_TYPE::LCHILD];
}
}
// 2. 오른쪽 자식이 없다면 => 부모로부터 왼쪽 자식일 때까지 위로 올라간다.
// 그때 부모가 중위 후속자
// ex. H → D, I → B, J → E, K → A, L → F, M → C, N → G
else
{
// 더이상 올라갈 부모가 없다면 다음은 없다는 의미로 nullptr를 반환한다.
// ex. O
//if (nullptr == pSuccessor->arrNode[(int)NODE_TYPE::PARENT])
// return nullptr;
// pSuccessor의 부모 쪽 포인터 접근 → 그쪽 노드의 왼쪽 자식 부분이 현재 노드랑 같은지 비교
// 일치한다면 pSuccessor가 부모가 왼쪽 자식이다.
//pSuccessor->arrNode[(int)NODE_TYPE::PARENT]->arrNode[(int)NODE_TYPE::LCHILD] == pSuccessor;
pSuccessor = _pNode;
while (true)
{
// 루트라면 애초에 부모가 없기 때문에 nullptr을 반환한다.
//
// 더이상 위쪽으로 올라갈 수 없다. ==> 마지막 노드였다.
if (pSuccessor->IsRoot())
return nullptr;
// 그게 아니라면 pSuccessor가 왼쪽 자식인지 물어본다.
// 왼쪽 자식이라면 부모가 내 후속자이다.
//
// 부모로부터 왼쪽 자식인지 체크
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)
{
tBSTNode<T1, T2>* pPredecessor = _pNode;
// 1. 왼쪽 자식이 있으면 => 왼쪽 자식으로 간 다음, 오른쪽 자식이 없을 때까지 오른쪽으로 내려간다.
// ex. C → M, A → K, B → I
if (nullptr != _pNode->arrNode[(int)NODE_TYPE::LCHILD])
{
pPredecessor = _pNode->arrNode[(int)NODE_TYPE::LCHILD]; // 왼쪽 자식을 받는다.
// pPredecessor의 오른쪽 자식이 null일 때까지 반복한다.
while (pPredecessor->arrNode[(int)NODE_TYPE::RCHILD])
{
pPredecessor = pPredecessor->arrNode[(int)NODE_TYPE::RCHILD];
}
}
// 2. 왼쪽 자식이 없다면 => 부모로부터 오른쪽 자식일 때까지 위로 올라간다.
// 그때 부모가 중위 선행자
// ex. I → D, J → B, K → E, L → A, M → F, N → C, O → G
else
{
// 더이상 올라갈 부모가 없다면 다음은 없다는 의미로 nullptr를 반환한다.
// ex. H
pPredecessor = _pNode;
while (true)
{
// 루트라면 애초에 부모가 없기 때문에 nullptr을 반환한다.
//
// 더이상 위쪽으로 올라갈 수 없다. ==> 마지막 노드였다.
if (pPredecessor->IsRoot())
return nullptr;
// 그게 아니라면 pSuccessor가 왼쪽 자식인지 물어본다.
// 왼쪽 자식이라면 부모가 내 후속자이다.
//
// 부모로부터 오른쪽 자식인지 체크
if (pPredecessor->IsRightChild())
{
// 그때 부모가 선행자
pPredecessor = pPredecessor->arrNode[(int)NODE_TYPE::PARENT];
break;
}
else
{
pPredecessor = pPredecessor->arrNode[(int)NODE_TYPE::PARENT];
}
}
}
return pPredecessor; // 선행자 반환
}
// 반환 타입이 클래스 내에 있는 이너 클래스인 경우 typename을 적어줘야 한다.
// inline도 헤더에 다 구현한다면 기본적으로 inline처리를 하기 때문에 생략해도 된다.
//
// begin() => 중위 순회를 기준으로 첫 번째
// 중위 순회를 기준으로 더이상 왼쪽 자식이 없을 때까지 루트부터 시작해서 왼쪽으로 쭉 내려가야 한다.
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::begin()
{
tBSTNode<T1, T2>* pNode = m_pRoot;
// 왼쪽 자식이 null이면 0이므로 while 입장에선 false이기 때문에 반복문이 끝난다.
while (pNode->arrNode[(int)NODE_TYPE::LCHILD])
{
pNode = pNode->arrNode[(int)NODE_TYPE::LCHILD]; // 현재 노드를 왼쪽 자식으로 갱신한다.
}
return iterator(this, pNode); // iterator가 가리키는 노드를 반환한다.
// this => iterator가 노드 자체를 알아야 된다.
}
// end() => null을 가리킨다.
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::end()
{
return iterator(this, nullptr);
}
// find() => 내가 찾고자 하는 노드를 가리키는 iterator를 만들어서 반환한다.
// 찾는 과정은 insert()와 비슷하다.
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::find(const T1& _find)
{
// 루트 노드 값은 바뀌거나 훼손되면 안 되니까 지역 변수를 사용한다.
tBSTNode<T1, T2>* pNode = m_pRoot; // 루트 노드 주소를 받는다.
// 가야 될 방향을 enum값 타입으로 지정
// 아무것도 정해지지 않은 상태기 때문에 END로 지정한다.
NODE_TYPE node_type = NODE_TYPE::END;
// 루트 노드와 들어온 데이터를 pair의 first끼리 비교한다.
// 언제까지 반복? => 들어온 데이터가 단말 노드가 될 때까지 비교하면서 내려간다.
while (true)
{
// pNewNode : 새로 들어온 노드 / pNode : 현재 노드
if (pNode->pair.first < _find)
// 노드 타입을 오른쪽으로 정한다.
// 오른쪽으로 간다.
node_type = NODE_TYPE::RCHILD;
else if (pNode->pair.first > _find)
// 노드 타입을 왼쪽으로 정한다.
// 왼쪽으로 간다.
node_type = NODE_TYPE::LCHILD;
// 두 개가 같다면 (first값이 똑같다면, key값이 같다면) 찾은 것이다.
else
{
// pNode가 현재 찾으려는 노드다.
break;
}
// 해당 방향이 비어있다(더이상 내려갈 곳이 없다.)면 찾고 싶은 것을 못 찾은 것이다.
if (nullptr == pNode->arrNode[(int)node_type])
{
// 노드 값을 null로 설정한다.
pNode = nullptr; // ==> end iterator
break;
}
// 해당 방향이 비어있지 않다면
// 노드를 해당 방향으로 갱신한다.
else
{
pNode = pNode->arrNode[(int)node_type];
}
}
return iterator(this, pNode);
}
// BST의 삭제
template<typename T1, typename T2>
inline typename CBST<T1, T2>::iterator CBST<T1, T2>::erase(const iterator& _iter)
{
// iterator가 BST 내부의 노드를 가리키는 것이 아니라면 assert
assert(this == _iter.m_pBST);
// 노드 삭제
tBSTNode<T1, T2>* pSuccessor = DeleteNode(_iter.m_pNode);
// 노드 복붙하고 삭제하는 과정을 erase()에 다 구현하면 코드 재사용이 많아져서 재귀적인 형태를 띈다.
// 때문에 노드를 삭제하는 부분을 함수로 만들고 함수에 해당 노드만 전달해주면 되는 형식으로 만들었다.
// 반환값은 삭제하려는 노드의 중위 후속자이다.
return iterator(this, pSuccessor);
// 해당 노드의 자식이 몇 개인지 체크
// 1. 자식이 하나도 없는 경우
// 삭제할 단말 노드의 부모를 가리키는 포인터로 부모에 접근한다.
// 부모에서 삭제할 자식 노드를 가리키는 해당 포인터(왼쪽 또는 오른쪽)를 nullptr로 만든다.
//if (_iter.m_pNode->IsLeaf())
//{
// // 부모 노드로 접근해서 삭제될 노드인 자식을 가리키는 포인터를 nullptr로 만들어서 연결 관계를 끊는다.
// if (_iter.m_pNode->IsLeftChild())
// _iter.m_pNode->arrNode[(int)NODE_TYPE::PARENT]->arrNode[(int)NODE_TYPE::LCHILD] = nullptr;
// else
// _iter.m_pNode->arrNode[(int)NODE_TYPE::PARENT]->arrNode[(int)NODE_TYPE::RCHILD] = nullptr;
// // iterator가 가리키고 있는 노드 삭제
// delete _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. 자식이 하나도 없는 경우
// 삭제할 단말 노드의 부모를 가리키는 포인터로 부모에 접근한다.
// 부모에서 삭제할 자식 노드를 가리키는 해당 포인터(왼쪽 또는 오른쪽)를 nullptr로 만든다.
if (_pTargetNode->IsLeaf())
{
// 삭제할 노드가 루트 노드인 경우
// 루트 노드는 부모가 없다.
// 루트 노드밖에 없다면 (루트 노드의 자식이 없다면) = BST 안에 데이터가 1개밖에 없다면
// => BST에서 루트 노드를 가리키는 포인터를 nullptr로 만든다.
if (_pTargetNode == m_pRoot)
{
m_pRoot = nullptr; // 루트를 가리키는 멤버를 null로 막아준다.
}
// 삭제시킬 노드가 루트 노드가 아니라면
else
{
// 부모 노드로 접근해서 삭제될 노드인 자식을 가리키는 포인터를 nullptr로 만들어서 연결 관계를 끊는다.
if (_pTargetNode->IsLeftChild())
_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;
}
// iterator가 가리키고 있는 노드 삭제
delete _pTargetNode;
// 데이터 개수 맞춰주기 위해 데이터 감소
--m_iCount;
}
// 2. 자식이 2개인 경우
else if (_pTargetNode->IsFull())
{
// 삭제될 자리에 중위 후속자의 값을 복사시킨다. (선행자로 해도 문제는 없다.)
_pTargetNode->pair = pSuccessor->pair;
// 원래 중위 후속자가 있던 노드를 삭제한다.
DeleteNode(pSuccessor);
// 이렇게 호출된 후속자는 자식이 2개 있을 수는 없다.
// 무조건 1개나 없는 경우이다.
//
// 재귀함수 형식이지만 무한 루프가 발생하지는 않는다.
// 함수 안에서 자기 자신을 계속 호출하는 경우 => 삭제할 노드가 또 자식이 2개일 때 -> 그래야 DeleteNode(pSuccessor);에 또 걸린다.
// 한 번 더 호출될 시 1, 3번 경우에 걸리기 때문에 재호출할 이유는 없다.
// 삭제할 노드가 곧 중위 후속자가 됐다.
pSuccessor = _pTargetNode;
}
// 3. 자식이 1개인 경우
// 삭제될 노드의 부모와 삭제될 노드의 자식을 연결해준다.
else
{
// 자식이 1개인 루트 노드를 삭제하는 경우
// 자식이 루트 노드가 되면 된다.
// 1개인 자식이 왼쪽인지 오른쪽인지 체크
// eChildType => 왼쪽 또는 오른쪽 자식으로 결정된다.
NODE_TYPE eChildType = NODE_TYPE::LCHILD;
if (_pTargetNode->arrNode[(int)NODE_TYPE::RCHILD])
eChildType = NODE_TYPE::RCHILD;
// 삭제할 노드가 루트 노드인 경우
if (_pTargetNode == m_pRoot)
{
m_pRoot = _pTargetNode->arrNode[(int)eChildType]; // 자식을 루트 노드로 올린다.
_pTargetNode->arrNode[(int)eChildType]->arrNode[(int)NODE_TYPE::PARENT] = nullptr;
}
// 삭제할 노드가 루트 노드가 아닌 경우
// 삭제될 노드의 부모와 삭제될 노드의 자식을 연결해준다.
else
{
// 삭제될 노드가 부모의 왼쪽 자식인지 오른쪽 자식인지 체크
// 삭제될 노드가 왼쪽 자식이라면
if (_pTargetNode->IsLeftChild())
{
// 삭제할 노드의 부모로 접근해서 거기의 왼쪽 자식 부분에 삭제될 노드가 보유하고 있던 eChildType를 넣어준다.
// 즉, _pTargetNode의 자식도 부모의 왼쪽 자식에 연결한다.
_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)eChildType]->arrNode[(int)NODE_TYPE::PARENT] = _pTargetNode->arrNode[(int)NODE_TYPE::PARENT];
}
// 노드 삭제
delete _pTargetNode;
// 데이터 개수 맞춰주기 위해 데이터 감소
--m_iCount;
}
return pSuccessor;
}
▷ main.cpp
▷ 예시 1 (25 삭제)
더보기
#include <iostream>
#include <map> // Red/Black 이진 탐색 트리가 구현되어있는 자료구조
#include "CBST.h"
using std::make_pair;
using std::cout;
using std::endl;
int main()
{
CBST<int, int> bstint;
// #1. 25 삭제
// iterator는 50을 가리킨다.
bstint.insert(make_bstpair(100, 0)); // 100
bstint.insert(make_bstpair(150, 0)); // 50 150
bstint.insert(make_bstpair(50, 0)); // 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);
cout << "삭제 후 iterator가 가리키는 값: " << Iter->first << endl;
// BST 순회 및 출력
cout << "\nBST 순회 결과" << endl;
for (Iter = bstint.begin(); Iter != bstint.end(); ++Iter)
{
cout << "키: " << Iter->first << ", 값: " << Iter->second << endl;
}
return 0;
}▽ 출력 결과
삭제 후 iterator가 가리키는 값: 50
BST 순회 결과
키: 50, 값: 0
키: 75, 값: 0
키: 100, 값: 0
키: 125, 값: 0
키: 150, 값: 0
키: 175, 값: 0
▷ 예시 2 (100만 있는 경우)
더보기
#include <iostream>
#include <map> // Red/Black 이진 탐색 트리가 구현되어있는 자료구조
#include "CBST.h"
using std::make_pair;
using std::cout;
using std::endl;
int main()
{
CBST<int, int> bstint;
// #2. 100만 있는 경우
// iterator는 end iterator가 된다.
bstint.insert(make_bstpair(100, 0)); // 100
// BST 순회 및 출력
cout << "BST 순회 결과" << endl;
for (Iter = bstint.begin(); Iter != bstint.end(); ++Iter)
{
cout << "키: " << Iter->first << ", 값: " << Iter->second << endl;
}
return 0;
}▽ 출력 결과
BST 순회 결과
키: 100, 값: 0
▷ 예시 3 (자식이 1개 있는 경우 (75를 제외하고 50 삭제))
더보기
#include <iostream>
#include <map> // Red/Black 이진 탐색 트리가 구현되어있는 자료구조
#include "CBST.h"
using std::make_pair;
using std::cout;
using std::endl;
int main()
{
CBST<int, int> bstint;
// #3. 자식이 1개 있는 경우 (75를 제외하고 50 삭제)
// 25는 100과 연결되고 iterator는 100을 가리킨다.
bstint.insert(make_bstpair(100, 0)); // 100
bstint.insert(make_bstpair(150, 0)); // 25 150
bstint.insert(make_bstpair(50, 0)); // 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(50);
Iter = bstint.erase(Iter);
// BST 순회 및 출력
cout << "BST 순회 결과" << endl;
for (Iter = bstint.begin(); Iter != bstint.end(); ++Iter)
{
cout << "키: " << Iter->first << ", 값: " << Iter->second << endl;
}
return 0;
}▽ 출력 결과
BST 순회 결과
키: 25, 값: 0
키: 100, 값: 0
키: 125, 값: 0
키: 150, 값: 0
키: 175, 값: 0
▷ 예시 4 (100, 150 빼고 다 제외, 100 삭제)
더보기
#include <iostream>
#include <map> // Red/Black 이진 탐색 트리가 구현되어있는 자료구조
#include "CBST.h"
using std::make_pair;
using std::cout;
using std::endl;
int main()
{
CBST<int, int> bstint;
// #4. 100, 150 빼고 다 제외, 100 삭제
// 150이 루트이자 후속자가 된다.
bstint.insert(make_bstpair(100, 0)); // 100
bstint.insert(make_bstpair(150, 0)); // 150
//bstint.insert(make_bstpair(50, 0)); //
//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(100);
Iter = bstint.erase(Iter);
cout << "BST 순회 결과" << endl;
for (Iter = bstint.begin(); Iter != bstint.end(); ++Iter)
{
cout << "키: " << Iter->first << ", 값: " << Iter->second << endl;
}
return 0;
}▽ 출력 결과
BST 순회 결과
키: 150, 값: 0
▷ 예시 5 (자식이 2개 있는 경우 (150 삭제))
더보기
#include <iostream>
#include <map> // Red/Black 이진 탐색 트리가 구현되어있는 자료구조
#include "CBST.h"
using std::make_pair;
using std::cout;
using std::endl;
int main()
{
CBST<int, int> bstint;
// #5. 자식이 2개 있는 경우 (150 삭제)
// 150 자리에 175가 온다. (125도 가능)
// iterator는 175를 가리킨다.
// 루트 노드인 100과 50, 175가 있을 때 100을 삭제해도 후속자가 그 자리를 대체하기 때문에 따로 예외처리를 할 필요가 없다.
bstint.insert(make_bstpair(100, 0)); // 100
bstint.insert(make_bstpair(150, 0)); // 50 175
bstint.insert(make_bstpair(50, 0)); // 25 75 125
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(150);
Iter = bstint.erase(Iter);
// BST 순회 및 출력
cout << "BST 순회 결과" << endl;
for (Iter = bstint.begin(); Iter != bstint.end(); ++Iter)
{
cout << "키: " << Iter->first << ", 값: " << Iter->second << endl;
}
return 0;
}▽ 출력 결과
BST 순회 결과
키: 25, 값: 0
키: 50, 값: 0
키: 75, 값: 0
키: 100, 값: 0
키: 125, 값: 0
키: 175, 값: 0
▷ 예시 5-1 (자식이 2개 있는 경우 (100 삭제))
더보기
#include <iostream>
#include <map> // Red/Black 이진 탐색 트리가 구현되어있는 자료구조
#include "CBST.h"
using std::make_pair;
using std::cout;
using std::endl;
int main()
{
CBST<int, int> bstint;
// #5-1. 자식이 2개 있는 경우 (100 삭제)
// 루트 노드인 100 삭제
// 125가 100 자리로 간다.
// iterator는 125를 가리킨다.
bstint.insert(make_bstpair(100, 0)); // 125
bstint.insert(make_bstpair(150, 0)); // 50 175
bstint.insert(make_bstpair(50, 0)); // 25 75
bstint.insert(make_bstpair(25, 0)); //
bstint.insert(make_bstpair(75, 0)); //
bstint.insert(make_bstpair(125, 0)); //
bstint.insert(make_bstpair(175, 0)); //
// 중단점 (Iter) => m_pNode -> pair
CBST<int, int>::iterator Iter = bstint.begin();
Iter = bstint.find(100);
Iter = bstint.erase(Iter);
// BST 순회 및 출력
cout << "BST 순회 결과" << endl;
for (Iter = bstint.begin(); Iter != bstint.end(); ++Iter)
{
cout << "키: " << Iter->first << ", 값: " << Iter->second << endl;
}
return 0;
}▽ 출력 결과
BST 순회 결과
키: 25, 값: 0
키: 50, 값: 0
키: 75, 값: 0
키: 125, 값: 0
키: 150, 값: 0
키: 175, 값: 0'Programming Language > C++' 카테고리의 다른 글
| [C++] 객체지향 언어 특징 (0) | 2024.04.05 |
|---|---|
| [C++] 오버로딩 vs. 오버라이딩 (+ 바인딩) (0) | 2024.04.05 |
| [C++] enum 클래스를 활용하여 BST(이진 탐색 트리) 구현 (0) | 2024.04.04 |
| [C++] enum과 enum 클래스 (0) | 2024.04.04 |
| [C++] BST(이진 탐색 트리) 구현 (0) | 2024.04.03 |