C++ 기초 : tree (9)

---

이번에는 -- 연산자를 오버로딩해 보겠습니다.

 

-- 연산자도 ++ 연산자를 오버로딩을 위해 

중위 후속자를 반환하는 함수를 구현한 것처럼

 

BST 역할을 하는 cBST 클래스 템플릿 내부에

GetInOrderPredecessor 함수를 만들어 줄 겁니다.

 

해당 함수는 중위 선행자를 반환하죠.

 

그리고 iterator가 반환된 중위 선행자를 가리키도록 합니다.

반환된 중위 선행자를 가리키는 해당 iterator를 반환하는 거죠.

-- 연산이 발생하면 중위 순회 기준으로

기존 노드의 이전 노드를 가리키는 iterator가 반환되는 겁니다.

 

 

GetInOrderPredecessor 함수는

 

GetInOrderSuccessor와 비슷한 방식으로 작동합니다.

 

다만 이번에는 중위 선행자를 구하는 것이기 때문에 

오른쪽이 아닌 왼쪽 자식의 여부가 중요하겠죠.

 

일단 노드를 가리키는 pSuccessor가 nullptr을 가리키게 하고,

케이스에 따라 pSuccessor가 특정 노드를 가리키게 하겠습니다.

(포인터 변수명을 바꾸지 못했네요. Successor의 철자가 틀리기도 하였고

현재 함수는 Successor가 아닌 Predecessor를 구하는 함수입니다. 죄송합니다.)

 

 

만약 선행자를 구하고자 하는 노드의

왼쪽 자식이 존재한다면 포인터 pSuccessor가

그 왼쪽 자식을 가리키게 합니다. 이후 포인터 pSuccessor가

가리키는 노드의 오른쪽 자식이 없을 때까지 오른쪽으로 내려갑니다.

 

그러다가 오른쪽 자식이 더 이상 없으면 while 문을 빠져 나가면서

마지막으로 포인터 pSuccessor가 가리키는 노드를 

선행자로 반환합니다.

 

아래 그림에서 100이 키-값인 노드가 이 경우에 해당하겠죠?

 

 

근데 왼쪽 자식이 없는

25, 60, 80, 150 같은 경우에는 조금 더

따져 봐야 할 것이 있습니다.

 

먼저 25의 선행자를 구하려는 경우

284번째 줄에 있는 if 문에 의해 nullptr이 반환될 겁니다.

 

25는 왼쪽 자식이기 때문에 선행자를 구하기 위해

296번째 줄에 있는 else 문에 의해 부모 노드로

올라가게 됩니다. 원래는 올라가다가 290번째 줄에 있는 

if 문에 의해 선행자가 반환되어야 하지만

25는 선행자가 존재하지 않기 때문에 계속 올라가다가 

결국 루트 노드를 만나게 되겠죠. 그때까지

290번째 줄에 있는 if 문에 걸리지 않았다는 것은

선행자가 없다는 것입니다.

 

 

60의 선행자를 구하려는 경우에는

60은 왼쪽 자식이므로 296번째 줄에 있는

else 문에 의해 부모 노드로 올라갈 겁니다.

 

그렇게 75까지 올라갑니다. 75는 오른쪽 자식이죠?

그래서 290번째 줄에 있는 if 문에 의해 75의 부모 노드,

즉 50을 선행자로 반환합니다. 

 

 

80의 선행자를 구하려는 경우는

80 본인이 오른쪽 자식이므로 부모 노드가

바로 선행자이죠.

 

 

150도 마찬가지입니다.

 

 

 

++ 연산자를 중위 후속자(inorder successor)를

반환하는 함수를 통해 오버로딩하였고

 

-- 연산자를 중위 선행자(inorder predecessor)를

반환하는 함수를 통해 오버로딩하였습니다.

 

 

-- 연산자를 통해 iterator가 중위 순회 기준, 가장 마지막 노드를 

가리키고 있다가 가장 처음 노드까지 차례대로 가리키면서

값을 출력하는 동작과 

 

++ 연산자를 통해 iterator가 중위 순회 기준, 가장 처음 노드를 

가리키고 있다가 가장 마지막 노드까지 차례대로 가리키면서

값을 출력하는 동작을 해 보겠습니다.

 

이진 탐색 트리에 노드가 잘 정렬되어 있기 때문에 

값이 중위 순회 순서대로 잘 출력되는 것이 확인됩니다.

 

 

---

 

 

 

이번에는 특정 노드를 삭제하는 erase 함수를 구현하려고 합니다.

 

만약 erase 함수가 존재한다면

아래와 같이 사용할 수 있겠죠.

 

