C++ 기초 : tree (8)

---

iterator 통해서 이진 탐색 트리를 

순회할 수 있어야겠죠?

 

iterator는 만들었지만

아래 for 문처럼

 

 

iterator의 값을 하나씩 올리면서 

iterator가 가리키는 노드의 키-값을 출력하는 반복문을,

iterator의 값이 nullptr, 즉 end iterator가 아닌 경우 계속

반복하려면 구현해야 할 연산자 오버로딩이 많습니다.

 

 

우선 iterator끼리 비교하기 위한

비교 연산자를 오버로딩해 봅시다.

 

== 연산자와 != 연산자를 오버로딩하였습니다.

 

먼저 == 연산자를 오버로딩한 부분부터 보시죠.

 

iterator가 서로 같은지, 다른지 비교하여 

같으면 true 다르면 false를 반환하는 함수입니다.

 

그래서 반환 타입은 bool형이죠.

 

단순 비교를 위한 연산자이기 때문에

비교 대상이 되는 다른 iterator를 const형 레퍼런스로

참조합니다. 비교 대상이 되는 iterator의 값을 수정할 일이 

없고, 복사할 필요 없이 바로 참조하여 값을 비교하기

위해서이죠.

 

 

if 문을 통해 iterator의 모든 멤버가 모두 같은 경우에만

같다고 판단하여 true를 반환합니다. 아니면 false를 반환하죠.

 

 

 

다음은 != 연산자 부분입니다.

 

반환 타입과 매개 변수는 == 연산자와 같습니다.

 

다른 점은 == 연산자와는 반대로 작동해야 하기 때문에

우선 해당 연산자를 호출한 왼쪽 iterator와

비교 대상이 되는 오른쪽 iterator를 인자로 == 연산자에 넘깁니다.

 

그리고 반환받은 결과가 true면 ! 연산을 하여 false를 반환,

false를 반환받았다면 true를 반환합니다.

 

 

---

 

 

 

다음은 * 연산자와 -> 연산자를 오버로딩할 것입니다.

 

먼저 * 연산자부터 보겠습니다. 

 

* 연산자로 iterator를 역참조를 하려는데

해당 iterator가 아무런 노드를 가리키고 있지 않으면 

오류가 떠야겠죠?

 

그래서 특정 노드의 주솟값을 저장하고 있는

멤버 m_Node의 값이 nullptr이면 

assert 매크로를 통해 오류 창을 띄웁니다.

(해당 매크로를 사용하려면 include 지시문을 통해

"assert.h" 파일을 포함해야 합니다.)

 

그게 아니라면 m_Node가 가리키는 

노드로 가서 해당 노드가 저장하고 있는

pair 자를 참조하여 반환합니다.

 

 

* 연산자의 실행 결과를 확인해 보겠습니다.

 

iterator가 키-값이 50인 노드를 가리키고 있는 상황에서 

* 연산자를 통해 역참조하였습니다. 

 

이후 해당 노드가 저장하고 있는 pair 자체를 

참조하였기 때문에 멤버에 접근할 수 있게 됩니다.

멤버 first가 50을 저장하고 있기 때문에 

변수 a에는 50이 대입됩니다.

 

 

 

-> 연산자를 오버로딩한 부분을

살펴 보겠습니다.

 

마찬가지로 iterator가 아무런 노드를 가리키고 

있지 않다면 assert 매크로를 통해 오류 창을 띄웁니다.

 

assert 매크로는 nullptr을 인자로 받으면 오류 창을 

띄우는데 iterator가 아무런 노드를 가리키고 있지

않다면 m_Node가 nullptr이겠고, 이를 assert 매크로의

인자로 주면 오류 창이 출력되겠죠?

 

 

이번에는 iterator가 가리키는 노드로 가서

멤버 pair에 접근합니다. 그리고 이 pair의 

주솟값을 반환합니다. 이렇게 얻은 pair의 주솟값을 통해

바로 pair의 멤버에 접근할 수 있게 됩니다.

 

 

실행 결과를 보면

 

iterator가 -> 연산자를 호출하면서

pair의 주솟값이 반환되고 이를 통해 

pair의 멤버인 first에 바로 접근이 가능하게 됩니다.

 

iterator가 가리키는 노드 속 pair의 멤버 fist의 값은

50입니다. 이를 변수 a에 대입하자

정말 변수 a에 50이 대입되는 것을 확인할 수 있습니다.

 

 

더 쉽게 이해해 볼까요?

 

키-값이 100인 pair를 만들고 이를

가리키는 ppair라는 포인터를 만들었습니다. 

ppair가 pair를 가리키기 위해서 pair의 주솟값을

저장하고 있죠.

 

이후 pair의 주솟값만을 갖고 있는 ppair를 통해 

바로 pair의 멤버에 접근하는 모습이 보이시나요?

 

위와 같은 동작을 위해 

-> 연산자 오버로딩에서도 pair의 주솟값을

반환한 겁니다. pair의 주솟값을 알고 있다면

pair의 멤버 변수에 바로 접근이 가능하니까요.

 

 

 

---

 

 

 

 

이제는 ++ 연산자를 오버로딩해야겠죠.

 

++ 연산을 진행하면 다음 노드를 가리키게 될 겁니다.

이진 탐색 트리는 중위 순회를 기준으로 탐색을 진행하므로

중위 순회 기준으로 다음인 노드를 가리켜야 할 겁니다.

 

아래 코드를 보시면

 

일단 간략하게 ++ 연산자를 오버로딩하였습니다.

 

이진 탐색 트리를 관리하는 BST 내부에

중위 후속자(inorder sucessor)를 반환하는 함수를 만들어 

iterator가 이를 가리키도록 한 후 해당 iterator를 반환하면

