트리란?
노드들이 연결된 비선형 자료구조. 루트 노드라 불리는 최상위 노드에서 시작해 여러 하위 노드로 확장되는 계측정 구조.
한 노드가 여러 노드와 연결돼 있다.
트리는 사이클이 존재하지 않는다. 즉, 탐색을 수행할 때 시작 노드와 종료 노드가 동일한 경로가 없다.
트리의 용어
- 노드(Node): 트리의 기본 단위
- 루트 노드(Root Node): 트리의 최상위 노드. 트리는 하나의 루트 노드를 가진다.
- 부모 노드(Parent Node): 자식 노드를 가지는 노드
- 자식 노드(Childe Node): 특정 노드의 하위 계층에 있는 노드
- 리프 노드(Leaf Node): 자식 노드를 가지지 않는 노드 즉, 최말단 노드
- 형제 노드(Sibling Node): 같은 부모 노드를 둔 노드들
- 레벨(Level): 지정된 노드에서 리프 노드까지 이어지는 경로의 길이. 여기에선 루트를 기준으로 하며, 서브 트리를 어떻게 구성하냐에 따라 노드의 레벨이 다르다.
- 차수(Degree): 노드가 가진 자식 노드의 개수 노드 B의 차수는 2이다.
이진 트리란
한 노드당 자식 노드를 최대 2개까지 가질 수 있는 노드. 3개 이상 가질 수 있다면 m-ary 트리라고 한다.
이진 트리의 종류
- 정 이진 트리(Full Binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 가지는 이진 트리
- 완전 이진 트리(Complete Binary Tree): 모든 레벨이 완전히 채워진 트리. 마지막 레벨은 왼쪽부터 순서대로 채워진다. 배열로 표현할 때 효율적이다.
- 포화 이진 트리(Perfect Binary Tree): 모든 부모 노드가 2개의 자식 노드를 가지고, 자식 노드들의 레벨이 동일한 트리 즉, 모든 레벨이 채워져있다.
- 치우친 이진 트리(Skewed Binary Tree): 모든 노드가 한 쪽에만 자식 노드를 가지는 트리 이를 해결하기 위해 AVL 트리같은 자료구조가 나왔다.
노드 정의
private static class Node {
int data;
Node left, right;
Node(int val) {
this.data = val;
}
public Node(int val, Node left, Node right) {
this.data = val;
this.left = left;
this.right = right;
}
}트리의 순회
트리의 삽입 삭제 과정을 거치기 위해선 트리를 탐색해야 한다.
전위(Pre-Order), 중위(In-Order), 후위(Post-Order), 레벨 (Level-Order) 4가지가 있다.
상황에 따라 어떤 순회 방식을 사용할지 결정된다.
중위 순회의 경우 이진 탐색 트리에서 삭제할 노드를 결정할 때 쓰인다.
시간 복잡도는 최소 O(log n), 최대 O(n) 이다.
private static void preOrder(Node node) {
if (node == null) {
return;
}
System.out.printf("%d ", node.data);
if (node.left != null) {
preOrder(node.left);
}
if (node.right != null) {
preOrder(node.right);
}
}
private static void inorder(Node node) {
if (node == null) {
return;
}
if (node.left != null) {
inorder(node.left);
}
System.out.printf("%d ", node.data);
if (node.right != null) {
inorder(node.right);
}
}
private static void postorder(Node node) {
if (node == null) {
return;
}
if (node.left != null) {
postorder(node.left);
}
if (node.right != null) {
postorder(node.right);
}
System.out.printf("%d ", node.data);
}
private static void levelOrder(Node node) {
if (node == null) {
return;
}
Queue<Node> q = new LinkedList<>();
q.add(node);
while (!q.isEmpty()) {
Node here = q.poll();
System.out.printf("%d ", here.data);
if (here.left != null) {
q.add(here.left);
}
if (here.right != null) {
q.add(here.right);
}
}
}트리의 삽입
이진 트리는 마지막 레벨을 왼쪽부터 삽입한다.
레벨을 N이라 할 때 각 레벨은 $2^N - 1$ 만큼의 노드를 가질 수 있다.
레벨 순회를 통해 삽입을 구현한 코드다.
시간 복잡도는 최소 O(log n), 최대 O(n) 이다.
private static void insert(int data) {
Node newNode = new Node(data);
if (root == null) {
root = newNode;
return;
}
Queue<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
Node here = q.poll();
if (here.left == null) {
here.left = newNode;
break;
} else if (here.right == null) {
here.right = newNode;
return;
}
else {
q.add(here.left);
q.add(here.right);
}
}
}트리의 삭제
이 부분에 대해선 다음 링크를 참고했다.
https://www.geeksforgeeks.org/deletion-binary-tree/
Deletion in a Binary Tree - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org
요약하면 삭제할 노드의 값을 가장 나중에 생성된 노드의 값으로 바꾼다.
시간 복잡도는 최소 O(log n), 최대 O(n) 이다.
private static void delete(int data) {
System.out.printf("%d 삭제\n", data);
Node deleteNode = null; // 값을 지울 노드
Node deepestNode = null; // 가장 나중에 생성된 노드
Node parentNode = null; // 가장 나중에 생성된 노드의 부모 노드, 루트는 이 값이 null
Queue<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
Node here = q.poll();
deepestNode = here;
if (here.data == data) {
deleteNode = here;
}
if (here.left != null) {
parentNode = here;
q.add(here.left);
}
if (here.right != null) {
parentNode = here;
q.add(here.right);
}
}
if (deleteNode != null) {
deleteNode.data = deepestNode.data;
if (parentNode != null) {
if(parentNode.left != null && parentNode.left.data == deepestNode.data) {
parentNode.left = null;
} else if (parentNode.right != null && parentNode.right.data == deepestNode.data) {
parentNode.right = null;
}
}
deepestNode = null;
}
System.out.println("----------------------------------");
}
전체 코드는 접어놨다.
더보기
import java.util.*;
public class BinaryTree {
private static class Node {
int data;
Node left, right;
Node(int val) {
this.data = val;
}
public Node(int val, Node left, Node right) {
this.data = val;
this.left = left;
this.right = right;
}
}
private static Node root;
public static void main(String[] args) {
System.out.println("1 ~ 9까지 삽입");
for (int i = 1; i < 10; i++) {
insert(i);
}
System.out.println("----------------------------------");
System.out.printf("전위 순회(preorder) : ");
preOrder(root);
System.out.printf("\n중위 순회(inorder) : ");
inorder(root);
System.out.printf("\n후위 순회(postorder) : ");
postorder(root);
System.out.printf("\n레벨 순회(postorder) : ");
levelOrder(root);
System.out.println();
print();
delete(5);
print();
}
private static void insert(int data) {
Node newNode = new Node(data);
if (root == null) {
root = newNode;
return;
}
Queue<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
Node here = q.poll();
if (here.left == null) {
here.left = newNode;
break;
} else if (here.right == null) {
here.right = newNode;
return;
}
else {
q.add(here.left);
q.add(here.right);
}
}
}
private static void delete(int data) {
System.out.printf("%d 삭제\n", data);
Node deleteNode = null; // 값을 지울 노드
Node deepestNode = null; // 가장 나중에 생성된 노드
Node parentNode = null; // 가장 나중에 생성된 노드의 부모 노드, 루트는 이 값이 null
Queue<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
Node here = q.poll();
deepestNode = here;
if (here.data == data) {
deleteNode = here;
}
if (here.left != null) {
parentNode = here;
q.add(here.left);
}
if (here.right != null) {
parentNode = here;
q.add(here.right);
}
}
if (deleteNode != null) {
deleteNode.data = deepestNode.data;
if (parentNode != null) {
if(parentNode.left != null && parentNode.left.data == deepestNode.data) {
parentNode.left = null;
} else if (parentNode.right != null && parentNode.right.data == deepestNode.data) {
parentNode.right = null;
}
}
deepestNode = null;
}
System.out.println("----------------------------------");
}
private static void print() {
System.out.println("출력");
Queue<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
int len = q.size();
for (int i = 0; i < len; i++) {
Node here = q.poll();
System.out.printf("%d ", here.data);
if (here.left != null) {
q.add(here.left);
}
if (here.right != null) {
q.add(here.right);
}
}
System.out.println();
}
System.out.println("----------------------------------");
}
private static void preOrder(Node node) {
if (node == null) {
return;
}
System.out.printf("%d ", node.data);
if (node.left != null) {
preOrder(node.left);
}
if (node.right != null) {
preOrder(node.right);
}
}
private static void inorder(Node node) {
if (node == null) {
return;
}
if (node.left != null) {
inorder(node.left);
}
System.out.printf("%d ", node.data);
if (node.right != null) {
inorder(node.right);
}
}
private static void postorder(Node node) {
if (node == null) {
return;
}
if (node.left != null) {
postorder(node.left);
}
if (node.right != null) {
postorder(node.right);
}
System.out.printf("%d ", node.data);
}
private static void levelOrder(Node node) {
if (node == null) {
return;
}
Queue<Node> q = new LinkedList<>();
q.add(node);
while (!q.isEmpty()) {
Node here = q.poll();
System.out.printf("%d ", here.data);
if (here.left != null) {
q.add(here.left);
}
if (here.right != null) {
q.add(here.right);
}
}
}
}https://github.com/brorica/DataStructure/blob/master/src/BinaryTree.java
GitHub - brorica/DataStructure: 수상할 정도로 나무를 좋아하는 레포
수상할 정도로 나무를 좋아하는 레포. Contribute to brorica/DataStructure development by creating an account on GitHub.
github.com
'알고리즘' 카테고리의 다른 글
| 레드 블랙 트리(red black tree) (0) | 2023.06.25 |
|---|---|
| 이진 힙(binary heap) (1) | 2023.06.14 |
| AVL 트리 (Adelson-Velsky and Landis Tree) (0) | 2023.06.11 |
| 이진 탐색 트리 (Binary Search Tree) (0) | 2023.06.10 |
| 2022 KAUPC 2회 출제 후기 (0) | 2022.09.18 |
