이진 탐색 트리 - 제거 구현 질문드립니다. - 인프런

그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)

이진 탐색 트리 - 제거 구현

이진 탐색 트리 - 제거 구현 질문드립니다.

해결된 질문

작성

285

자식 노드가 모두 존재하는 경우에 제거하는 경우의 수 중에서

제일 마지막 fakeParentRootNode 를 처리하는 부분에서 질문이 있습니다.

제거를 할 때 값을 변경하는 방식으로 진행하다보니 루트노드가 제거가 된다고 하더라도 fakeParentRootNode의 오른쪽 자식노드는 계속해서 root 노드의 주소값을 바라보고 있을 것이고, 변경사항이 없을텐데 해당 코드를 넣는 이유가 있을까요?

if (fakeParentRootNode.getRightSubTree() !== this.root) {
   this.root = fakeParentRootNode.getRightSubTree();
}

알고리즘

답변 1

감자

지식공유자

루트노드가 18, 왼쪽 자식노드가 15 하나 있는 트리로 가정해보겠습니다.

만약 루트노드(18)를 삭제하는 경우 else if문(자식 노드가 1개 있는 조건문)이 실행됩니다.
이 조건문에서는 아래 코드와 같이 자식 노드를 값이 아닌 주소를 바꿉니다.

        }else if(deletingNode.getLeftSubTree() == null || deletingNode.getRightSubTree() == null){
            let deletingNodeChild;

            if(deletingNode.getLeftSubTree() != null){
                deletingNodeChild = deletingNode.getLeftSubTree();
            }else{
                deletingNodeChild = deletingNode.getRightSubTree();
            }

            if(parentNode.getLeftSubTree() == deletingNode){
                parentNode.setLeftSubTree(deletingNodeChild); 
            }else{
                parentNode.setRightSubTree(deletingNodeChild); // fakeParentRootNode의 오른쪽 자식노드가 15인 노드가 됨.
            }

따라서 해당 케이스에 바뀐 루트노드를 다시 설정하는 것입니다.

궁금증이 해결되셨나요? 😀

황유정

질문자

감사합니다! 해결되었습니다.

인프런 커뮤니티 질문&답변

이진 탐색 트리 - 제거 구현 질문드립니다.