이진 탐색 트리
이진 트리로 만들어진 탐색을 위한 자료구조로 4가지 조건을 가진다.
- 왼쪽 자식 노드의 키는 부모 노드의 키보다 작다.
- 오른쪽 자식 노드의 키는 부모 노드의 키보다 크다.
- 서브 트리들도 이진 탐색 트리를 유지한다.
- 중복된 키를 허용하지 않는다.
왼쪽 자식 노드 < 부모노드 < 오른쪽 자식 노드
탐색
- 찾고자 하는 데이터를 루트 노드부터 비교 시작
- 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동
- 찾는 데이터가 없으면 null 반환
- 어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어진다.
삽입
- 탐색과 마찬가지로 루트부터 비교 시작 (중복 키 발견 시 추가 없이 종료)
- 삽입키가 현재 노드의 키보다 작으면 왼쪽으로 이동
- 삽입키가 현재 노드의 키보다 크면 오른쪽으로 이동
- Leaf 노드에 도달 후 마지막으로 비교하고 삽입
삭제
1. 삭제 대상 노드가 Leaf 노드인 경우
- 삭제 후 부모 노드의 해당 자식 링크 null로 변경
2. 삭제할 노드에 자식 노드가 하나 있는 경우
- 삭제할 노드의 부모 노드에 자식 노드를 연결 후 삭제
3. 삭제 대상 노드에 자식 노드가 둘인 경우
두 가지 방법이 있다.
Successor
- 선택한 노드의 오른쪽 서브트리중 가장 작은 값을 가지는 노드를 의미한다.
- 즉, 삭제할 노드의 오른쪽 서브트리 -> 왼쪽 노드로 계속 이동(최소값)
- Successor를 삭제 대상 노드 위치로 옮긴다.
Predecessor
- 선택한 노드의 키보다 작으면서 가장 큰 값을 가지는 노드로 Successor의 반대이다.
- 삭제할 노드의 왼쪽 서브트리 -> 오른쪽 노드로 계속 이동(최대값)
- Predecessor을 삭제 대상 노드 위치로 옮긴다.
이진 탐색 트리 구현
import java.util.LinkedList;
import java.util.Queue;
// 노드 구성: key, 왼쪽 노드, 오른쪽 노드
class Node {
int key;
Node left;
Node right;
Node(int key, Node left, Node right) {
this.key = key;
this.left = left;
this.right = right;
}
}
// 이진 탐색 트리
class BinarySearchTree {
Node head;
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);
} else {
Node cur = this.head;
// 크기 비교해가며 왼 or 오른쪽에 삽입
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 prev = 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;
}
}
// 조건에 따라 다른 삭제 코드
// 트리에 key가 없는 경우
if (cur == null) {
System.out.println("key에 해당하는 노드 없음");
}
// 1. 삭제할 노드가 Leaf 노드인 경우
if (cur.left == null && cur.right == null) {
if (parent == null) {
this.head = null;
} else {
if (parent.left == cur) {
parent.left = null;
} else {
parent.right = null;
}
}
// 2. 삭제할 노드의 자식 노드가 하나인 경우
} 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;
}
}
// 3. 삭제할 노드의 자식 노드가 2개인 경우
} else {
prev = cur;
successor = cur.right; // 오른쪽 서브트리 이동
while (successor.left != null) {
prev = successor;
successor = successor.left;
}
prev.left = successor.right;
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(10);
bst.addNode(5);
bst.addNode(17);
bst.addNode(1);
bst.addNode(6);
bst.addNode(14);
bst.addNode(21);
bst.levelOrder(bst.head); // 10 5 17 1 6 14 21
// 노드 삭제(Successor 예제)
bst.removeNode(10);
bst.levelOrder(bst.head); // 14(root) 5 17 1 6 21
}
}