-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
이진 탐색 트리 - 제거 구현 질문드립니다.
23.04.28 02:51 작성 조회수 221
1
자식 노드가 모두 존재하는 경우에 제거하는 경우의 수 중에서
제일 마지막 fakeParentRootNode 를 처리하는 부분에서 질문이 있습니다.
제거를 할 때 값을 변경하는 방식으로 진행하다보니 루트노드가 제거가 된다고 하더라도 fakeParentRootNode의 오른쪽 자식노드는 계속해서 root 노드의 주소값을 바라보고 있을 것이고, 변경사항이 없을텐데 해당 코드를 넣는 이유가 있을까요?
if (fakeParentRootNode.getRightSubTree() !== this.root) {
this.root = fakeParentRootNode.getRightSubTree();
}
답변을 작성해보세요.
1
감자
지식공유자2023.04.28
루트노드가 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인 노드가 됨.
}
따라서 해당 케이스에 바뀐 루트노드를 다시 설정하는 것입니다.
궁금증이 해결되셨나요? 😀
답변 1