BST
for (myIter = cbs.begin(); myIter = cbs.end(); ++myIter)
{
cout << myIter.m_i_nodeAddr->pair->first << myIter.m_i_nodeAddr->pair->second << endl;
}원래는 이렇게 접근이 가능한데
이게 아니라 '->' 연산자를 제공을 하게 만들어서
for (myIter = cbs.begin(); myIter = cbs.end(); ++myIter)
{
cout << myIter->first << myIter->second << endl;
}이렇게 접근이 가능 하도록 만들어야한다.
* 연산자 및 비교연산자 구현하기
- 로 iterator 접근을 하면 pair가 나와 주어야한다.
bool operator == (const iterator& other)
{
if (m_i_bstNode == other.m_i_bstAddr && m_i_nodeAddr == other.m_i_nodeAddr)
return true;
return false;
}
bool operator != (const iterator& other)
{
return !(*this == other)
}
const Pair<T1, T2>& operator *()
{
// nullptr이라면 assert (end iterator인지 아닌지)
assert(m_i_nodeAddr);
return m_i_nodeAddr->pair;
}이렇게 *연산자와 함께 구현을 해주었는데
pair에 접근을 할 때
(*myIter).first;
*(myIter).second;이렇게 접근을 해야하는데
이것을
myIter->first;
myIter->second;이렇게 해주고 싶은 것이다.
'*', '->' 👍👍👍
const Pair<T1, T2>& operator *()
{
// nullptr이라면 assert (end iterator인지 아닌지)
assert(m_i_nodeAddr);
return m_i_nodeAddr->pair;
}
const Pair<T1, T2>* operator ->()
{
// nullptr이라면 assert (end iterator인지 아닌지)
assert(m_i_nodeAddr);
return &m_i_nodeAddr->pair;
}지금 다른점은 operator ->는 반환 타입이
Pair<T1, T2>* 주소값을 반환을 하고
return 부분에서도 m_i_nodeAddr->pair에다가
주소연산자 '&'를 사용해서 해당 노드의 페어의 주소를
전달해주고 있기때문에 반환타입이랑 알맞다. (코드 좋은듯?)
참조자의 설명 ❗❗❗
- reference
변수라고 하는 것은 할당된 메모리 공간에 붙여진 이름이다. 우리는 이 이름을 가지고 해당 메모리 공간에 접근이 가능해진다. 그러면 참조자는 무엇일까? 참조자는 할당된 하나의 메모리 공간에 다른 이름을 붙이는 것을 말한다.
그래서
const Pair<T1, T2>& operator *()
{
// nullptr이라면 assert (end iterator인지 아닌지)
assert(m_i_nodeAddr);
return m_i_nodeAddr->pair;
}이렇게 operator *를 정의를 했을 때
이것을 사용을 할려면
(*myIter).first;이렇게 사용했었는데 operator * 가 반환을 하는 것이
m_i_nodeAddr의 pair인데 이것을 "참조"로 반환을 하겠다는 것이다.
그러면 메모리 공간의 다른 이름을(지금은 다른 이름을 부여하지는 않았지만)
"참조"로써 반환을 하기 때문에
구조체 그자체가 반환이 되어서 '.' 으로 first에 접근이 가능한 것이다.
int num = 10;
int& num2 = num1;
cout << num << endl; // 10
cout << num2 << endl; // 10
cout << &num << endl; // num의 메모리 주소값 => 0x00FFA10
cout << &num2 << endl; // num2의 메모리 주소값 => 0x00FFA10
그때도 말한 것처럼 스택이라는 메모리 안에
| 주소 (메모리 주소) | 변수명 (메모리 공간에 붙여진 이름) | 값 (들어있는 값) |
|---|---|---|
| 0x00FA1234 | num | 10 |
| 0x00FA2222 | num2 | 0x00FA1234 |
이거는 맞다. 다만 vs에 찾을 포인터 변수의 주소값을 찾을려고하니까
못찾겠다.
중위 순회 기준으로
In Order Successor ( 중위 후속자 )
In Order Predeccessor (중위 선행자)
기능을 제공을 해야한다.
operator ++ (--) 은 iterator의 연산자 이지만
중위 선행자, 후속자를
BST 에서 제공을 하겠다라는 말이다. (Cbst 클래스에 제공한다는 말)
operator ++ 구현
이게 끝이다.
이렇게 구현을 해주도록 하자.
중위 후속자, 선행자 규칙 ❗
우선순위는
1 순위 : 오른쪽 자식 보유
2 순위 : 왼쪽 자식인 경우, 부모가 중위 후속자
< 설명 >
k의 중위 후속자 찾는 법은
현재 k는 e의 오른쪽 자식이다. k의 자식은 없다.
그러면 부모인 e로 올라간다 -> e도 도 b의 오른쪽 자식이다.
그러면 b로 올라간다. -> b는 a의 왼쪽 자식이다.
b는 a의 왼쪽 자식이기 때문에 k의 중위 후속자를 a로 해준다.
부모가 왼쪽 자식이 될 떄까지 올라가면된다. 그러면 왼쪽 자식일 경우
부모가 바로 중위 후속자 이기 때문에.
왼쪽 자식의 경우에는 중위후속자가 가능
자신의 부모 이다.
그런데 오른쪽 자식을 보유한다고 해서 무조건
"오른쪽 자식"이 "중위 후속자"는
A의 중위 후속자는?
오른쪽 자식으로 내려가서 왼쪽 자식이 없을때까지 내려간다.
중위 후속자 구현
template<typename T1, typename T2>
inline typename BstNode<T1, T2>* Cbst<T1, T2>::GetInOrderSuccessor(BstNode<T1, T2>* nodeAddr)BstNode * 를 뱉어주는 GetInOrderSuccessor 함수를 보도록 하자.
첫번쨰 경우
- 오른쪽 자식이 있는 경우, 오른쪽 자식으로 가서, 왼쪽 자식이 없을때 까지 내려감
BstNode<T1, T2>* successor = nullptr;
if (nullptr != nodeAddr->nodeArrayAddr[(int)NodeType::RCHLID])
{
successor = nodeAddr->nodeArrayAddr[(int)NodeType::RCHLID];
while (successor->nodeArrayAddr[(int)NodeType::LCHILD])
{
successor = successor->nodeArrayAddr[(int)NodeType::LCHILD]
}
}
return successor;successor가 nullptr이 될때까지
successor = successor->nodeArrayAddr[(int)NodeType::L];이 작업을 반복을 해준다.
(이해 OK)
두번쨰 경우
bool IsRoot()
{
if (nullptr == nodeArrayAddr[(int)NodeType::PARENT])
return true;
return false;
}
bool IsLeftChild()
{
if (nodeArrayAddr[(int)NodeType::PARENT]->nodeArrayAddr[(int)NodeType::LCHILD] == this)
return true;
return false;
}
bool IsRightChild()
{
if (nodeArrayAddr[(int)NodeType::PARENT]->nodeArrayAddr[(int)NodeType::RCHLID] == this)
return true;
return false;
}먼저 이렇게 뚫어놓고 다시 GetInOrderSuccessor 구현 다시 시작하면 된다.
최종 코드
template<typename T1, typename T2>
inline typename BstNode<T1, T2>* Cbst<T1, T2>::GetInOrderSuccessor(BstNode<T1, T2>* nodeAddr)
{
BstNode<T1, T2>* successor = nullptr;
// 1. 오른쪽 자식이 있는 경우, 오른쪽 자식으로 가서, 왼쪽 자식이 없을때 까지 내려감
if (nullptr != nodeAddr->nodeArrayAddr[(int)NodeType::RCHLID])
{
successor = nodeAddr->nodeArrayAddr[(int)NodeType::RCHLID];
while (successor->nodeArrayAddr[(int)NodeType::LCHILD])
{
successor = successor->nodeArrayAddr[(int)NodeType::LCHILD]
}
}
// 2. 부모로 부터 왼쪽자식일 때 까지 위로 올라감.
// 그떄 부모가 후속자
else
{
successor = nodeAddr;
while (true)
{
// 먼저 부모가 있는지 없는지를 확인 해야함
// 루트 노드인지 아닌지 확인하기 위해서
if (successor->IsRoot())
return nullptr;
// Root가 아닐 때 내가 왼쪽 자식이냐? 라고 물어봤을 때
// 부모가 successor(후속자)이다.
if (successor->IsLeftChild()) // 부모로부터 왼쪽자식인지 체크
{
// 그때 부모가 후속자
successor = successor->nodeArrayAddr[(int)NodeType::PARENT];
break;
}
else // 부모로 부터 오른쪽 자식이니까 올라가는 작업
{
successor = successor->nodeArrayAddr[(int)NodeType::PARENT];
// 올라갔는데 왼쪽 자식이길 기대를 하면서 올라가는 것임.
}
}
}
return successor;
}그 다음
operator ++
iterator& operator ++()
{
m_i_nodeAddr = m_i_bstAddr->GetInOrderSuccessor(m_i_nodeAddr);
return *this;
}이제 좀 반복되는 부분 줄이러 가보도록 하자.
