🎁 트리(Tree)란 무엇인가요? (더보기)
🎁 이진 트리(Binary Tree)
각 노드는 최대 2개의 자식을 갖는 트리를 뜻한다.
각 노드는 자식이 없거나 1 or 2개만을 가지는데, 자식 노드는 좌우를 구분한다.
(1). 왼쪽 자식 : 부모 노드의 왼쪽 아래
(2). 오른쪽 자식 : 부모 노드의 오른쪽 아래
🎁 이진 트리 종류
1. 포화 이진트리(Perfect binary Tree)
- 모든 레벨에서 노드들이 꽉 채워져 있는 트리
- 노드가 2개이며, 차수(Degree)가 2이다.
- 모든 노드가 가득 차 있기 때문에, 단말 노드부터 루트 노드까지의 높이(Height)가 같다.
- 노드의 갯수는 n = 2^h - 1, h = 높이
- 포화 이진 트리의 높이가 h일 때, 노드의 수는 2의 h(+1) 제곱 -1개
- 포화 이진 트리의 노드가 N개 일 경우, 높이는 logN
2. 완전 이진 트리(Complete binary Tree) :
- 마지막 레벨을 제외하곤 노드들이 모두 채워져 있는 트리
- 완전 이진 트리의 개념은 힙(Heap)과 관련 있다.
- 노드의 갯수는 n = 2^h - 1, h = 높이
- 마지막 레벨은 왼쪽 부터 노드가 채워져 있어야 한다.
3. 편향 트리(Skeed binary Tree) :
- 사향트리(한쪽으로만 기울어진 트리)
- 각 높이에 1개의 노드만 있다.
- 노드의 개수 => h , n <=2^h - 1, h = 높이
4. 정 이진 트리(Full binary Tree) :
- 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
- 2 * height + 1 <= 노드의 개수 n <= 2^(height+1) - 1
5. 균형 이진 트리(Balanced binary Tree) :
- 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리
🎁 이진 트리 구현
1. 배열 : 레벨 트리 순회 순으로 배열에 구성
- 높이가 h인 포화 이진 트리의 노드 번호를 배열의 인덱스로 이용하여 1차원 배열로 표현
- 1차원 배열에서 인덱스를 계산을 간단히 하기 위해 인덱스 0번은 실제로 사용하지 않고, 인덱스 1번에 루트를 저장
2. 연결 리스트 : 값과 간선을 관리하기 위한 노드로 연결리스트 구성한다.
- 배열로 표현하는 것과 다르게 메모리 문제 및 삽입/삭제 연산의 비효율에 의해 연결 자료구조 방식을 사용한다
'Knowledge > 자료구조' 카테고리의 다른 글
| 순열과 순열의 코드 구현 [Java] (0) | 2023.09.14 |
|---|---|
| [자료구조] 트리(Tree)의 구조와 순회 (0) | 2023.08.19 |
| [Java/자료구조] 우선순위 큐(PriorityQueue) (0) | 2023.08.13 |
댓글