자바를 통해 이진 탐색 트리 구조에서 삭제 기능을 구현해보자.
* 과정이 많이 복잡하기 때문에 나눠서 이해하는 것이 좋다.
Leaf Node 삭제
- Leaf Node : Child Node 가 없는 Node
- 삭제할 Node 의 Parent Node 가 삭제할 Node 를 가리키지 않도록 한다.
Child Node 가 하나인 Node 삭제
- 삭제할 Node 의 Parent Node 가 삭제할 Node 의 Child Node 를 가리키도록 한다.
Child Node 가 두 개인 Node 삭제(택1) (중요)
* 삭제할 Node 의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node 의 Parent Node 가 가리키도록 한다.
* 삭제할 Node 의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node 의 Parent Node 가 가리키도록 한다.
- 위 의 두 가지 방법 중에서 오른쪽 자식 중 가장 작은 값을 가져오는 방법을 사용해보자.
1. 삭제할 Node 의 오른쪽 자식 선택
2. 오른쪽 자식의 가장 왼쪽에 있는 Node 선택
3. 해당 Node 를 삭제할 Node 의 Parent Node 의 왼쪽 Branch(또는 오른쪽 - 삭제할 Node 가 Parent Node 로부터 왼쪽 또는 오른쪽에 있는지에 다라 처리를 다르게 해줘야 한다.) 가 가리키게 함
4. 해당 Node 의 왼쪽 Branch 가 삭제할 Node 의 왼쪽 Child Node 를 가리키게 함
5. 해당 Node 의 오른쪽 Branch 가 삭제할 Node 의 오른쪽 Child Node 를 가리키게 함
6. 만약, 해당 Node 가 기존에 오른쪽 Child Node 를 가지고 있었을 경우 해당 Node 의 본래 Parent Node 의 왼쪽 Branch 가 해당 오른쪽 Child Node 를 가리키게 한다.
* 위에서 Child Node 가 2개인 Node 를 삭제하는 경우와 같이 굉장히 복잡한 과정을 풀어내야 하는 경우
풀이 과정을 여러갈래로 세분화 하여 하나씩 하나씩 문제를 해결해나간다.
* 이와 같은 풀이 방법 또는 알고리즘을 분할 정복(Divide and Conquer) 라고 한다.
* 각 경우 별로 삭제 메소드에서 코드를 어떻게 작성했는지 한번 살펴보자.
- 우선 특정 Node를 삭제하려면 해당 Node 가 존재하는지 부터 확인해야 한다.
public boolean delete(int value) {
// 노드가 있는지 부터 확인
boolean searched = false;
Node currentNode = this.head;
Node parent = this.head;
while (currentNode != null){
if(currentNode.getValue() == value) {
searched = true;
break;
}
else if(value < currentNode.getValue()) {
parent = currentNode;
currentNode = currentNode.getLeft();
}
else {
parent = currentNode;
currentNode = currentNode.getRight();
}
}
if(searched == false)
return false;
// 이하 코드 생략...
return true;
}- delete 메소드의 반환 타입을 boolean 으로 선언해준다.
- 현재 객체가 가지고 있는 트리의 헤드 객체 참조 값을 currentNode 와 parent 에 적재해준다.
- 반복문을 수행하며 노드를 찾기 시작한다.
- 현재 노드의 데이터 값이 메소드에 파라미터로 입력 받은 value 값과 같다면 현재 노드가 찾고자 했던 Node 라는 뜻 이기 때문에 searched 변수의 값을 true 로 설정해주고 반복문을 종료시킨다.
- 현재 노드의 데이터 값이 value 보다 클 경우 현재 노드의 위치를 왼쪽 노드로 옮겨주고 parent 객체를 현재 객체의 참조 값으로 변경해준다.
- 반대의 경우 현재 노드의 위치를 오른쪽 노드로 옮겨준다.
- 반복문이 끝난 이후 searched 의 값에 따라 조건문을 수행해준다.
* 위와 같은 코드를 통해 찾고자 하는 Node 를 찾았을 경우, 해당 노드의 유형에 따라 코드를 작성하여 삭제 기능을 구현한다.
- Leaf Node 를 삭제하는 경우
if(currentNode.getLeft() == null && currentNode.getRight() == null) {
if(value < parent.getValue()) // 부모 노드 보다 값이 작으면(부모 노드의 왼쪽에 있으면)
parent.setLeft(null);
else
parent.setRight(null);
}- 현재 노드의 왼쪽, 오른쪽 노드가 모두 존재하지 않는 경우 현재 노드가 Leaf Node 임으로 그에 맞는 코드를 작성해준다.
- 현재 노드의 부모 노드의 데이터 값과 입력받은 value 값을 비교하여 value 값이 작을 경우, 삭제하고자 하는 노드가 부모 노드 기준 왼쪽 Node 라는 뜻이므로 parent 객체의 왼쪽 노드 값을 null 로 세팅해 줌으로서 해당 노드를 삭제한다.
- 반대로 value 값이 크거나 같을 경우 삭제하고자 하는 노드가 부모 노드 기준 오른쪽 Node 라는 뜻이므로 parent 객체의 오른쪽 노드 값을 null 로 세팅해 줌으로서 해당 노드를 삭제한다.
- 삭제하고자 하는 Node가 Child Node 를 하나 가지고 있을 경우
// 해당 노드가 왼쪽 Child Node 를 가지고 있을 경우
if(currentNode.getLeft() != null && currentNode.getRight() == null) {
if(value < parent.getValue()) // 부모 노드의 왼쪽에 있을 경우
parent.setLeft(currentNode.getLeft());
else // 부모 노드의 오른쪽에 있을 경우
parent.setRight(currentNode.getLeft());
}
// 해당 노드가 오른쪽 Child Node 를 가지고 있을 경우
else if(currentNode.getLeft() == null && currentNode.getRight() != null) {
if(value < parent.getValue())
parent.setLeft(currentNode.getRight());
else
parent.setRight(currentNode.getRight());
}- 삭제하고자 하는 Node 가 가지고 있는 Child Node 가 왼쪽에 있는지 오른쪽에 있는지를 조건문을 통해 판별 해준 후 각각의 경우에 맞는 코드를 작성해준다.
- 왼쪽 Child Node 를 가지고 있을 경우 value 값과 부모 노드의 데이터값을 비교하여 왼쪽 Child Node 를 부모 노드의 왼쪽, 또는 오른쪽 노드로 연결해준다.
- 오른쪽 Child Node 를 가지고 있을 경우 value 값과 부모 노드의 데이터값을 비교하여 오른쪽 Child Node 를 부모 노드의 왼쪽, 또는 오른쪽 노드로 연결해준다.
- 삭제하고자 하는 Node 가 Child Node 를 두 개 가지고 있을 경우
// 삭제할 Node 가 두개의 노드를 가지고 있을 때
if(currentNode.getLeft() != null && currentNode.getRight() != null) {
Node changeNode = null;
Node changeNode_Parent = null;
// 삭제할 Node 가 부모 노드의 왼쪽에 있을 경우
if(value < parent.getValue()) {
changeNode = currentNode.getRight();
changeNode_Parent = currentNode.getRight();
// 삭제할 노드의 오른쪽에서부터 가장 작은 값을 찾는다.
while(changeNode.getLeft() != null) {
changeNode_Parent = changeNode;
changeNode = changeNode.getLeft();
}
// 가장 작은 노드가 오른쪽 노드를 가지고 있는 경우
if(changeNode.getRight() != null){
changeNode_Parent.setLeft(changeNode.getRight());
}
else // 오른쪽 노드를 가지고 있지 않은 경우
// 오른쪽에서 가장 작은 노드와, 그 부모 노드와의 연결을 끊어준다.
changeNode_Parent.setLeft(null);
// 오른쪽에서 가장 작은 값을 가진 노드를 삭제한 데이터의 위치로 올려준다.
parent.setLeft(changeNode);
// 삭제한 노드가 가지고 있는 자식 노드들의 정보를 적재해준다.
changeNode.setLeft(currentNode.getLeft());
// 오른쪽 노드에서 왼쪽으로 한번이라도 이동 했을 경우
// 즉, 가장 작은 값을 찾기 위해 왼쪽으로 한번이라도 이동 했을 경우
if(currentNode.getRight() == changeNode) {
changeNode.setRight(currentNode.getRight());
}
}
// 삭제할 노드가 부모 노드의 오른쪽에 있을 경우
else {
changeNode = currentNode.getRight();
changeNode_Parent = currentNode.getRight();
while(changeNode.getLeft() != null) {
changeNode_Parent = changeNode;
changeNode = changeNode.getLeft();
}
if(changeNode.getRight() != null) {
changeNode_Parent.setLeft(changeNode.getRight());
}
else
changeNode_Parent.setLeft(null);
parent.setRight(changeNode);
changeNode.setLeft(currentNode.getLeft());
// 오른쪽 노드에서 한번이라도 왼쪽으로 이동한 경우
if(currentNode.getRight() == changeNode) {
changeNode.setRight(currentNode.getRight());
}
}
currentNode = null; // gc 에 의해 자동으로 정리된다.
parent = null; // gc 에 의해 자동으로 정리된다.
}- 삭제할 Node 가 왼쪽,오른쪽 Child Node 를 전부 가지고 있을 때 조건문을 수행한다.
- 삭제할 Node 의 오른쪽에서 가장 작은 Node 객체를 담을 changeNode 와 해당 객체의 부모 객체를 담을 changeNode_Parent 를 선언해주고, 삭제할 노드가 부모 노드 기준 왼쪽에 있는지 오른쪽에 있는지와 상관없이 각 객체들에 현재 Node 의 오른쪽 Child Node 객체를 우선적으로 적재해준다.
- 반복문을 통해 삭제할 노드의 오른쪽 자식 Node 들 중에서 가장 작은 데이터값을 가지고 있는 노드와, 그 노드의 부모 노드 객체를 찾는다.
- 가장 작은 노드를 찾은 결과, 해당 노드가 오른쪽 자식 노드를 가지고 있는 경우, 오른쪽 Child Node 를 해당 노드의 부모 노드에게 왼쪽 노드로서 연결시켜 주고, 그렇지 않으면 부모 노드의 왼쪽 노드를 null 값으로 초기화 해준다.
- 삭제할 노드에서 부모 노드의 왼쪽, 또는 오른쪽 노드에(삭제할 노드가 부모 노드 기준 어느쪽 자식 노드인지에 따라 다르게 처리해준다.) 찾아온 오른쪽 노드 들 중에서 가장 작은 노드 객체를 연결해준다.
- 가장 작은 노드 객체의 왼쪽 Branch 에, 기존에 삭제할 노드가 가지고 있던 왼쪽 Child Node 객체를 연결해준다.
- 가장 작은 노드 객체의 오른쪽 Branch 의 경우, 삭제할 노드의 오른쪽에서 부터 한번이라도 왼쪽 노드로 이동했을 경우 기존에 삭제할 노드가 가지고 있던 오른쪽 Child Node 객체를 연결해준다.
- 만일 오른쪽에서 한번도 왼쪽으로 간 적이 없을 경우, 삭제할 노드의 오른쪽 자식 노드가 곧 오른쪽에서 가장 작은 값을 가진 노드였다는 의미이므로 가장 작은 노드의 오른쪽 Branch 연결에 대해선 아무 처리도 해주지 않고 가져온 그대로의 정보를 유지해준다.
왼쪽으로 한번이라도 갔는지 그렇지 않았는지를 따져야 하는 이유?
* 오른쪽에 있던 노드가 오른쪽에서 가장 작은 노드 였을 경우(한번도 왼쪽으로 이동하지 않음), 오른쪽 노드의 위치를 삭제한 노드의 위치로 옮겨주되 해당 노드의 오른쪽 자식 노드에 연결된 정보는 삭제된 노드의 오른쪽 노드 정보를 연결 시키지 않고 원본 그대로 유지시켜 줘야 한다.
왜냐하면 만약 삭제한 노드의 오른쪽 자식 노드 정보를 원래 삭제된 노드의 오른쪽 자식 노드였던 노드에게 연결시켜 줄 경우, 삭제한 노드의 위치로 옮겨온 오른쪽 자식 노드가 가리키고 있는 자신의 오른쪽 자식 노드에 대한 정보가 자기 자신이 되어 버리므로 반드시 문제가 발생하게 될 것이기 때문이다.
* 자바로 직접 구현한 이진 탐색 트리의 기능을 확인해볼 main 클래스는 다음과 같다.
- BST_main.java
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class BST_main {
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
bw.write("데이터를 입력하세요 : ");
bw.flush();
int data = Integer.parseInt(br.readLine());
BSTMgmt mgnt = new BSTMgmt(new Node(data));
bw.write("이진 탐색 트리의 루트 노드가 생성 완료되었습니다.\n");
bw.flush();
while(true) {
String option = "";
bw.write("메뉴를 선택하세요 \n");
bw.write("1. 트리 데이터 삽입\n");
bw.write("2. 트리 데이터 검색\n");
bw.write("3. 트리 데이터 삭제\n");
bw.write("4. 프로그램 종료\n");
bw.write("메뉴 선택 : ");
bw.flush();
option = br.readLine();
if(option.equals("4")) {
bw.write("\n프로그램이 종료 됩니다.\n");
bw.flush();
break;
}
else if(option.equals("1")) {
bw.write("\n삽입하고자 하는 데이터를 입력하세요(숫자) : ");
bw.flush();
mgnt.insert(Integer.parseInt(br.readLine()));
}
else if(option.equals("2")) {
bw.write("\n검색하고자 하는 데이터를 입력하세요(숫자) : ");
bw.flush();
mgnt.search(Integer.parseInt(br.readLine()));
}
else if(option.equals("3")) {
bw.write("\n삭제하고자 하는 데이터를 입력하세요(숫자.) : ");
bw.flush();
if(mgnt.delete(Integer.parseInt(br.readLine()))) {
bw.write("데이터가 정상적으로 삭제되었습니다.\n\n");
bw.flush();
}
else {
bw.write("해당 데이터가 존재하지 않습니다.\n\n");
bw.flush();
}
}
}
}
}
이진 탐색 트리의 시간 복잡도와 단점
- 이진 탐색 트리에서 가장 중요한 것은 저장된 데이터를 얼마나 빨리 찾느냐이다.
- 이진 탐색 트리의 depth(트리의 높이) 를 h 라고 표기한다면 O(h)가 된다.
- n 개의 노드를 가진다면 h = log2n 에 가까우므로 시간 복잡도는 O(log n) 이다.
- 빅오 표기법에서 log n 에서의 log 의 밑은 10 이 아니라 2 이다.
- 한번 실행 시 마다 50% 의 실행할 수도 있는 명령이 제거된다는 의미이다.
- 즉, 50% 의 실행 시간을 단축 시킬 수 있다는 것을 의미한다.
* 이진 검색 트리의 단점(최악의 경우)
이진 탐색 트리의 평균 시간 복잡도는 O(log n) 이지만, 이는 트리가 균형 잡혀 있는 때의 평균 시간 복잡도이며,
트리가 한쪽으로 치우쳐져 있을 경우(최악의 경우) 연결 리스트 등과 동일한 성능을 보여주게 된다.(O(n))
'자료구조 및 알고리즘 > 자료구조' 카테고리의 다른 글
| [자료구조] 자바 에서의 힙(Heap) #2 (0) | 2021.11.30 |
|---|---|
| [자료구조] 자바 에서의 힙(Heap) #1 (0) | 2021.11.30 |
| [자료구조] 자바 에서의 트리 #1 (0) | 2021.11.28 |
| [자료구조] 자바에서의 해쉬 테이블과 충돌 문제 해결 (0) | 2021.11.25 |
| [자료구조] - 자바로 연결 리스트를 구현해보자. #2 (0) | 2021.11.25 |
