해당 글에서는 자료구조에서 비 선형 구조에 대해 이해하며, 그 종류인 일반트리/이진트리에 대해서 알아봅니다.
💡 [참고] 자료구조의 전체 구조
- 해당 글에서는 자료구조 중 비선형 구조에 대해 알아봅니다.
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.*;
publicclassMain {
publicstaticvoidmain(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 값을 출력합니다
트리의 모든 내부 노드가 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. 삽입, 삭제 등의 연산이 발생해도 트리의 균형을 유지하지 않습니다.