find 함수를 통해 iterator가 특정 노드를 가리킬 수 있도록

하고 이를 erase 함수에 인자로 넣어 iterator가 가리키는

특정 노드를 제거하는 것이죠.

 

기본적으로 제공하는 vector, list, map(이진 탐색 트리) 등의

erase 함수는 제거한 노드의 다음 노드를 반환합니다.

 

BST(Binary Search Tree, 이진 탐색 트리)에서는 

중위 후속자를 반환한다고 볼 수 있겠네요.

 

 

 

노드를 제거할 때 따져 봐야 할 것이 크게 세 가지가 있습니다.

 

먼저 제거할 노드가 단말 노드(Leaf Node)일 때입니다.

이 경우 자식 노드가 존재하지 않기 때문에 부모 노드의 자식 노드 부분을

nullptr로 하고 제거를 진행하면 되죠.

 

 

 

예를 들어 위 그림에서 20을 제거한다고 할 때

우선 부모 노드인, 키-값이 50인 노드의 왼쪽 자식 부분을

nullptr로 바꾸고 키-값이 25인 노드의 메모리를 해제하면 되겠죠.

 

80을 제거한다고 하면 키-값이 75인 노드의 오른쪽 자식 부분을

nullptr로 바꾸고 키-값이 80인 노드의 메모리를 해제하면 되겠고요.

 

 

두 번째로 자식 노드가 한 개인 경우입니다.

 

제거하려는 노드의 부모 노드의 자식 부분이

제거하려는 노드의 자식을 가리키도록 하고,

제거하려는 노드의 자식의 부모 부분이

제거하려는 노드의 부모를 가리키도록 합니다.

 

그리고 제거하면 되겠죠.

 

위 그림에서 150을 제거한다고 할 때,

150의 부모 노드 100이,

150의 자식 노드 170을 가리키게 하고

150의 자식 노드 170이

150의 부모 노드 100을 가리키게 하면 됩니다.

 

그리고 150을 메모리 해제하면 되죠.

 

 

세 번째로 자식 노드가 두 개인 경우입니다.

 

아래 그림을 보시죠.

 

 

만약 자식 노드가 두 개인 75를 제거한다고 합시다.

 

그럼 75 자리에는 60이 와야 할까요, 80이 와야 할까요?

 

 

이 고민을 하기 전에 이진 탐색 트리인 위 그림의 트리가

어떻게 중위 순회되는지 생각해 봐야 합니다.

 

25 - 50 - 55 - 60 - 70 - 75 - 79 - 80 - 90 - 100 - 150 - 170

 

이렇게 순회되겠죠? 여기서 75를 뺍니다.

 

 

25 - 50 - 55 - 60 - 70 - 79 - 80 - 90 - 100 - 150 - 170

 

보이시나요? 사실 75가 제거된 자리에는

60이나 80이 아닌, 중회 순회 기준 70 또는 79가

와야 하는 것입니다.

 

 

여기서 75가 있던 자리에 70이나 79를 

어떻게 놓을 수 있을까요? 상당히 많은 부모와

자식 간의 연결 관계를 재구성해야 할 겁니다.

 

근데 그렇게 할 필요 없이 노드의 데이터를 

복사하면 됩니다. 예를 들어 후속자로 제거된 자리를

대체한다고 하면 79의 데이터를 75에 복사하는 거죠. 

 

그리고 원래 79가 있던 노드를 제거하는 겁니다. 

 

이렇게 되면 

 

위 그림에서 볼 수 있듯이 이진 탐색 트리의

정렬 구조를 훼손하지 않고 75를 제거할 수 있습니다.

 

 

그럼 여기서 이런 경우가 떠오를 수 있습니다.

 

자식 노드가 두 개인 노드를 제거하기 위해 후속자의

데이터를 복사하고 후속자가 있던 노드를 제거하려고 하는데,

후속자가 또 두 개의 자식을 갖고 있는 경우입니다.

그러면 또 위 과정을 반복할까요?

 

따지고 보면 그렇지 않습니다. 

 

후속자라는 것은 왼쪽 자식 노드가 없을 때까지

내려가면서 얻어낸 것이기 때문에 적어도 후속자가

왼쪽 자식은 갖고 있지 않죠.

 

 

하지만 분명 후속자는

오른쪽 자식을 갖고 있을 수는 있습니다. 

 

만약 두 개의 자식 노드를 보유한 노드를 제거하기 위해

후속자의 값을 복사한 후, 후속자를 제거하려고 할 때

후속자가 오른쪽 자식을 보유하고 있으면

먼저 후속자의 부모 노드와 후속자의 오른쪽 노드를

