트리에 대해 정리한 게시글이다.
해당 게시글을 읽기 전 참고하면 좋을 것 같다.
트리(Tree) (Java)
트리(Tree)란? 트리 구조란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다. 용어 트리 구조를 보며 알아야 할 용어들이 몇 개 있다. 부모 노드(parent node) : 자기 자신(노드)과 연결된
hyeon-z.tistory.com
이진 탐색 트리(Binary Search Tree)란?
이진 + 탐색 + 트리
즉, 이분화된 탐색을 위한(혹은 특화된) 트리 자료구조이다.
이진 트리 (Binary Tree)
모든 노드의 최대 차수를 2로 제한한 트리.
각 노드는 자식 노드를 최대 2개까지 가질 수 있다.
탐색에 특화된 트리
❓위의 이진 트리의 각 노드가 갖고 있는 값이 규칙이 없다면 어떻게 될까?
최악의 경우, 특정 값을 찾기 위해서 모든 노드를 탐색해야 한다.
이를 방지하고자 이진 트리에 한 가지 규칙이 추가된다.
"부모 노드를 기준으로 왼쪽 자식 노드들은 부모 노드보다 값이 작으며, 오른쪽 자식 노드들은 부모 노드보다 값이 크다"
예를 들어 부모 노드 6을 보자.
4는 6보다 작으므로 왼쪽 자식 노드가 되었고, 7은 6보다 크므로 오른쪽 자식 노드가 되었다.
❓이 구조의 장점은 무엇일까?
특정 값을 탐색할 때 빠르다는 것이다.
현재 탐색 노드와 찾으려는 값의 대소 관계를 비교해서 작다면 왼쪽 노드를 탐색하고, 크다면 오른쪽 노드를 탐색하고, 같다면 해당 값을 찾게 된다.
코드 구현 및 설명
Node 클래스
static class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
}
}
Insertion (삽입)
public void insert(int data) {
root = insert(root, data);
}
private Node insert(Node root, int data) {
if (root == null) {
root = new Node(data);
return root;
}
// 새로 들어온 값이 루트보다 큰 경우(오른쪽에 삽입)
if (data > root.data) {
root.right = insert(root.right, data);
}
// 새로 들어온 값이 루트보다 작은 경우 (왼쪽에 삽입)
else {
root.left = insert(root.left, data);
}
return root;
}
Search (탐색)
public Node search(int data) {
return search(rootNode, data);
}
private Node search(Node root, int key) {
if (root == null) {
return null;
}
if (root.data == key) {
return root;
}
if (key < root.data) {
return search(root.left, key);
}
return search(root.right, key);
}
Deletion (삭제)
노드를 삭제할 때 총 3가지 경우가 존재한다.
1. 자식이 없는 노드를 삭제하는 경우
만약 노드 7을 삭제한다면, 해당 노드만 삭제하면 된다.
2. 자식이 1개 있는 노드를 삭제하는 경우
만약 노드 14를 삭제한다면, 14를 삭제한 후 해당 자리로 그의 자식인 13을 가져와야 한다.
3. 자식에 2개 있는 노드를 삭제하는 경우
❓ 만약 노드 8을 삭제한다면 어떻게 해야 할까?
노드 8의 오른쪽 노드를 해당 자리로 가져온다면, 노드 10의 자식이 2개일 경우 루트 노드의 자식이 총 3개가 되어 이진 트리의 조건에서 벗어나게 된다.
<해결 방법>
1. 삭제된 노드의 오른쪽 자식 노드에서 제일 작은 노드로 대체한다.
2. 삭제된 노드의 왼쪽 자식 노드에서 제일 큰 노드로 대체한다.
조금 더 자세히 설명해 보면,
오른쪽 트리에서 루트 노드인 18과 가장 가까운 두 노드는 무엇일까?
18의 왼쪽 자식에서 가장 오른쪽에 있는 노드, 18의 오른쪽 자식에서 가장 왼쪽에 있는 노드일 것이다.
두 가지 해결 방법 중 1번을 선택하여 삭제를 구현하겠다.
'삭제하는 노드의 오른쪽 자식 노드에서 가장 작은 노드' 즉 10을 가져온 후, 해당 자리로 옮긴다.
✅한번 더 정리
[삭제하는 노드의 자식 노드가 없는 경우]
해당 노드 삭제
[삭제하는 노드가 왼쪽 또는 오른쪽 자식 노드, 즉 1개의 자식 노드를 갖고 있을 때]
이 경우 자식노드를 삭제노드의 위치로 옮긴다.
[삭제하는 노드가 왼쪽, 오른쪽 자식 노드 모두 갖고 있을 때]
'삭제하는 노드의 오른쪽 자식 노드에서 가장 작은 노드'를 갖고 온 뒤, 해당 노드를 삭제하고자 하는 노드로 옮긴다.
public void delete(int data) {
rootNode = delete(rootNode, data);
}
private Node delete(Node root, int data) {
if (root == null) {
return null;
}
// 삭제할 값이 루트보다 작은 경우 (왼쪽 서브트리 탐색)
if (data < root.data) {
root.left = delete(root.left, data);
}
// 삭제할 값이 루트보다 큰 경우(오른쪽 서브트리 탐색)
else if (data > root.data) {
root.right = delete(root.right, data);
}
// 삭제하려는 대상을 찾은 경우
else {
// 삭제할 노드: 자식 x
if (root.left == null && root.right == null) {
return null;
}
// 삭제할 노드: 자식 1 (오른쪽)
else if (root.left == null) {
return root.right;
}
// 삭제할 노드: 자식 1 (왼쪽)
else if (root.right == null) {
return root.left;
}
// 삭제할 노드: 자식 2
root.data = findMin(root.right);
root.right = delete(root.right, root.data);
}
return root;
}
// 삭제하는 노드의 오른쪽 자식 노드에서 가장 작은 노드 찾기
int findMin(Node root) {
int min = root.data;
while (root.left != null) {
min = root.left.data;
root = root.left;
}
return min;
}
중위 순회 출력
왼쪽 서브 트리->루트 노드->오른쪽 서브 트리순으로 출력하는 중위 순회로 출력
public void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
}
최종 코드
class BTree {
static class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
}
}
Node rootNode;
public Node search(int data) {
return search(rootNode, data);
}
private Node search(Node root, int key) {
if (root == null) {
return null;
}
if (root.data == key) {
return root;
}
if (key < root.data) {
return search(root.left, key);
}
return search(root.right, key);
}
public void insert(int data) {
rootNode = insert(rootNode, data);
}
private Node insert(Node root, int data) {
if (root == null) {
root = new Node(data);
return root;
}
// 새로 들어온 값이 루트보다 작은 경우 (왼쪽에 삽입)
if (data < root.data) {
root.left = insert(root.left, data);
}
// 새로 들어온 값이 루트보다 큰 경우(오른쪽에 삽입)
else {
root.right = insert(root.right, data);
}
return root;
}
public void delete(int data) {
rootNode = delete(rootNode, data);
}
private Node delete(Node root, int data) {
if (root == null) {
return null;
}
// 삭제할 값이 루트보다 작은 경우 (왼쪽 서브트리 탐색)
if (data < root.data) {
root.left = delete(root.left, data);
}
// 삭제할 값이 루트보다 큰 경우(오른쪽 서브트리 탐색)
else if (data > root.data) {
root.right = delete(root.right, data);
}
// 삭제하려는 대상을 찾은 경우
else {
// 삭제할 노드: 자식 x
if (root.left == null && root.right == null) {
return null;
}
// 삭제할 노드: 자식 1 (오른쪽)
else if (root.left == null) {
return root.right;
}
// 삭제할 노드: 자식 1 (왼쪽)
else if (root.right == null) {
return root.left;
}
// 삭제할 노드: 자식 2
root.data = findMin(root.right);
root.right = delete(root.right, root.data);
}
return root;
}
// 삭제하는 노드의 오른쪽 자식 노드에서 가장 작은 노드 찾기
int findMin(Node root) {
int min = root.data;
while (root.left != null) {
min = root.left.data;
root = root.left;
}
return min;
}
public void inorder() {
inorder(rootNode);
System.out.println("");
}
// 중위 순회 출력
public void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
}
}
class BSearchTree {
public static void main(String[] args) {
BTree tree = new BTree();
tree.insert(8);
tree.insert(3);
tree.insert(10);
tree.insert(1);
tree.insert(6);
tree.insert(4);
tree.insert(7);
tree.insert(14);
tree.insert(13);
tree.inorder(); // 1 3 4 6 7 8 10 13 14
tree.delete(8); // 1 3 4 6 7 10 13 14
tree.inorder();
if (tree.search(16) == null) {
System.out.println("탐색 실패"); // 탐색 실패
}
}
}
Reference
'☁️ Algorithm' 카테고리의 다른 글
| 최대공약수, 최소공배수 (feat. 유클리드 호제법) (0) | 2023.05.18 |
|---|---|
| 약수 알고리즘 (Java) (0) | 2023.05.17 |
| 트리(Tree) (Java) (0) | 2023.05.03 |
| 이진 탐색(Binary Search) (Java) (0) | 2023.05.03 |
| [알고리즘] 조합(Combination) (Java) (0) | 2023.03.21 |
댓글