트리
계층적인 구조를 표현할 때 사용할 수 있는 비선형 자료구조
나무를 거꾸로 뒤집은 모습과 유사해 트리라 부르게 됨
트리의 용어
- 노드 : 데이터를 저장하는 기본 단위. 그래프의 정점
- 루트 노드(root node) : 부모가 없는 최상위 노드
- 단말 노드(leaf node) : 자식이 없는 노드
- 크기 : 트리에 포함된 모든 노드의 개수
- 깊이 : 루트 노드부터 단말 노드까지의 거리
- 높이 : 깊이 중 최댓값
- 차수 : 각 노드의 간선(자식) 개수
특징
- 하나의 루트 노드와 0개 이상의 하위 트리로 구성
- 데이터를 순차적으로 저장하지 않음 → 비선형 자료구조
- 트리 내에 또 다른 트리가 있는 재귀적 자료구조
- 사이클을 갖지 않고 연결된 무방향 그래프 구조
- 노드 간에 부모 자식 관계를 가지는 계층형 자료구조이며, 모든 자식노드는 하나의 부모 노도만 가짐
- 노드가
n개인 트리는 항상n-1개의 간선을 가짐
트리의 종류
편향 트리
- 모든 노드들이 자식을 하나만 가지는 트리
이진 트리
- 각 노드의 차수(자식 노드)가 2 이하인 트리
완전 이진 트리
- 트리의 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드는 왼쪽부터 순서대로 채워진 트리
이진 탐색 트리
- 이진 탐색이 동작할 수 있도록 고안된 순서화된 이진 트리
- 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
- 탐색, 삽입, 삭제 효율적
- 평균 시간복잡도
O(log n)/ 최악O(n)
힙
- 완전 이진 트리를 기반으로 하는 트리 자료구조
- 최소 힙 (Min-Heap) : 부모 노드 값이 자식 노드보다 작거나 같음
- 최대 힙 (Max-Heap) : 부모 노드 값이 자식 노드보다 크거나 같음
- 우선순위 큐 구현에 사용
- 시간복잡도 :
O(log n)
트리의 순회
트리에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법
대표적으로 전위 순회, 중위 순회, 후위 순회의 세 가지가 있다.
-
전위 순회 (Pre-order traverse)
현재 노드 출력 → 왼쪽 방문 → 오른쪽 방문
방문 순서 :A - B - D - E - C - F - G -
중위 순회 (In-order traverse)
왼쪽 서브트리 순회를 끝낸 후 오른쪽 서브트리 순회
왼쪽 방문 → 현재 노드 출력 → 오른쪽 방문
→ 이진 검색 트리를 중위순회 하면 순서대로 정렬이 가능
방문 순서 :D - B - E - A - F - C - G -
후위 순회 (Post-order traverse)
왼쪽 서브트리 순회를 끝낸 후 오른쪽 서브트리 순회
왼쪽 방문 → 오른쪽 방문 → 현재 노드 출력방문 순서 :
D - E - B - F - G - C - A
사용 사례
- 계층적 데이터 저장 ex) 파일, 폴더 등
- 효율적인 검색속도 O(1)
- 힙
- 데이터베이스 인덱싱 ex) B-Tree, B+Tree, AVL-Tree 등
트리 구현
그래프와 동일하게 인접리스트, 인접행렬로 구현 가능함
인접행렬 방식
2차원 배열으로 두 노드의 연결 여부를 저장함
- 부모-자식 관계
- 자식노드의 왼, 오른쪽 여부
의 두 가지 정보를 알 수 없음
인접리스트 방식
각 노드에 연결된 자식 노드들을 리스트로 관리
List<List<Integer>> list = new ArrayList<>();
// 각 정점의 자식 정점을 확인
list.get("부모").add("자식");
// 각 정점의 부모 정점을 확인
list.get("자식").add("부모");해시맵을 이용한 방식
각 정점의 부모는 한 개이므로, 부모 정점을 알아야 하는 경우 Map 활용 가능
- 각 노드의 Key-Value 쌍을 부모-자식 쌍으로 표현
Map<Integer, List<Integer>> tree = new HashMap<>();
// 0번 노드의 자식 1, 2 추가
tree. put(0, Arrays.asList(1,2));
// 자식 정점에 대해 부모 정보 저장
Map<Integer, Integer> tree = new HashMap<>();
tree.put(0,1); // 0번 노드의 부모는 1번
tree.put(1,2); // 1번 노드의 부모는 2번
노드 클래스 참조 방식
왼쪽, 오른쪽 자식의 구분을 위해 사용자 정의 객체를 만들어 구현
class Node{ // 노드 클래스
int nodeValue;
Node left;
Node right;
// 생성자
Node(int value){
this.value = value;
this.left = null;
this.right = null;
}
}
class BinaryTree { // 이진트리 클래스
Node root;
BinaryTree(int rootValue){
this.root = rootValue;
}
public void addNode(Node parent, int value, boolean isRight){
if(isRight{
parent.right = new Node(value);
}else{
parent.left = new Node(value);
}
}
}
public class Main {
public static void main(String[] args){
// 트리 생성
BinaryTree tree = new BinaryTree(1); // 루트노드 : 1
// 노드 추가
tree.add(tree.root, 2, false); // 루트의 왼쪽 자식 : 2
tree.add(tree.root, 3, true); // 루트의 오른쪽 자식 : 3
tree.add(tree.root.left, 4, true); // 2의 왼쪽 자식 : 4
}
}구현 방식 선택 기준
인접 행렬 : 간선 정보가 자주 필요할 때
인접 리스트 : 간선 정보가 적은 경우
노드 클래스 참조 : 이진 트리 (구조적 트리) 구현 시
배열 : 완전 이진 트리, 힙 구현 시
해시맵 : 동적 트리 표현 시
