1일1공부/비선형자료구조
이진 탐색 트리 개념과 자바로 구현해보기
정진킴
2023. 9. 20. 09:32
1. 이진 탐색 트리 (Binary Search Tree)
- 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음
- 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼
- 각각의 서브 트리도 이진 탐색 트리를 유지
- 중복된 키를 허용하지 않음
2. 이진 탐색 트리의 특징
- 이진 탐색 트리 규칙에 의해 데이터가 정렬됨
- 이진 트리에 비해 탐색 필요 (균형 유지 필요)
3. 이진 탐색 트리 - 검색
- 찾고자 하는 데이터를 루트 노드부터 비교 시작
- 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동
- 찾는 데이터가 없으면 null 반환
- 어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어짐
4. 이진 탐색 트리 - 삽입
- Root 부터 비교 시작 (중복 키 발견 시 노드 추가하지 않고 종료)
- 삽입할 키가 현재 노드의 키보다 작으면 왼쪽으로 이동
- 삽입할 키가 현재 노드의 키보다 크면 오른쪽으로 이동
- Leaf 노드에 도달 후 키 비교하여 작으면 왼쪽, 크면 오른쪽에 삽입
5. 이진 탐색 트리 - 삭제(1)
- 삭제 대상 노드가 Leaf 노드인 경우
- 삭제 대상 노드 삭제
- 부모 노드의 해당 자식 링크 null 로 변경
6. 이진 탐색 트리 - 삭제(2)
- 삭제 대상 노드에 자식 노드가 하나 인 경우
- 자식 노드를 삭제 대상 노드의 부모 노드에 연결
- 삭제 대상 노드 삭제
7. 이진 탐색 트리 - 삭제(3)
- 삭제 대상 노드에 자식 노드가 둘인 경우
- 1. 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드 선택
- 2. 삭제 대상 노드의 오른쪽 서브 트리에서 가장 작은 노드 선택
- 1 또는 2 (둘 중 하나의 방법) 에서 선택한 노드를 삭제 대상 노드 위치로 올림
- 위로 올리는 과정에서 다른 자식 노드들의 링크 연결 작업 진행
- 삭제 대상 노드 삭제
import java.util.LinkedList;
import java.util.Queue;
class Node {
int key;
Node left;
Node right;
public Node(int key, Node left, Node right) {
this.key = key;
this.left = left;
this.right = right;
}
}
class BinarySearchTree {
Node head;
public BinarySearchTree(int key) {
this.head = new Node(key, null, null);
}
public void addNode(int key) {
if (this.head == null) {
this.head = new Node(key, null, null);
return;
}
Node cur = this.head;
while (true) {
Node pre = cur;
if (key < cur.key) {
cur = cur.left;
if (cur == null) {
pre.left = new Node(key, null, null);
break;
}
} else {
cur = cur.right;
if (cur == null) {
pre.right = new Node(key, null, null);
break;
}
}
}
}
public void removeNode(int key) {
Node parent = null;
Node successor = null;
Node predecessor = null;
Node child = null;
Node cur = this.head;
while (cur != null) {
if (key == cur.key) {
break;
}
parent = cur;
if (key < cur.key) {
cur = cur.left;
} else {
cur = cur.right;
}
}
if (cur == null) {
System.out.println("key에 해당하는 노드가 없습니다.");
return;
}
if (cur.left == null && cur.right == null) { // Leaf 노드인 경우
if (parent == null) {
this.head = null;
} else {
if (parent.left == cur) {
parent.left = null;
} else {
parent.right = null;
}
}
} else if (cur.left != null && cur.right == null || cur.left == null && cur.right != null) { // 자식노드가 하나인 경우
if (cur.left != null) {
child = cur.left;
} else {
child = cur.right;
}
if (parent == null) {
this.head = child;
} else {
if (parent.left == cur) {
parent.left = child;
} else {
parent.right = child;
}
}
} else { // 자식 노드가 둘인 경우
predecessor = cur;
successor = cur.left;
while (successor.right != null) {
predecessor = successor;
successor = successor.right;
}
predecessor.right = successor.left;
successor.left = cur.left;
successor.right = cur.right;
if (parent == null) {
this.head = successor;
} else {
if (parent.left == cur) {
parent.left = successor;
} else {
parent.right = successor;
}
}
}
}
public void levelOrder(Node node) {
Queue<Node> queue = new LinkedList<>();
queue.add(node);
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.print(cur.key + " ");
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree(20);
bst.addNode(10);
bst.addNode(30);
bst.addNode(1);
bst.addNode(15);
bst.addNode(25);
bst.addNode(13);
bst.addNode(35);
bst.addNode(27);
bst.addNode(40);
bst.levelOrder(bst.head);
// 노드 삭제
bst.removeNode(40);
bst.levelOrder(bst.head);
bst.removeNode(25);
bst.levelOrder(bst.head);
bst.removeNode(20);
bst.levelOrder(bst.head);
}
}- 결과
// 노드 추가
20 10 30 1 15 25 35 13 27 40
// Leaf 노드 삭제
20 10 30 1 15 25 35 13 27
// 자식 노드가 하나인 경우
20 10 30 1 15 27 35 13
// 자식 노드가 2개인 경우
15 10 30 1 13 27 35
- 위 로직을 재귀함수로 간결하게 구현이 가능하다.
- 장점으로는 로직 구현량이 적으며 연산량도 적다.
import java.util.LinkedList;
import java.util.Queue;
class BinarySearchTree2 {
Node head;
public BinarySearchTree2(int key) {
this.head = new Node(key, null, null);
}
public Node addNodeRecursive(Node cur, int key) {
if (cur == null) {
return new Node(key, null, null);
}
if (key < cur.key) {
cur.left = addNodeRecursive(cur.left, key);
} else {
cur.right = addNodeRecursive(cur.right, key);
}
return cur;
}
public Node removeNodeRecursive(Node cur, int key) {
if (cur == null) {
return null;
}
if (key < cur.key) {
cur.left = removeNodeRecursive(cur.left, key);
} else if (key > cur.key) {
cur.right = removeNodeRecursive(cur.right, key);
} else {
if (cur.left == null) { // 자식노드가 하나이거나 없는 경우
return cur.right;
} else if (cur.right == null) { // 자식노드가 하나이거나 없는 경우
return cur.left;
} else { // 자식 노드가 2개 인 경우
Node predecessor = cur;
Node successor = cur.left;
while (successor.right != null) {
predecessor = successor;
successor = successor.right;
}
predecessor.right = successor.left;
cur.key = successor.key;
}
}
return cur;
}
public void levelOrder(Node node) {
Queue<Node> queue = new LinkedList<>();
queue.add(node);
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.print(cur.key + " ");
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
System.out.println();
}
}
public class Practice2 {
public static void main(String[] args) {
BinarySearchTree2 bst = new BinarySearchTree2(20);
bst.addNodeRecursive(bst.head, 10);
bst.addNodeRecursive(bst.head, 30);
bst.addNodeRecursive(bst.head, 1);
bst.addNodeRecursive(bst.head, 15);
bst.addNodeRecursive(bst.head, 25);
bst.addNodeRecursive(bst.head, 13);
bst.addNodeRecursive(bst.head, 35);
bst.addNodeRecursive(bst.head, 27);
bst.addNodeRecursive(bst.head, 40);
bst.levelOrder(bst.head);
// 노드 삭제
bst.removeNodeRecursive(bst.head, 40);
bst.levelOrder(bst.head);
bst.removeNodeRecursive(bst.head, 25);
bst.levelOrder(bst.head);
bst.removeNodeRecursive(bst.head, 20);
bst.levelOrder(bst.head);
}
}