되겠죠. (중위 후속자는 중위 순회 기준으로 다음인 노드를

의미합니다.)

 

그럼 iterator에 ++ 연산을 하게 되면

iterator가 중위 후속자, 즉 다음 노드를 가리키게 되겠죠.

 

 

그럼 GetInOrderSuccessor 함수의 정의를 살펴 보겠습니다.

 

특정 노드를 인자로 받으면 이를 노드를 가리키는 포인터

pSuccessor에 대입합니다. 

 

 

이후 포인터 pSucessor가 가리키는 노드의

후속자를 찾아야 하는데 만약 아래 그림과 같은

이진 탐색 트리가 있다고 가정해 봅시다.

 

100의 중위 후속자는 오른쪽 자식인 150이죠?

 

25의 중위 후속자는 오른쪽 자식이 없으므로

부모 노드인 50이 중위 후속자입니다.

만약 오른쪽에 30이 자식으로 있었다면 30이 

중위 후속자였겠죠.

 

75의 중위 후속자는 오른쪽 자식인 80입니다.

 

그럼 이번에는 50의 중위 후속자를 찾아 볼까요.

오른쪽 자식인 75라고 생각했는데 75에 왼쪽 자식이 있네요.

그럼 50의 중위 후속자는 60이죠?

 

이를 통해 알 수 있는 건 일단 오른쪽 자식이 

있느냐 없느냐가 상당히 중요하다는 것을

알 수 있습니다. 

 

 

211 ~ 221번째 코드가 바로 이 내용입니다.

 

현재 가리키고 있는 노드가 오른쪽 자식을 갖고 있다면

오른쪽 자식으로 갑니다. 근데 해당 자식이 왼쪽 자식을 갖고

있다면 왼쪽 자식으로 내려갑니다. 이후 왼쪽 자식이

없을 때까지 계속 이진 탐색 트리를 내려가는 겁니다.

 

그러다가 왼쪽 자식이 더 이상 존재하지 않을 경우

while 문과 if 문을 빠져 나와 포인터 pSuccessor가

가리키고 있던 최종 왼쪽 자식 노드를 반환합니다.

 

 

근데 위 그림의 25, 60, 80, 150처럼

오른쪽 자식 노드가 존재하지 않는 경우도 있죠.

 

그런 경우 포인터 pSuccessor가 현재 가리키고

노드가 어떤 노드의 왼쪽 자식인지 오른쪽 자식인지,

부모 노드가 존재하기는 하는지 따져 봐야 합니다.

 

그래서 아래 코드처럼

 

노드 역할을 하는 tBSTNode 클래스 템플릿에

노드 자신이 부모 노드면 true를, 아니면 false를 반환하는 함수와

노드 자신이 왼쪽 노드면 true를, 아니면 false를 반환하는 함수,

노드 자신이 오른쪽 노드면  true를, 아니면 false를 반환하는 함수를

만들어 줍니다.

 

자신의 부모 노드가 nullptr이면

자신이 루트 노드라는 의미겠죠.

 

자신과 자신의 부모 노드의 왼쪽 자식 노드가 같으면

자신은 특정 노드의 왼쪽 노드라는 의미겠고,

자신과 자신의 부모 노드의 오른쪽 자식 노드가 같으면

자신은 특정 노드의 오른쪽 노드라는 의미겠죠.

 

 

다시 GetInOrderSuccessor 함수로 돌아와서,

222 ~ 245번째 코드가 오른쪽 자식이 없는 경우

실행되는 코드입니다.

 

먼저 228번째 줄에 있는 if 문을 보시죠.

 

이는 150과 같이 다음 노드가 존재하지 않아

중위 후속자가 없는 경우를 위한 if 문입니다.

후속자가 없으면 nullptr을 반환하죠.

 

pSuccessor가 위 그림과 같은

이진 탐색 트리에 있는 150을 가리키고 있다고 합시다.

150은 100의 오른쪽 자식이니까 

240번째 줄에 있는 else 문에 걸릴 겁니다.

pSuccessor는 이제 150의 부모 노드인

100을 가리키고 있겠죠.

 

이후 다시 while 문을 돕니다.

 

pSuccessor가 가리키는 노드(100)는

루트 노드이기 때문에 부모 노드가 존재하지 않습니다.

그래서 nullptr을 반환하죠.

 

nullptr을 반환받았으므로 150의 후속자가 없음을 의미합니다.

 

 

234번째 줄은 자신이 특정 노드의 왼쪽 자신인 경우입니다.

pSuccessor가 가리키는 노드를 IsLeftChild 함수를 통해

왼쪽 자식인지 아닌지 판단하고 왼쪽 자식이라면

true를 반환하게 되어 234번째 줄에 있는 if 문이 작동할 겁니다.

 

포인터 pSuccessor는 이제 부모 노드를 가리키게 되고

이를 바로 반환합니다. 위 그림에서 25가 저장된 노드가

해당 if 문에 걸리겠죠.

 

 

240번째 줄에 있는 else 문은

자신이 오른쪽 자식인 경우입니다.

 

위 그림에서 80의 중위 후속자를 구하는 경우죠.

자신이 오른쪽 자식이면서 자신의 오른쪽 자식이

존재하지 않는다면 다음 노드는 멀리 있다는 겁니다.

 

이를 찾기 위해서 계속 부모 노드로 올라가야 하죠.

 

올라가서 도착한 부모 노드가 어떤 노드의

왼쪽 자식 노드일 경우, 234번째 줄에 있는 if 문에 

걸리게 되며 부모 노드를 중위 후속자로 반환하게 됩니다.

 

 

---

강의 출저 : https://www.youtube.com/watch?v=HtI_0WXjCGY&list=PL4SIC1d_ab-aOxWPucn31NHkQvNPHK1D1&index=78

---