C++ 기초 : tree (10)
DeleteNode 함수를 통해 제거하려는 노드가
단말 노드(Leaf Node)인 경우를 작성하였으니
이번에는 제거하려는 노드의 자식이 1개 있는 경우와
두 개 있는 경우의 동작을 작성하도록 하겠습니다.
먼저 자식 노드가 한 개인 경우입니다.
제거하려는 노드가 보유하고 있는 자식이
오른쪽 자식이냐, 왼쪽 자식이냐를 먼저 따져 봅니다.
NODE_TYPE enum 클래스를 통해 객체를 하나 만들고
제거하려는 노드가 보유하고 있는 자식이 우선 왼쪽이라고
가정합시다. 이 상태에서 만약 오른쪽 자식을 보유하고 있어
438번째 줄에 있는 if 문에 걸리면 NODE_TYPE 형 객체에
RCHILD를 대입하여 오른쪽 자식이 있음을 나타냅니다.
제거하려는 노드가 루트 노드일 경우에는
루트 노드를 가리키는 BST의 멤버 pRootNode가
제거하려는 노드의 자식 노드를 가리키도록 한 후,
제거하려는 노드의 자식 노드의 부모 부분을 nullptr로 합니다.
제거하려는 노드의 자식 노드가
부모 노드가 없는 상태, 즉 루트 노드가 되게 하는 것이죠.
제거하려는 노드가 루트 노드가 아닌 경우,
두 가지 분기점이 생깁니다.
제거하려는 노드 자신이 왼쪽 노드이냐,
오른쪽 노드이냐에 따라 말이죠.
그래서 왼쪽 자식이 맞다면 true를 아니면 false를 반환하는
IsLeftChild 함수를 통해 제거하려는 노드를 검사합니다.
만약 왼쪽 자식이라서 true를 반환하게 되면
451번째 줄에 있는 if 문에 걸리겠죠.
제거하려는 노드의 부모 노드로 가서
왼쪽 자식 부분에 내 자식을 대입합니다.
내가 오른쪽 자식이라면 455번째 줄에 있는
else 문에 걸릴 겁니다. 제거하려는 노드의
부모 노드로 가서 오른쪽 자식 부분에 내 자식을 대입합니다.
그리고 두 분기점 모두 공통적으로 실행되어야 하는 것은
제거하려는 노드가 보유한 자식 노드로 가서 부모 부분에
제거하려는 노드의 부모 노드를 대입하는 것입니다.
이러면 제거하려는 노드의 자식 노드가
제거하려는 노드의 부모 노드를 가리키게 되겠죠.
이후 제거하려고 했던 노드를
delete를 통해 메모리 해제하여 제거합니다.
노드가 하나 사라진 것이므로
BST 내에 있는 노드의 개수를
나타내는 iCount의 값을 하나 내립니다.
아래 코드는 자식 노드가 두 개인 경우
실행되는 코드입니다. 특정 노드가
두 개의 자식 노드를 갖고 있는지 확인하는
IsFullNode 함수를 통해 제거하려는 노드가
두 개의 자식을 갖고 있는지 확인합니다.
IsFullNode 함수가 true를 반환하여
제거하려는 노드가 두 개의 자식을 갖고 있다고
판단되면 중위 후속자가 갖고 있는
pair(키-값과 실질적인 데이터로 이루어짐) 데이터를
제거하려는 노드가 갖고 있는 pair에 복사합니다.
아래 그림에서
50을 제거한다고 할 때 pSuccessor는 60을 가리키고 있다가
426번째 줄 코드에 의해 60이 50에 복사가 되는 겁니다.
그럼 아래 그림처럼 되겠죠.
이 상태에서 DeleteNode 함수를 또 호출하여
pSuccessor를 인자로 넣습니다. 그러면 pSuccessor가
가리키던 60이 제거가 되어 아래 그림처럼 될 겁니다.
그리고 430번째 줄 코드로 인해
이제 pSuccessor는 원래 50이 있었고
현재는 60이 있는 노드를 가리키게 되고
해당 노드를 반환하게 되겠죠.
428번째 줄에 있는 코드로 인해 DeleteNode 함수를
다시 호출했는데 자식 노드가 두 개인 경우가 발생하여
DeleteNode 함수가 무한 반복되는 일은 걱정하지 않아도
됩니다. 자식이 두 개인 노드의 후속자는 애초에 자식이
한 개 이상 존재할 수가 없습니다. 자식이 두 개인 노드의
후속자는 왼쪽 노드가 존재하지 않을 때까지 내려가서
얻어낸 노드이기 때문이죠. 오른쪽 노드는 존재할 수 있기
때문에 433번째 줄에 있는 else 문에 걸릴 수 있기는 합니다.
아무튼 후속자가 보유한 자식 노드가 두 개여서
DeleteNode 함수가 무한 반복되는 일은 없을 겁니다.
자식이 두 개 있는 루트 노드를 제거할 때
예외 처리를 해 줘야 하는지 고민이 됩니다.
하지만 자식이 두 개인 경우는 실제 루트 노드가
제거되는 것이 아니라, 루트 노드의 값을
중위 후속자의 값으로 덮어씌우고,
실제 중위 후속자가 있던 노드를 제거하는 방식이라
루트 노드의 주솟값을 저장하고 있는 멤버 pRootNode의
값은 바뀌지 않을 겁니다. 그래서 따로 예외 처리를
해 줄 필요는 없어 보이네요.
중요한 것은 --iCount; 구문입니다.
자식 노드가 없거나 한 개인 노드를
제거하는 경우에는 동작이 끝나면
iCount의 값을 하나 내렸죠?
그러나 자식 노드가 두 개인 노드를
제거하는 경우에는 동작이 끝나도
iCount의 값을 내리지 않았습니다.
이유는 428번째 줄에 있는 코드로 인해
DeleteNode 함수가 재귀 함수처럼
내부에서 다시 호출되기 때문이죠.
428번째 줄에 있는 DeleteNode 함수가
호출되고 종료되면서 이미 iCount의
값을 하나 내렸을 겁니다.
근데 자식 노드가 두 개인 노드를 제거하는
동작이 끝난 후 또 iCount의 값을
내리면 노드를 하나 제거했는데 iCount의 값이
두 개 내려가는 현상이 발생하겠죠.
erase 함수도 구현을 했으니
잘 작동하는지 확인해 봐야겠죠?
먼저 단말 노드를 제거하는 경우부터 살펴 봅시다.
위 코드의 주석처럼 이진 탐색 트리를 구성했습니다.
그리고 25를 제거한 후 iterator가 중위 후속자를
가리키게 할 예정이죠.
iterator의 값을 확인해 보니 25의 중위 후속자였던
50을 가리키고 있음을 확인할 수 있습니다.
BST의 멤버 iCount의 값이 7이 되었고,
루트 노드인 100의 왼쪽 자식인 50으로 가서
왼쪽 자식의 값이 nullptr인 것이 확인됩니다.
25가 잘 제거되었네요.
이번에는 단말 노드이면서 루트 노드인
노드를 제거해 보겠습니다.
100을 제거하였더니
iterator에는 nullptr이 대입되었습니다.
유일한 노드인 100은 후속자가 없기 때문이죠.
BST의 멤버 iCount의 값이 0이고
루트 노드도 존재하지 않는 것으로 확인이 됩니다.
이제는 자식 노드가 한 개 있는 노드를
제거해 보겠습니다.
아래 코드에서
150을 제거해 보죠.
150는 중위 순회 기준으로 마지막 노드라서
중위 후속자는 존재하지 않습니다.
그래서 erase 함수를 통해 반환된 iterator는 값이 nullptr이죠.
루트 노드의 오른쪽 자식 노드로 가서
값을 확인해 보니 125가 있네요.
그리고 125의 부모 노드를 보니
루트 노드인 100을 가리키고 있습니다.
잘 작동하네요.
자식이 한 개인 루트 노드를 제거해 보겠습니다.
루트 노드인 100을 제거하고
erase 함수를 통해 반환된 후속자는 150입니다.
그리고 BST의 루트 노드는
150이 되었죠.
이번에는 자식 노드가 두 개인 노드를
제거해 보겠습니다.
50을 제거해 보죠.
후속자를 대입한 iterator가
50의 후속자인 60을 가리키고 있습니다.
BST에서 루트 노드의 왼쪽 자식으로 가서
값을 확인해 보니 60이 있습니다.
그리고 60의 오른쪽 자식의 왼쪽 자식,
즉 원래 60이 있던 자리를 확인해 보니
nullptr이네요. 50이 있던 자리에 중위 후속자인
60을 복사하고 실제 중위 후속자인 60은 제거한 것이죠.
이번에는 루트 노드인 100을 제거합니다.
100의 중위 후속자는 125죠?
iterator에 125가 잘 대입되었습니다.
그리고 BST의 루트 노드를 보니
100의 중위 후속자인 125로 바뀌었습니다.
루트 노드의 왼쪽 자식은 여전히 50입니다.
또한 루트 노드의 오른쪽 자식은
여전히 150이죠.
그리고
루트 노드의 오른쪽 자식의 왼쪽 자식,
즉 원래 125가 있던 자리가 nullptr이 되었죠.
루트 노드인 100을 제거하려고 하자
100에다가 중위 후속자인 125의 값을 복사하고
실제 125는 제거한 것입니다.
강의 출처 : https://www.youtube.com/watch?v=PaoNFmlcYwU&list=PL4SIC1d_ab-aOxWPucn31NHkQvNPHK1D1&index=80