열혈 자료구조 p451를 보면
이진탐색트리의 삭제구현 중 상황 3: "삭제할 노드가 두 개의 서브트리를 가지는 경우"의
코드설명이 제시되어 있습니다.
여기서 어려운 부분인 단계3의 경우, 그림설명이 있다면 이해하는데 도움이 될 것이라고 생각합니다.
따라서 아래와 같은 구조를 가진 이진트리가 있다고 가정하고, 설명해보도록 하겠습니다.
그림에 제시된 것처럼 우리는 두번째 줄의 dnode를 삭제하는 과정을 살펴볼 것입니다.
p451의 본문에 제시되어 있는 것처럼, 노드를 삭제하는 단계는 총 3단계로 이루어져 있습니다.
1~3단계를 만들기 전에 설명된 부분을 편의상 0단계라고 부르도록 하겠습니다.
0단계. 준비단계
-대체노드를 정하기 위해, 우리는 dnode의 오른쪽 서브트리(RightSubTree) 중에서 가장 작은 값을 가지는 노드를
찾아내야 해야 합니다.
-먼저 dnode에서부터 출발할 것이기 때문에, dnode를 가리키는 포인터인 mpnode를 선언해줍니다
BTreeNode * mpNode = dNode-그리고 dnode의 RightSubTree에서 대체노드를 찾을 것이기 때문에, RightSubTree의 첫번째 노드를 가리키는 포인터를 하나 더 선언해줍니다. 이것은 mNode라고 이름지을 것입니다.
BTreeNode * mNode = GetRightSubTree(dNode)
1단계. 삭제할 노드(dnode)의 대체노드를 찾는다
-이제 원래 mnode 의 자리는 mpnode가 가리키고, mnode는 트리의 아래로 한칸 더 내려가는 과정이
while문을 통해 반복되면서, mnode가 노드의 끝부분, 가장 값이 작은 노드까지 도달하게 만들어 줄 것입니다.
-그 과정이 본문에는 다음과 같이 코드로 구현돼 있습니다. 이것을 부분으로 나누어 그림으로 설명하도록 하겠습니다.
③while(GetLeftSubTree(mNode) != NULL)
{
①mpNode = mnode;
②mnode = GetLeftSubTree(mNode);
}
1-①: *mpnode가 *mnode가 가리키는 노드를 가리키게 됩니다.
1-②:*mnode는 tree의 아래쪽으로 보내주는데, 가장 작은 값을 찾아야 하므로 왼쪽자식노드를 가리키게 만들어줍니다.
1-①, 1-② 를 수행하고 나면 while 조건문이 참인지 확인하게 되며, 아직 mnode의 왼쪽자식노드는 NULL이 아니기 때문에, while문은 반복 수행될 것입니다. 그 과정을 그림으로 나타내면 아래와 같습니다.
그림처럼 mdone가 2에 도달함으로써, dnode의 rightsubtree 중에서 가장 작은 값을 저장한 노드를 가리키게 됩니다.
우리는 이 mnode를 dnode를 대체할 노드로 이용할 것입니다.
작은 값을 찾기 위해 mnode는 계속 왼쪽으로 내려오기 때문에,
트리의 가장 아래쪽에 있는 값이 3인 노드로는 mnode가 내려가지 않습니다.
그리고 현재 mnode의 왼쪽자식노드가 NULL이기 때문에, while문은 종료되고 2단계로 넘어가게 됩니다.
2단계.대체할 노드에 저장된 값을 삭제할 노드에 대입한다
SetData (dNode, GetData(mnode));이 결과 mNode가 가리키는 값인 2가 dNode에 대입되어, 이제 dNode의 값은 2로 변경되었습니다.
dnode가 mNode로 바뀐 것과 마친가지이기 때문에, 이제 다음단계에서 해야 할 일은
기존의 mnode의 자리에 mnode의 자식노드를 넣어주는 작업이 필요하게 됩니다.
3단계. 대체할 노드의 부모 노드와 자식 노드를 연결한다. ★★★
if(GetLeftSubTree(mpNode) == mNode){
ChangeLeftSubTree(mpNode, GetRightsubTree(mNode));
}
else
{
ChangeRightSubTree(mpNode, GetRightSubTree(mNode))
}이 3단계를 이해하기 위해서 if의 조건문인
GetLeftSubTree(mpNode) == mNode을 참, 거짓 2가지 경우로 나누어 자세히 생각해보겠습니다.
먼저 제가 예시로 들었던 이진트리의 경우
mpnode의 왼쪽자식노드가 mnode이므로 조건문은 참을 만족하게 됩니다.
이런 경우 3단계에서는, 남아 있던 mnode의 자식노드(위치는 mnode의 오른쪽에 있습니다)를
mnode가 있던 자리에 넣어줘야 할 것입니다.
이 설명으로 그림으로 표현하면 아래와 같습니다.
위 그림에서는 값이 3인 노드를 mpnode의 왼쪽자식노드로 만들어주면 되기 때문에,
ChangeLeftSubTree(mpNode, GetRightsubTree(mNode);라는 함수를 이용하게 되는 것이죠.
그러면 if문이 만족하지 않는, GetLeftSubTree(mpNode) != mNode인 경우는 어떤 경우일까요?
책에는 나오지 않았지만, 바로 아래와 같은 경우의 이진트리라고 할 수 있습니다.
위와 같은 이진트리에서 dnode를 제거할 경우,
dnode의 오른쪽 서브트리에서 제일 작은 값인 9가 dnode를 대체해야 할 것입니다.
어떤 결과가 나오는지, 역시 1~3단계로 나누어 간단하게 생각해보도록 하겠습니다.
단계1.
이런 형태의 이진트리의 경우, mpnode와 mnode가 선언된 상태에서
이미 mnode의 왼쪽 자식노드가 NULL이기 때문에, while문이 실행되지 않고 지나가게 되죠.
단계2.
dnode의 값에는 mnode의 값, 즉 9가 대입될 것입니다.
단계3.
이 단계에서 일어나야 할 일은, mpnode가 mnode를 건너뛰고 mnode의 오른쪽자식노드와 연결되는 일이죠.
또는 mnode의 자리에 mnode의 오른쪽 자식노드를 넣어준다고 생각해도 됩니다.
이것을 그림으로 표현하면 다음과 같습니다.
위의 그림과 같은 경우가 바로 GetLeftSubTree(mpNode) != mNode를 만족시키는 경우이며,
if문에서는 아래의 함수를 통해 마지막단계가 구현됩니다.
{
ChangeRightSubTree(mpNode, GetRightSubTree(mNode))
}그 결과 다음과 같은 이진트리가 만들어지게 됩니다.
이상 설명을 마치도록 하겠습니다.