C Data Structure - 이진 탐색 트리 3

C Data Structure - 이진 탐색 트리 2

지난 포스팅에서 순회까지 끝냈다. 이제 탐색과 삭제가 남았다.

바로 이어서 탐색을 보자.

이진 탐색 트리의 탐색

이진 탐색 트리에서 탐색과 순회는 다르다. 순회는 모든 노드를 방문하는 것을 이야기하지만, 탐색은 가장 효율적이고 적은 깊이로 노드를 방문하여 원하는 값을 찾는 것인가이다.

1번 : 찾으려고 하는 5 값이 루트 노드의 10 값보다 작으니, 왼쪽 서브 트리를 대상으로 하고 인덱스를 옮긴다.
2번 : 찾으려고 하는 5 값이 노드의 4 값보다 크니, 오른쪽 서브 트리를 대상으로 하고 인덱스를 옮긴다.
그 이후 발견.

위와 같이 서브 트리를 대상으로 옮기고, 또 서브 트리의 서브 트리로 대상을 옮기고 하는 과정에서 봤을 때, 재귀로 해결할 수 있다! 탐색 또한 마찬가지로 순회처럼 재귀를 이용하여 문제를 해결해갈 것이다.

코드를 보면 다음과 같다.

매개 변수인 sub_root에는 서브 트리의 루트 노드가 항상 들어온다. 이 서브 트리의 루트 노드와 값을 비교하여 같으면 탐색 완료, 작으면 다시 왼쪽 서브 트리 재탐색을 위한 재귀 호출, 크면 다시 오른쪽 서브 트리 재탐색을 위한 재귀 호출 순서로 조건 및 연산 수행을 진행하면 된다.

이진 탐색 트리의 삭제

아.. 삭제는 ㅋㅋ 여러 유형으로 나뉜다 쉽지가 않다. 왜냐하면? 자식이 없는 단말 노드를 삭제할 경우, 그냥 해당 단말 노드만 제거하면 끝나는 문제이지만 자식 노드가 존재하는 노드를 삭제할 경우 문제가 커진다. 

일단은 그림 형태로 유형 별로 확인한 뒤 코드를 보자.

삭제할 타겟이 단말(리프) 노드인 경우

간단하다. 그냥 끝에 있는 노드이므로 바로 삭제를 하면 되는데, 다만! 삭제할 타겟의 부모의 링크(left or right)가 NULL을 가리키도록 설정해주면 된다. 다음의 그림과 같이 말이다.

위에 해당하는 코드는 다음과 같다.

삭제할 타겟의 자식 노드가 하나만 존재하는 경우

이 경우 또한 간단하다. 아래의 그림과 같은 경우인데 삭제할 타겟의 부모의 링크와 삭제할 타겟이 가지고 있는 하나의 자식 노드를 연결해주면 된다.

위에 해당하는 코드는 다음과 같다.

삭제할 타겟의 자식 노드가 두 개 모두 존재하는 경우

이 경우는 좀 답이 없다. 물론 설명하기 답이 없다는 것이다. ㅋㅋ 좀만 생각해보면 쉽다! 

먼저, 이전의 노드 삭제 유형들처럼 타겟을 삭제하고 부모와 자식을 연결해주는 등의 간단한 방법으로 끝날 문제가 아니다.

삭제할 타겟 노드가 자식 노드를 두 마리나(?) 가지고 있는 바람에 왼쪽 자식 노드의 서브 트리와 오른쪽 자식 노드의 서브 트리를 만족할 수 있는 값으로 대체 노드 선별해야한다. 

아 그러면? 삭제할 타겟 노드의 자식들 중 하나로 선택하면 되는 것 아니냐?

응 안된다. 왜냐하면 그림에 자세히 설명을 해 놓았다. 아래의 그림에서 두 번째 케이스에 해당하는 경우다. 혼돈하지 말아야 한다.

그러면 자식 중에 아무나 하나를 그냥 올리면 안되면 어떻게 올려야 하나?

왼쪽 서브 트리에서 가장 큰 값을 갖는 노드를 대체 노드로 선별하거나,
오른쪽 서브 트리에서 가장 작은 값을 갖는 노드를 대체 노드로 선별해야한다.

두 경우 중 하나를 선택해야 한다. 그 선택은 뭐 개발자 마음이고, 코드 작성자 마음이다. 선택했다면 다음과 같은 순서를 떠올릴 수 있다.

1. 대체 노드의 링크들을 타겟 노드의 링크로 전부 동기화 한다.
2. 대체 노드의 부모의 링크를 적절한 포인터(노드 혹은 NULL)로 변경한다.
3. 타겟 노드를 제거한다.

이러한 순서를 떠올렸는데 여기서 약간의 꼼수(?)를 쓴다고 하며, 지혜를 발휘한다고 읽는다. 뭐냐하면, 대체 노드를 굳이 드러내어 타겟이 있던 자리로 옮겨서 링크를 수정할게 아니라, 타겟 노드의 값만 대체 노드의 값으로 바꿔준다면 링크들을 굳이 변경할 필요가 없기 때문이다. 

1번 연산이 굉장히 부담 그 자체이다. 헤깔려죽겠는데.. 2번과 3번은 어차피 대체 노드에 대해서 해야할 작업이기 때문에 그렇다 치더라도, 1번 연산은 안 해도 될 일을 하는 것과 다름이 없다! ㅋㅋ

그래서 뭐 어찌 되었든 간에 왼쪽/오른쪽 중에 선택을 했다면, 다음 그림으로 그 선택 이후의 과정을 설명한다. 번호 순서대로 색깔과 연관 지어서 차근 차근 읽으면 된다.

 

이에 따른 코드는 아래와 같으며, 타겟 노드를 루트 노드로 한 서브 트리의 오른쪽 자식의 서브 트리 군에서 가장 작은 값을 선택하여 타겟 노드의 자리에 대체하기로 하였다.

하.. 이로써 삭제까지 끝이다.

일요일에 정말 집중도 안되고, 포스팅을 하면 할수록 코드 작성 때는 떠 올리지도 않았던 세세한 부분까지 의구심이 들어서 시간이 두배, 세배 드는 것 같다.

뭐 다음 시간에는 코드와 실행 결과만 올린다.