//1 오른쪽에 있는거 위로 옮기기
자식이 1개인 경우 완성하기
else
{
pSuccessor = FindInOrderSuccessor(_target.m_TargetNode);
// 1
if (_target.m_TargetNode->IsRoot())
{
// 2
if (_target.m_TargetNode->HasLeftChild())
{
m_Root = _target.m_TargetNode->pLeftChild;
}
// 3
else
{
m_Root = _target.m_TargetNode->pRightChild;
}
// 4
m_Root->pParent = nullptr;
// 5
//delete _target.m_TargetNode;
}
// 6
else if (_target.m_TargetNode->IsLeftChild())
{
// 7
if (_target.m_TargetNode->HasLeftChild())
{
_target.m_TargetNode->pLeftChild->pParent = _target.m_TargetNode->pParent;
_target.m_TargetNode->pParent->pLeftChild = _target.m_TargetNode->pLeftChild;
}
// 8
else
{
_target.m_TargetNode->pRightChild->pParent = _target.m_TargetNode->pParent;
_target.m_TargetNode->pParent->pLeftChild = _target.m_TargetNode->pRightChild;
}
}
// 9
else
{
// 10
if (_target.m_TargetNode->HasLeftChild())
{
_target.m_TargetNode->pLeftChild->pParent = _target.m_TargetNode->pParent;
_target.m_TargetNode->pParent->pRightChild = _target.m_TargetNode->pLeftChild;
}
// 11
else
{
_target.m_TargetNode->pRightChild->pParent = _target.m_TargetNode->pParent;
_target.m_TargetNode->pParent->pRightChild = _target.m_TargetNode->pRightChild;
}
}
// 12
delete _target.m_TargetNode;
// 13
--m_CurCount;
// 14
return iterator(this, pSuccessor);
}- 1번은 삭제할 노드가 루트인 경우다
- 2번은 하나뿐인 왼쪽자식을 루트로 만든다.
- 루트가 아닐경우에만 아래의 조건들을 수행할수 있었다.(6번아래)
- 3번은 하나뿐인 오른쪽 자식을 루트로 만든다.
- 4번은 루트의 부모를 널로 막는다.
- 5번은 12번에서(함수 밖)에서 처리하니까 여기서 안해도 된다.
- 2번은 하나뿐인 왼쪽자식을 루트로 만든다.
- 6번은 삭제할 노드가 왼쪽 자식이다.
- 7번은 보유한 자식이 왼쪽 자식이다.
- 8번은 보유한 자식이 오른쪽 자식이다.
- 9번은 삭제할 노드가 오른쪽 자식이다.
- 10번은 보유한 자식이 왼쪽 자식이다.
- 11번은 보유한 자식이 오른쪽 자식이다.
- 12번은 해당 노드를 메모리 해제한다.
- 13번은 데이터 개수를 하나 줄인다.
- 14번은 미리 찾아놨던 포인터(this)와 미리만들어둔 후속자를 가리키는 이터레이터를 반환한다.
TestIter = bst.begin();
TestIter = bst.erase(TestIter);
TestIter = bst.erase(TestIter);
100
50 150
25 75 125 170- 저 코드 실행하면 25, 50을 지운 상태가 된다.
- 50 지울떄 케이스(중단점)에 맞게 잘 들어간다.
100
75 150
125 170자식이 2개 있는 경우
else if (_target.m_TargetNode->IsFull()) // 1
{
pSuccessor = FindInOrderSuccessor(_target.m_TargetNode); // 2
assert(pSuccessor); // 3
_target.m_TargetNode->pair = pSuccessor->pair; // 4
erase(iterator(this, pSuccessor)); // 5
return iterator(this, _target.m_TargetNode); // 6
}- 자식이 2개인 경우 코드다.
- 1번은 자식이 2개인 경우를 분기 처리해준것.
- 2번은 중위후속자를 찾는 코드부분이다.
- 3번은 후속자가 없을경우 assert
- 삭제할 노드의 후속자를 찾는다
- 자식이 2개라는 소리는 후속자가 없을수가 없다.
- 맨 마지막인 경우도 자식이 2개 일수가 없어서 무조건 자식 2개인 경우는 후속자를 갖는다.
- 삭제할 노드의 후속자를 찾는다
- 4번은 중위 후속자 노드의 데이터를 삭제할 노드의 데이터로 복사시킨다.
- 원래 삭제할려했던 다음을 후속자 데이터를 가진다.
- 5번은 자식이 2개인 노드의 후속자는 자식이 1개 또는 0개이다.
- erase 자식 0개 1개는 이미 구현해으니 그걸 재귀호출해서 삭제시킬수 있다.
- erase 함수를 재귀호출해서 자식이 1개 or 2개인 노드를 삭제하는 부분을 해결한다.
- 이떄 erase 안에서 데이터 개수를 줄이므로 여기서 다시 또 데이터 개수를 줄일 필요가 없다.
- 6번은 삭제된 노드의 후속자가 가진 데이터가 삭제할 노드로 복사되었기 때문에 원래 삭제하려고 했던 노드가 다시 삭제된 다음노드가 되었다.
TestIter = bst.find(100);
if (bst.end() != TestIter)
{
// 2.7
// 100을 erase로 지워죵.
bst.erase(TestIter);
}- TestIter는 100(루트노드)을 가리키고 있당.
- 찾고자 하는 iterator가 없을수도 있으니 조건문을 걸어버린다.
- 100을 erase로 지워버린다.
- 루트노드가 125로 갱신되었당.
- 2번에서 100에 후속자인 125를 반환한다
- 4번에서 125를 복사한다.
- 125의 페어값을 타켓노드100(TestIter)의 페어값에 대입한다.(세컨드 값도 복사된다.)
- 그러면 125가 가운데로 지정된다.
- 5번은 재귀함수를 호출해서 125를 처리하고와서 후속자 150으로 재설정한다.(?)
- erase안에 임시객체 pSuccessor를 가리키는 자식이 하나도 없는 125를 다시호출해서 지워버린다.
- 6번은 125를 헤드노드로인 상태로 반환한다.
- 그 자신(this)와 100을 대체한 125를 반환한다.
- 100을 erase로 지워버린다.
- 여기까지 구현을 하면 앵간한 map과 set의 표준 라이브러리랑 비슷하게 구현했다 그러나 표준라이브러리는 값을 들어올때 or 삭제할때마다 밸런스맞게 회전시키는걸 구현을 아직 안함.
- 회전하는 알고리즘은 나중에 레드블랙트리보면서 해보기.
operator ->
- 기존의 연결형리스트나 동적배열은 데이터를 1개씩 넣엇다.(템플릿 하나씩만함
- 탐색의 용이한 알고리즘은 2개의 템플릿을 썻다
- T1은 탐색용도의 타입이다.
- 색인값,키값(탐색할때 쓰는값, id)
- T2는 실제 저장하고 싶었던 데이터 타입(유저정보)
- T1은 탐색용도의 타입이다.
(*TestIter).first;
(*TestIter).second;- 노드안에 있던 pair로 반환해주니기 떄문에 접근 연산자
.으로 안에 값에 접근할수 있었다.- 포인터를 흉내내는것.
// 3.2
struct test
{
int first;
int second;
};
int main()
{
test t = {};
test* pTest = &t;
// 1
(*pTest).first;
(*pTest).second;
// 2
pTest->first;
pTest->second;
return 0;
}- 1번은 포인터의
.이고 포인터는 조금더 편하게 쓸려고 2번처럼 -> 를 사용 가능했당.
TestIter->first;
TestIter->second;- 우리의 BST iterator도 이렇게 사용하고 싶다.
- 오류가 뜬다.
const BSTPair<T1, T2>* operator-> ()
{
assert(m_Owner && m_TargetNode);
return &m_TargetNode->pair;
}- 반환타입을 레퍼런스가 아니라 포인터로 준다.
- 페어의 주소값을 주면 밖에서 화살표를 요청하면 페어의 주소값으로 리턴되게한다.
- 만들어주면 오류 해결.
(TestIter->)->first;
(TestIter->)->second;- 엄밀히 말하면 원래 이래야되는데 두번쓰지 않게 컴파일러가 화살표 operator을 만들면 한번만 작성해도 접근한거까지 연산을 해준다.
TestIter->first;
TestIter->second;- 가능.
강의 코드
main.cpp
#include <iostream>
using std::cout;
using std::endl;
#include "BST.h"
template<typename T1, typename T2>
class MyTemplateClass
{
T1 m_Data1;
T2 m_Data2;
};
MyTemplateClass<int, float> obj;
#include <set>
#include <map>
using std::set;
using std::map;
using std::make_pair;
// 퀵소트, 머지소트, 힙소트
// O(N logN)
// 그래프 - 노드간의 연결관계를 표현
// 트리 - 순환이 불가능한 그래프
// 이진트리 - 자식의 개수를 2개로 제한한 트리
// 이진탐색트리 - 입력 데이터를 크기에 따라 좌우(작은것을 왼쪽, 큰것을 오른쪽)로 정렬하는 트리
// Self Balanced Binary Search Tree
// 자가균형 이진탐색트리
// Red-Black, AVL
// 탐색
// 순차 탐색 O(N)
// 이진 탐색 O(logN)
// - 데이터가 정렬되어있어야 한다.
// - N(문제의 크기) 을 절반씩 줄여나가는 방식
// 컨테이너 vector list map,set
// 자료구조 동적배열 연결형 리스트 이진탐색트리
// 입력 O(1) O(1) O(logN)
// 삭제 O(N) O(1) O(1)
// 인덱싱 O(1) O(N) O(N)
// 탐색 O(N) O(N) O(logN)
struct test
{
int first;
int second;
};
int main()
{
test t = {};
test* pTest = &t;
(*pTest).first;
(*pTest).second;
pTest->first;
pTest->second;
set<int> intset;
intset.insert(100);
intset.insert(150);
intset.insert(170);
intset.insert(125);
intset.insert(80);
intset.insert(90);
intset.insert(50);
// 100
// / \
// 80 150
// /\ /\
// 50 90 125 170
// find 함수는 입력된 데이터랑 동일한 데이터가 있는지 찾아서 그 데이터를 가리키는 iterator 를 반환.
// 만약 해당 데이터가 컨테이너 안에 없었으면, end iterator 를 반환
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));
// 100-1
// / \
// 80-5 150-2
// / \ / \
// 50-7 90-6 125-4 170-3
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));
// 100
// 50 150
// 25 75 125 170
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 = bst.end();
--TestIter;
--TestIter;
--TestIter;
--TestIter;
--TestIter;
--TestIter;
--TestIter;
TestIter = bst.find(100);
(*TestIter).first;
(*TestIter).second;
TestIter->first;
TestIter->second;
if (bst.end() != TestIter)
{
bst.erase(TestIter);
}
return 0;
}
// 중위 선행자 구하기
// BST iterator -- 구현하기
// 1. erase 구현 마무리
// 2. iterator -> operator
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);
}
private:
// 중위 후속자, 선행자 찾기
BSTNode<T1, T2>* FindInOrderSuccessor(BSTNode<T1, T2>* _TargetNode);
BSTNode<T1, T2>* FindInOrderPredecessor(BSTNode<T1, T2>* _TargetNode);
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;
}
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 ++()
{
assert(m_Owner);
// 중위 후속자(InOrder Successor) 찾아서 가리킨다.
m_TargetNode = m_Owner->FindInOrderSuccessor(m_TargetNode);
if (nullptr == m_TargetNode)
{
wcscpy_s(this->m_szDesc, L"End");
}
return (*this);
}
iterator& operator--()
{
assert(m_Owner);
// 중위 선행자 찾아서 가리킨다.
m_TargetNode = m_Owner->FindInOrderPredecessor(m_TargetNode);
// 중위 선행자를 찾을수 없었다(nullptr)
// ==> Begin Iterator 에 -- 함수를 호출한 상황
assert(m_TargetNode);
// 찾은 중위선행자가 맨 처음이라면
if (!m_TargetNode->HasLeftChild())
{
wcscpy_s(m_szDesc, L"Begin");
}
else
{
// 상태설명 갱신
wcscpy_s(m_szDesc, L"");
}
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)
{
BSTNode<T1, T2>* pSuccessor = nullptr;
// 삭제할 노드가 리프노드인 경우 (자식이 0개)
if (_target.m_TargetNode->IsLeaf())
{
// 삭제할 노드의 후속자를 찾는다.
pSuccessor = FindInOrderSuccessor(_target.m_TargetNode);
// 1. 삭제하려는 노드가 루트 노드인 경우
if (_target.m_TargetNode->IsRoot())
{
// 루트노드를 삭제하고, m_Root 포인터를 nullptr 로 변경한다.
delete m_Root;
m_Root = nullptr;
}
// 2. 루트노드는 아니다. (리프노드만)
else
{
// 부모 노드로 가서 삭제될 노드를 가리키는 포인터를 nullptr 로 변경한다.
if (_target.m_TargetNode->IsLeftChild())
{
_target.m_TargetNode->pParent->pLeftChild = nullptr;
}
else
{
_target.m_TargetNode->pParent->pRightChild = nullptr;
}
// 해당 노드를 메모리 해제한다.
delete _target.m_TargetNode;
}
// 데이터 개수를 하나 줄인다.
--m_CurCount;
// 삭제된 노드의 다음(후속자) 을 가리키는 iterator 를 반환해준다.
return iterator(this, pSuccessor);
}
// 자식이 2개 있는 경우
else if (_target.m_TargetNode->IsFull())
{
// 삭제할 노드의 후속자를 찾는다.
pSuccessor = FindInOrderSuccessor(_target.m_TargetNode);
assert(pSuccessor);
// 중위 후속자 노드의 데이터를 삭제할 노드의 데이터로 복사시킨다.
_target.m_TargetNode->pair = pSuccessor->pair;
// 자식이 2개인 노드의 후속자는 자식이 1개 또는 0개 이다.
// erase 함수를 재귀호출해서 자식이 1개 or 0 개인 노드를 삭제하는 부분을 해결한다.
// 이때 erase 안에서 데이터 개수를 줄이므로 여기서 다시 또 데이터개수를 줄일 필요가 없다.
erase(iterator(this, pSuccessor));
// 삭제된 노드의 후속자가 가진 데이터가 삭제할 노드로 복사되었기 때문에
// 원래 삭제하려고 했던 노드가 다시 삭제된 다음노드가 되었다.
return iterator(this, _target.m_TargetNode);
}
// 자식이 1개 있는 경우
else
{
pSuccessor = FindInOrderSuccessor(_target.m_TargetNode);
// 삭제할 노드가 루트인 경우
if (_target.m_TargetNode->IsRoot())
{
// 하나뿐인 자식을 루트로 만든다.
if (_target.m_TargetNode->HasLeftChild())
{
m_Root = _target.m_TargetNode->pLeftChild;
}
else
{
m_Root = _target.m_TargetNode->pRightChild;
}
m_Root->pParent = nullptr;
}
// 삭제할 노드가 왼쪽 자식이다.
else if (_target.m_TargetNode->IsLeftChild())
{
// 보유한 자식이 왼쪽 자식이다.
if (_target.m_TargetNode->HasLeftChild())
{
_target.m_TargetNode->pLeftChild->pParent = _target.m_TargetNode->pParent;
_target.m_TargetNode->pParent->pLeftChild = _target.m_TargetNode->pLeftChild;
}
// 보유한 자식이 오른쪽 자식이다.
else
{
_target.m_TargetNode->pRightChild->pParent = _target.m_TargetNode->pParent;
_target.m_TargetNode->pParent->pLeftChild = _target.m_TargetNode->pRightChild;
}
}
// 삭제할 노드가 오른쪽 자식이다.
else
{
if (_target.m_TargetNode->HasLeftChild())
{
_target.m_TargetNode->pLeftChild->pParent = _target.m_TargetNode->pParent;
_target.m_TargetNode->pParent->pRightChild = _target.m_TargetNode->pLeftChild;
}
else
{
_target.m_TargetNode->pRightChild->pParent = _target.m_TargetNode->pParent;
_target.m_TargetNode->pParent->pRightChild = _target.m_TargetNode->pRightChild;
}
}
// 해당 노드를 메모리 해제한다.
delete _target.m_TargetNode;
// 데이터 개수를 하나 줄인다.
--m_CurCount;
return iterator(this, pSuccessor);
}
}
template<typename T1, typename T2>
BSTNode<T1, T2>* BST<T1, T2>::FindInOrderSuccessor(BSTNode<T1, T2>* _TargetNode)
{
// 오른쪽 자식이 있으면
if (_TargetNode->HasRightChild())
{
// 오른쪽 자식으로 간다.
BSTNode<T1, T2>* pNextNode = _TargetNode->pRightChild;
// 왼쪽자식이 없을 때 까지 내려간다.
while (pNextNode->pLeftChild) { pNextNode = pNextNode->pLeftChild; }
return pNextNode;
}
// 오른쪽 자식이 없으면
else
{
BSTNode<T1, T2>* pNextNode = _TargetNode;
// 부모의 왼쪽 자식일때 까지 올라가서 그때 부모가 나의 중위 후속자
while (true)
{
if (pNextNode->IsRoot())
{
// 현재 노드가 가장 마지막 노드이다(중위 후속자를 찾기전에 루트노드에 도달)
// -> end iterator 로 변경
return nullptr;
}
else if (pNextNode->IsLeftChild())
{
return pNextNode->pParent;
}
else
{
pNextNode = pNextNode->pParent;
}
};
}
}
template<typename T1, typename T2>
BSTNode<T1, T2>* BST<T1, T2>::FindInOrderPredecessor(BSTNode<T1, T2>* _TargetNode)
{
// End Iterator 인데 -- 를 호출받은 경우
if (nullptr == _TargetNode)
{
BSTNode<T1, T2>* pNode = m_Root;
while (pNode->pRightChild) { pNode = pNode->pRightChild; }
return pNode;
}
// 중위 선행자(InOrder Predecessor)
// 왼쪽 자식이 있으면
else if (_TargetNode->HasLeftChild())
{
// 왼쪽 자식으로 간다.
BSTNode<T1, T2>* pNextNode = _TargetNode->pLeftChild;
// 오른쪽 자식이 없을 때 까지 내려간다.
while (pNextNode->pRightChild) { pNextNode = pNextNode->pRightChild; }
return pNextNode;
}
// 왼쪽 자식이 없으면
else
{
BSTNode<T1, T2>* pNextNode = _TargetNode;
// 부모의 오른쪽 자식일때 까지 올라가서, 그때 부모가 나의 중위 선행자
while (true)
{
if (pNextNode->IsRoot())
{
// 현재 노드가 가장 처음 노드이다(중위 선행자를 찾기전에 루트노드에 도달)
// -> assert, begin 이전으로 갈 수 없다.
return nullptr;
}
else if (pNextNode->IsRightChild())
{
return pNextNode->pParent;
}
else
{
pNextNode = pNextNode->pParent;
}
};
}
}
1차 24.01.10
2차 24.01.11
3차 24.01.12
4차 24.01.15
5차 24.01.16
:D