연결해 주고 제거해 줘야겠죠?

 

 

 

---

 

 

 

 

아래 코드는 erase 함수를 구현한 것입니다.

 

387번째 줄의 의미는 

erase 함수를 호출한 이진 탐색 트리와

iterator가 가리키는 이진 탐색 트리가 다른 경우,

오류 창을 띄우겠다는 의미입니다.

 

A라는 이진 탐색 트리의 키-값이 10인 노드를 제거하려고 하는데

B라는 이진 탐색 트리의 키-값이 10인 노드를 가리키는

iterator를 통해 노드를 제거하면 문제가 발생하기 때문이죠.

 

근데 비교를 위해서는 iterator의 멤버 m_BST의 값을 얻어야 하는데

erase 함수는 BST가 호출하는 함수이기 때문에

BST의 inner 클래스인 iterator 클래스로 만든 객체의 멤버 m_BST에

접근할 수 없습니다. 그래서 iterator 클래스 끝에 friend class cBST<T1, T2>;

코드를 넣어 cBST 클래스 템플릿으로 만든 객체가

iterator의 멤버에 접근할 수 있도록 해야 합니다.

 

 

389번째 줄에서 DeleteNode라는 함수가 호출되었습니다.

 

erase 함수를 통해 다양한 경우의 수를 따져 

노드를 제거한 후 제거한 노드의 중위 후속자를 찾고, 

해당 중위 후속자로 iterator를 만들어 반환하려고 하면

erase 함수가 복잡해지겠죠.

 

그래서 노드를 제거하고 중위 후속자를 찾는 역할은

DeleteNode 함수가 하도록, 따로 만들었습니다.

해당 함수가 반환하는 중위 후속자를 erase 함수에서 받고

erase를 호출한 BST 자신과 받은 중위 후속자를 인자로 하여

iterator를 만들어 반환하게 되죠.

 

 

아래 코드는 DeleteNode 함수를 구현한 것입니다.

 

우선 pSuccessor 라는 tBSTNode<T1, T2>형 포인터를

선언하고 nullptr로 초기화합니다.

 

해당 포인터가 후속자를 가리키게 하고 이를 반환할 예정입니다.

 

바로 후속자를 가리키지 않고 nullptr로 초기화하는 이유는 

후속자를 가리키는 타이밍이 경우마다 다르기 때문입니다.

 

제거하려는 노드가 단말 노드인 경우

미리 후속자를 가리키면 되지만,

 

제거하려는 노드의 자식 노드가 두 개인 경우

후속자의 값을, 제거하려는 노드에 복사하고

실제로는 후속자인 노드를 제거하기 때문에

미리 후속자를 가리키게 되면 나중에 가리키던

후속자가 제거되면서 pSuccessor가 nullptr이 되겠죠?

 

그래서 해당 케이스에 맞는 타이밍에 후속자를

가리킬 수 있도록 우선은 nullptr로 초기화하고

케이스에 맞는 구문에 들어간 다음에

후속자를 가리키도록 하는 겁니다.

 

 

400번째 줄에 있는 if 문은 

제거하려는 노드가 leaf node인 경우입니다.

 

leaf node는 후속자가 그대로 보존되기 때문에 

후속자를 반환하는 GetInOrderSuccessor 함수를 통해 

pSuccessor가 바로 후속자를 가리키도록 하는 모습입니다.

 

404번째 줄에서 

제거하려는 노드가 루트 노드인지 확인합니다.

제거하려는 노드가  루트 노드라면 DeleteNode 함수를

호출한 BST의 루트 노드를 가리키는 멤버 pRootNude를

nullptr로 지정합니다.

 

제거하려는 노드가 루트 노드가 아니라면

408번째 줄에 있는 else 문이 실행되겠죠.

만약 제거하려는 노드가 왼쪽 자식 노드라면

제거하려는 노드의 부모 노드로 가서 왼쪽 자식 부분을

nullptr로 합니다. 

 

근데 그것이 아니라면, 즉 제거하려는 노드가 

오른쪽 자식이라면 제거하려는 노드의 부모 노드로 가서

오른쪽 자식 부분을 nullptr로 합니다.

 

 

연결 관계를 재설정했으면 이제 420번째 줄에서 

제거하려는 노드의 메모리를 해제합니다.

 

 

그리고 434번째 줄에서

노드가 하나 제거되었으므로 BST가 관리하는

노드의 개수를 나타내는 iCount의 값을 하나 내립니다.

 

 

---

강의 출처 : https://www.youtube.com/watch?v=nFFtB9r7TAI&list=PL4SIC1d_ab-aOxWPucn31NHkQvNPHK1D1&index=79

---