해당 글에서는 자료구조에서 비 선형 구조에 대해 이해하며, 그 종류인 일반트리/이진트리에 대해서 알아봅니다.
💡 [참고] 자료구조의 전체 구조
- 해당 글에서는 자료구조 중 비선형 구조에 대해 알아봅니다.
1) 비선형 구조(Non Linear)
💡 비 선형구조(Non Linear) - 데이터를 저장하기 위한 방법으로 데이터 간의 관계를 이루면서 ‘계층적인 구조‘를 가지며 ‘일렬로 나열되지 않은 자료구조’ 형태를 의미합니다.
- 일련 되지 않은 자료구조는 계층적으로 데이터의 관계가 부모-자식 관계, 연결 관계, 또는 소속 관계 등을 가지고 있어서 계층적이거나 상호 연결되어 있습니다. - 대표적인 비선형 구조는 트리(Tree), 그래프(Graph)등이 이에 해당합니다.
[ 더 알아보기 ] 💡 계층적인 구조?
- 데이터 요소들이 상위와 하위 간의 관계를 가지며, 부모와 자식으로 구성되는 구조를 의미합니다. 이러한 구조에서는 상위 요소가 하위 요소를 포함하고 있으며, 하위 요소는 상위 요소에 속하는 관계를 가지고 있습니다 - 계층적 구조에서는 각 요소들이 단계적으로 조직되어 있고, 상위 요소에 의해 하위 요소들이 제어될 수 있습니다.
💡 선형 구조?
- 선형구조는 데이터를 저장하기 위한 가장 기본적인 형태로 데이터 구조간의 관계가 계층적인 구조를 가지며 ‘데이터를 일렬로 나열한 형태’를 의미합니다. - 선형구조에는 선형 리스트, 연결 리스트, 큐(Queue), 스택(Stack), 덱(deque)이 있습니다.
💡 트리(Tree)란? - 비선형 구조 중 하나로 데이터를 ‘계층적으로 구조화하여 저장하는 자료구조’입니다.
- 데이터는 노드(Node)라는 구성요소로 구성되며, 하나의 루트 노드에서 시작하여 여러 개의 자식 노드로 분기되는 구조를 가지고 있습니다. - 일반트리의 경우 자식 노드를 0개 혹은 다수의 하위 노드를 가질 수 있습니다. 그러나 이진트리의 경우 자식 노드를 최대 2개까지만 가질 수 있다는 차이점이 있습니다.
노드(정점)와 노드를 연결하는 선을 의미합니다. 트리에서 edge(간선)는 부모 노드와 자식 노드를 연결하는 선을 의미합니다.
2. 노드의 깊이와 높이
💡 노드의 깊이와 높이
- 하나의 노드에는 루트노드와 부모와 자식 노드가 존재하는데 이와의 관계에 대해 노드의 깊이와 높이가 존재합니다.
종류
설명
외부 노드, 단말 노드(External Node)
- 외부노드는 자식 노드가 없는 노드를 의미합니다.
내부 노드, 가지 노드(Internal Node)
- 비 단말노드는 자식 노드가 있는 노드를 의미합니다
간선(Edge)
- 노드(정점)와 노드를 연결하는 선을 의미합니다. 트리에서 edge(간선)는 부모 노드와 자식 노드를 연결하는 선을 의미합니다.
노드의 깊이(Depth)
- 루트 노드(Root Node)에서 해당 노드까지 경로 상에 있는 간선(Edge)의 개수입니다. - 다시 말해서, 루트 노드에서 해당 노드까지 몇 개의 간선을 지나야 하는지를 의미합니다.
노드의 높이(Height)
- 해당 노드에서 leaf 노드(끝 노드)까지 가장 긴 경로 상에 있는 간선의 개수를 의미합니다. - 다시 말해서, 해당 노드에서 가장 먼 leaf 노드까지 몇 개의 간선을 지나야 하는지를 의미합니다.
3) 트리(Tree) : 이진트리(Binary Tree)
💡 이진 트리(Binary Tree)란?
- 트리의 각 노드가 ‘최대 두 개의 자식 노드’를 갖는 트리 구조를 의미합니다.
- 이진트리는 데이터를 저장하는데 매우 효율적이며 검색 알고리즘과 정렬 알고리즘, 데이터 구조에 유용하게 사용이 됩니다.
1. 이진 트리(Binary Tree)의 구조 및 특징
💡 이진 트리(Binary Tree)의 구조 및 특징 - 주요한 구조는 하나의 루트 노드와 최대 두 개의 자식 노드를 가지는 노드들로 이루어졌습니다. (최대 두 개의 노드는 자식 노드가 0 또는 1 또는 2개의 노드를 갖는 것을 의미합니다) - 각 노드는 키(key)와 값(value), 왼쪽 자식 노드(left child node), 오른쪽 자식 노드(right child node)를 가지고 있습니다.
💡 이진트리(Binary Tree) 주요 특징 1. 최대 자식 노드 개수 - 각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다.
2. 이진트리의 노드 값 - ‘왼쪽 자식노드’는 부모 노드보다 작은 값을 가지며 ‘오른쪽 자식노드’는 부모노드보다 큰 값을 가집니다.
3. 이진트리의 균형 - 균형 잡힌 트리이거나 불균형한 트리일 수도 있습니다.
4. 이진트리의 검색 - 이진트리를 이용하여 효율적인 검색이 가능합니다
5. 탐색 시간 - 높이에 따라 결정되며 높이가 낮을수록 빠른 검색이 가능합니다
6. 삽입, 삭제 - 균형을 유지하는 것이 중요합니다
[ 더 알아보기 ] 💡 균형트리
- 모든 노드의 서브 트리의 높이 차이가 한정된 트리를 의미합니다. 이는 트리의 균형을 유지하며, 검색 및 삽입 연산의 시간 복잡도를 일정하게 유지할 수 있게 합니다. 💡 불균형트리
- 한쪽으로 치우쳐진 트리 구조를 의미합니다. 이는 서브 트리의 높이 차이가 크게 나는 경우를 말하며, 검색 및 삽입 연산의 시간 복잡도가 불규칙하게 증가할 수 있습니다. - 불균형 트리의 예로는 단순 연결 리스트와 같이 한 방향으로만 노드가 연결된 구조가 있습니다.
2. 이진트리(Binary Tree)의 활용
💡 이진트리(Binary Tree)의 활용
- 이진트리는 대표적으로 검색과 정렬에서 효율적으로 사용됩니다. -특히 이진탐색트리(Binary Search Tree)는 이진트리 중에서도 특히 검색과 삽입, 삭제 연산이 빠른 구조로, 데이터베이스 쿼리나 검색 엔진에서 사용됩니다.
분류
활용 방안
검색 알고리즘
- 이진트리는 데이터를 “정렬된 상태”로 저장하기 때문에 데이터 검색 시간을 줄일 수 있습니다. - 이진트리 검색 알고리즘은 주어진 값을 찾을 때까지 반복적으로 노드를 탐색하는 방법을 사용합니다. - 이진트리 검색 알고리즘은 매우 빠르며, 데이터 검색에 아주 적합합니다.
정렬 알고리즘
- 이진탐색트리(BST)를 이용하면 데이터를 삽입하면서 자동으로 정렬이 되기 때문입니다. - 또한, 힙(Heap)은 특정 우선순위 큐를 구현할 때 사용되며, 우선순위 큐를 이용한 다익스트라 알고리즘 등에 활용됩니다.
이진 검색 트리
- 이진트리는 압축 알고리즘에서도 매우 유용합니다. 이진트리를 사용하여 데이터를 압축하면 중복되는 데이터를 제거할 수 있습니다. - 예를 들어, 문자열 "ABBCCCDDDDEEEEE"를 이진트리로 압축하면 "A(1)B(2)C(3)D(4)E(5)"와 같이 표현할 수 있습니다.
파일 시스템
- 파일 시스템에서는 이진트리를 사용하여 파일을 저장합니다. 이진트리를 이용하면 파일을 빠르게 검색할 수 있습니다. - 또한, 파일 시스템에서 이진트리를 사용하면 파일을 삽입하거나 삭제할 때 빠르게 처리할 수 있습니다.
게임 개발
- 게임에서는 이진트리를 사용하여 다양한 기능을 구현할 수 있습니다. - 예를 들어, 적을 탐색하거나, 아이템을 검색하거나, 스킬 트리를 구현하는 등의 기능에 이진트리를 사용할 수 있습니다.
데이터베이스
- 데이터베이스에서는 인덱싱을 위해 이진트리를 사용합니다. 이진탐색트리(BST)를 이용하면 데이터를 빠르게 검색할 수 있습니다. - 또한, B+트리(B+Tree)는 대용량 데이터베이스에서 많이 사용되는 인덱스 알고리즘입니다.
3. Java에서 이진트리(Binary Tree)를 활용하는 방법
💡 TreeSet 클래스를 사용하여 문자열을 정렬하는 코드는 다음과 같습니다.
- TreeSet 클래스를 사용하여 문자열을 정렬하고 출력합니다. - TreeSet 클래스는 중복된 값을 허용하지 않으므로, add() 메서드를 이용하여 여러 개의 문자열을 추가하고, for-each 문을 이용하여 문자열을 출력합니다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Set<String> set = new TreeSet<>();
set.add("apple");
set.add("banana");
set.add("cherry");
set.add("durian");
set.add("elderberry");
for (String s : set) {
System.out.println(s);
}
}
}
💡 TreeMap 클래스를 이용하여 key-value 쌍으로 데이터를 저장하는 코드는 다음과 같습니다.
- TreeMap 클래스는 이진탐색트리(BST)를 이용하여 key-value 쌍을 저장하므로, key 값에 대한 검색과 정렬에 매우 유용합니다. put() 메서드를 이용하여 key-value 쌍을 추가하고, keySet() 메서드를 이용하여 모든 key 값을 출력합니다
import java.util.*;
public class Main {
public static void main(String[] args) {
Map<String, Integer> map = new TreeMap<>();
map.put("apple", 100);
map.put("banana", 200);
map.put("cherry", 300);
map.put("durian", 400);
map.put("elderberry", 500);
for (String key : map.keySet()) {
System.out.println(key + " : " + map.get(key));
}
}
}
4) 트리(Tree) : 이진트리(Binary Tree) 종류
종류
설명
사용처
전 이진 트리 (Full Binary Tree)
트리의 모든 노드가 0개 또는 2개의 자식 노드를 가지는 이진 트리
암호화 알고리즘
포화 이진 트리 (Perfect Binary Tree)
트리의 모든 내부 노드가 2개의 자식을 가지며 모든 리프 노드가 같은 레벨에 있는 이진 트리
데이터 정렬, 우선순위 큐 및 트리기반 알고리즘
완전 이진 트리 (Complete Binary Tree)
트리의 모든 레벨이 완전히 채워져 있지는 않지만 마지막 레벨을 제외한 모든 레벨에서 왼쪽으로 차례대로 채워진 이진 트리
힙 구조
편향 이진 트리 (Skewed Binary Tree)
트리의 모든 노드가 한 쪽(왼쪽, 오른쪽)으로만 자식을 가지는 이진 트리
-
균형 트리 (Balanced Tree)
트리의 모든 내부 노드의 두 자식 서브 트리의 높이 차이가 1이하 인 이진 트리
검색이나 삽입 작업
이진 힙(Binary Heap)
트리의 각 노드가 자식 노드보다 작은 값을 가지는 최소 힙이거나 각 노드가 자식 노드보다 큰 값을 가지는 최대 힙 형태를 가지는 이진트리
우선순위 큐
2. 전 이진 트리 (Full Binary Tree)
💡 전 이진 트리 (Full Binary Tree) - 트리의 모든 노드가 0개 또는 2개의 자식노드를 가지는 이진트리를 의미합니다.
- 모든 내부 노드가 두 개의 자식을 가지거나 모두 리프 노드인 완전한 트리 구조를 가지게 됩니다. - 암호화 알고리즘에서 주로 사용이 됩니다.
💡 전 이진트리 (Full Binary Tree)의 주요 특징
1. 자식 노드의 개수는 0개 또는 2개 - 리프 노드를 제외한 모든 노드는 두 개의 자식 노드를 가지고 있습니다.
2. 모든 레벨이 꽉 차 있음 - 모든 레벨이 꽉 차 있으며, 리프 노드의 깊이가 같습니다.
3. 노드의 개수 - 노드의 개수가 2^n - 1개인 경우, 전 이진트리라고 할 수 있습니다. (n은 레벨 수)
[ 더 알아보기 ] 💡 리프노드 (Leaf Node) - 자식 노드가 없는 노드를 의미합니다.
3. 포화 이진트리(Perfect Binary Tree)
💡 포화 이진 트리(Perfect Binary Tree) - 트리의 모든 내부 노드가 2개의 자식을 가지며 모든 리프 노드가 같은 레벨에 있는 이진트리를 의미합니다.
- 이러한 트리는 노드의 개수가 정확히 2의 거듭제곱인 경우에만 만들어집니다. - 데이터 정렬, 우선순위 큐 및 트리 기반의 알고리즘에 주로 사용됩니다.
💡 포화 이진트리(Perfect Binary Tree)의 주요 특징 1. 포화 이진트리의 높이 - 모든 레벨이 꽉 차 있어야 하기 때문에 높이가 작아지고, 탐색 시간이 빨라집니다.
2. 효율적인 메모리 사용 - 모든 노드가 두 개의 자식 노드를 갖기 때문에 노드의 개수가 적어지고 메모리를 효율적으로 사용할 수 있습니다.
3. 삽입 삭제 시 트리 재구성 - 노드의 개수가 2의 거듭제곱이어야 하기 때문에, 삽입이나 삭제를 할 때 트리를 재구성해야 하는 경우가 생깁니다.
4. 힙(heap) 자료구조를 구현하는 데 사용 - 포화 이진트리는 힙(heap) 자료구조를 구현하는 데 사용됩니다. 힙은 최대값 또는 최소값을 빠르게 찾기 위해 사용되는 자료구조로, 이진트리의 형태를 띠는 특수한 종류의 트리입니다.
[ 더 알아보기 ] 💡 모든 레벨이 꽉 차있다는 무슨 말인가? - 모든 레벨에서 노드가 가득 차 있다는 것은 그 레벨에 포함될 수 있는 노드의 개수만큼 노드가 존재한다는 의미입니다. 예를 들어, 레벨 0에서는 1개의 노드, 레벨 1에서는 2개의 노드, 레벨 2에서는 4개의 노드가 있어야 합니다. 💡 트리의 레벨 - 루트 노드를 기준으로 레벨 0에서부터 시작하여 하위 노드를 이어갈 때의 높이를 의미합니다.
4. 완전 이진트리(Complete Binary Tree)
💡 완전 이진트리(Complete Binary Tree) - 트리의 모든 레벨이 완전히 채워져 있지는 않지만 마지막 레벨을 제외한 ‘모든 레벨에서 노드들이 왼쪽으로 차례대로 채워진 이진트리’를 의미합니다.
- 마지막 레벨에서는 노드들이 왼쪽부터 순서대로 채워지지만 그 외에는 모든 레벨에서 왼쪽부터 노드들이 채워집니다. - 배열을 사용하여 효율적으로 저장할 수 있는 특징이 있습니다. 또한, 이진 힙(Binary Heap)과 같은 자료구조에서 사용되기도 합니다.
💡 포화 이진트리(Perfect Binary Tree)의 주요 특징 1. 부모와 자식 노드 사이의 관계 - 노드 i의 왼쪽 자식 노드: 2i - 노드 i의 오른쪽 자식 노드: 2i+1 - 노드 i의 부모 노드: i/2 (단, i가 1일 경우 부모 노드는 없음) 2. 사용되는 자료구조 - 이진 탐색 트리(BST)나 힙(Heap) 등의 자료구조에서 사용됩니다.
3. 연산이 빠릅니다. - 완전 이진트리의 높이는 log2n 이하이기 때문에 검색, 삽입, 삭제 등의 연산이 빠르게 수행됩니다.
4. 삽입 삭제 시 구조가 깨짐 - 노드의 삽입과 삭제가 일어날 경우 트리의 구조가 깨질 수 있기 때문에 구현이 복잡하다는 단점이 있습니다.
5. 편향 이진트리(Skewed Binary Tree)
💡 편향 이진트리(Skewed Binary Tree) - 모든 노드가 한쪽(왼쪽 또는 오른쪽)으로만 자식을 가지는 이진트리입니다. - 이러한 특징으로 인해 트리의 한쪽 가지가 다른 가지보다 훨씬 길어지게 됩니다.
https://hsc-tech.tistory.com/7
6. 균형 트리 (Balanced Tree)
💡 균형 트리 (Balanced Tree) - 모든 서브트리의 높이 차이가 최대 하나인 이진 트리를 의미합니다.
- 이러한 특성으로 인해 균형 트리는 검색 연산의 시간 복잡도를 최적화할 수 있습니다. - 대표적인 균형 트리의 종류로는 AVL 트리, 레드-블랙 트리, B-트리 등이 있습니다. - 이러한 균형 트리들은 삽입, 삭제 연산이 발생할 때 트리의 균형을 유지하면서 효율적인 검색을 제공합니다.
💡 서브트리
- 트리에서 부모 노드와 그 노드의 자식들로 이루어진 하위 트리를 말합니다. 부모 노드를 기준으로 자식 노드들과 그들의 자손들로 구성된 트리 구조입니다.
💡 균형 트리 (Balanced Tree)의 주요 특징 1. 탐색시간 - 균형 트리는 높이가 낮아 탐색 시간이 빠릅니다. 2. 삽입, 삭제 연산 - 노드의 삽입, 삭제 연산 시 균형을 유지하기 위한 추가 연산(회전)이 필요합니다. - 자동으로 균형을 유지하기 때문에, 트리의 구조가 항상 일정합니다.
7. 이진 힙(Binary Heap)
💡 이진 힙(Binary Heap) - 각 노드가 자식 노드보다 작은 값을 가지는 최소 힙이거나 각 노드가 자식 노드보다 큰 값을 가지는 최대 힙입니다. - 이진 힙은 주로 우선순위 큐와 같은 자료 구조에서 사용됩니다. 이진 힙은 삽입, 삭제 등의 연산이 발생해도 트리의 균형을 유지하지 않습니다. 따라서 탐색 시간은 보장되지 않습니다.
https://www.geeksforgeeks.org/binary-heap/
[ 더 알아보기 ] 💡 최소 힙(Min Heap)
- 각 노드가 자식 노드보다 작은 값을 가지는 특징을 가지고 있습니다. - 이는 최소값을 빠르게 찾을 수 있는 자료 구조로 주로 사용됩니다. 최소 힙에서는 루트 노드가 항상 최소값을 가지며, 삽입과 삭제 연산을 통해 최소값을 유지합니다.
💡 최대 힙(Max Heap)
- 각 노드가 자식 노드보다 큰 값을 가지는 특징을 가지고 있습니다. - 최대 힙도 최소 힙과 마찬가지로 빠른 최대값 탐색에 사용됩니다. 최대 힙에서는 루트 노드가 항상 최대값을 가지며, 삽입과 삭제 연산을 통해 최대값을 유지합니다.
💡 이진 힙(Binary Heap)의 주요 특징
1. 각 노드가 자식 노드보다 작은 값을 가지는 최소 힙이거나, 각 노드가 자식 노드보다 큰 값을 가지는 최대 힙입니다. 2. 주로 우선순위 큐와 같은 자료 구조에서 사용됩니다. 3. 삽입, 삭제 등의 연산이 발생해도 트리의 균형을 유지하지 않습니다.
