터미널 노드는 자식노드를 가지고 있지 않기 때문에 단순히 부모노드와 연결만 끊어주면 간단하게 제거된다.
2. 자식노드가 1개만 있는 노드 제거
15 노드 삭제
제거할 노드와 연결된 노드를 끊는다.
부모노드와 제거할 노드의 자식노드를 연결해준다.
3. 자식노드가 2개 있는 노드 제거
10 노드 삭제
제거할 노드의 위치에 와야될 노드는 이진 탐색 트리의 조건을 무너뜨리지 않는 노드가 와야한다.
제거하려는 노드가 10이라고 가정해보자.
10을 대신할 값을 구해서 10 위에 덮어써야한다.
10노드의 왼쪽 자식노드에서 제일 큰 값이나 오른쪽 자식노드에서 제일 작은 값을 구한다. 두 값 중 아무 값이나 10의 자리를 대신할 수 있다. (위 트리에선 8, 11)
4. 코드 구현
코드 60 라인부터 참고
public class Main {
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.insert(18);
tree.insert(15);
tree.insert(10);
tree.insert(6);
tree.insert(3);
tree.insert(8);
tree.insert(12);
tree.insert(11);
tree.insert(31);
tree.insert(27);
tree.insert(24);
tree.insert(20);
tree.insert(33);
tree.insert(35);
tree.insert(37);
tree.remove(10);
tree.root.inOrderTraversal(tree.root);
}
}
public class BinarySearchTree {
BinaryTree root = null;
// insert() 생략
public BinaryTree remove(int targetData) {
// 루트노드를 제거할 때 사용하기 위함
// 루트노드는 부모노드를 갖고 있지 않아서 다른 노드와 똑같은 방식으로 제거를 진행할 수 없다.
// 루드노트도 다른 노드들과 똑같은 방식으로 제거하기위해 임시로 fake 노드를 만들어둔 것.
BinaryTree fakeParentRootNode = new BinaryTree(0);
BinaryTree parentNode = fakeParentRootNode;
BinaryTree currentNode = this.root;
BinaryTree deletingNode = null;
// fake이므로 왼쪽에 넣든 오른쪽에 넣든 상관없음
fakeParentRootNode.setRightSubTree(currentNode);
while (currentNode != null && currentNode.getData() != targetData) {
parentNode = currentNode;
if (targetData < currentNode.getData()) {
currentNode = currentNode.getLeftSubTree();
} else {
currentNode = currentNode.getRightSubTree();
}
}
// 제거할 데이터를 찾은 경우 currentNode는 제거할 노드를 가리키고
// 제거할 데이터를 찾지 못한 경우 currentNode는 null을 가리킨다.
if (currentNode == null) {
return null;
}
deletingNode = currentNode;
// 제거할 노드에 자식노드가 없는지 확인
// 1. 터미널 노드를 제거하는 상황
if (deletingNode.getLeftSubTree() == null && deletingNode.getRightSubTree() == null) {
if (parentNode.getLeftSubTree() == deletingNode) {
parentNode.removeLeftSubTree();
} else {
parentNode.removeRightSubTree();
}
} else if (deletingNode.getLeftSubTree() == null || deletingNode.getRightSubTree() == null) {
// 2. 제거할 노드가 자식노드를 1개 가지고 있는 상황 -> 제거할 노드의 자식노드를 제거할 노드의 부모노드와 연결
BinaryTree deletingNodeChild;
if (deletingNode.getLeftSubTree() != null) {
deletingNodeChild = deletingNode.getLeftSubTree();
} else {
deletingNodeChild = deletingNode.getRightSubTree();
}
// 제거할 노드의 자식노드를 제거할 노드의 부모노드와 연결
if (parentNode.getLeftSubTree() == deletingNode) {
parentNode.setLeftSubTree(deletingNodeChild);
} else {
parentNode.setRightSubTree(deletingNodeChild);
}
} else {
// 3. 제거할 노드가 자식노드를 2개 가지고 있는 상황 (제거할 노드 = 10) - *그림참고
BinaryTree replacingNode = deletingNode.getLeftSubTree();
BinaryTree replacingParentNode = deletingNode;
// 왼쪽 서브트리에서 대체할 노드를 찾는다는 가정하에 가장 큰 값을 가지고 있는 노드(대체할 노드 = 8)를 찾아냄
while (replacingNode.getRightSubTree() != null) {
replacingParentNode = replacingNode;
replacingNode = replacingNode.getRightSubTree();
}
int deletingNodeData = deletingNode.getData(); // 10
deletingNode.setData(replacingNode.getData()); // 8 (노드를 제거하는 것이 아닌 data 값만 덮어쓰기)
// ex) 대체할노드(8)의 부모노드(6)에 기존의 대체할노드의 자식노드(7)를 연결
// 근데 왜 replacingNode.getLeftSubTree()를 연결해주는걸까?
// -> 제거할 노드의 왼쪽 서브트리에서 replacingNode가 가장 큰 값을 갖고 있는 걸 알고있다.
// -> 그러므로 replacingNode의 오른쪽 자식노드는 존재하지 않는다.
// ℹ오른쪽 자식노드가 존재하면 이진탐색트리 규칙 상, 그 노드의 값이 제일 클 것이다.
if (replacingParentNode.getLeftSubTree() == replacingNode) {
replacingParentNode.setLeftSubTree(replacingNode.getLeftSubTree()); // null ok
} else {
replacingParentNode.setRightSubTree(replacingNode.getLeftSubTree()); // null ok
}
deletingNode = replacingNode;
deletingNode.setData(deletingNodeData);
}
// 특수한 경우)
// 지금까지는 노드를 제거할 때, 그 노드가 부모노드를 갖고있다는 가정을 함
// 제거하려는 노드가 루트노드일 때는 부모노드가 없으므로 임시 부모노드인 fakeParentRootNode를 만들어 부모 역할을 시킴
// 만약 루트노드가 제거된 경우라면 변경된 루트노드를 이 트리의 루트노드로 다시 설정해줘야 한다.
if (fakeParentRootNode.getRightSubTree() != this.root) {
this.root = fakeParentRootNode.getRightSubTree();
}
return deletingNode;
}
}
