트리(Tree) | 트리, 트라이, 이진트리 비교

코딩테스트에서의 Tree 문제 분류

1) 그래프로 푸는 Tree

• 트리도 특수한 그래프 형태의 하나이기 때문에 노드, 간선 정보가 주어질 수 있다.
• 이 경우, 인접리스트 형태로 트리를 표현하고, 그에 맞는 그래프 처리 (ex. DFS/BFS) 풀이

2) Tree 만을 위한 문제

• 보통 1차원 배열로 트리를 표현한다.
• 이진트리, 세그먼트 트리, LCA(최소 공통 조상)

---

1. 트리 (Tree)

(1) 트리 Tree : 노드-에지로 연결된 그래프의 특수한 형태

(2) 특징

• 사이클 X, 루트 노드 1개
• 루트노드 제외한 모든 노드들은 단 1개의 부모 노드만 갖는다.
• 트리의 부분 트리(=서브트리) 역시 같은 특징을 따른다.

(3) 트리의 구성 요소

트리 구성요소

---

2. 트라이 (Trie)

(1) 트라이 (Trie) ; 문자열 검색 빠르게 실행 가능하도록 설계한 트리 형태의 자료구조

• 일반적으로 단어들을 사전 형태로 생성한 후, 트리의 부모 자식 관계 이용하여 ‘검색 수행’

(2) 트라이 특징

• N진 트리 : 문자 종류에 따라 N이 결정됨 (ex. 알파벳 26개 문자 구성 → 26진트리)
• 루트 노드는 항상 공백 상태 유지

---

3. 이진 트리 (Binary Tree)

(1) 이진 트리 : 각 노드의 최대 차수 (자식노드 개수) 2 이하로 구성된 트리

(2) 이진 트리 종류

• 편향 이진 트리 : 노드들이 한쪽으로 편향돼 생성된 이진 트리
• 포화 이진 트리 : 단말 노드 꽉찬 이진 트리
• 완전 이진 트리 : 단말 노드가 덜 꽉 찬 이진 트리 (마지막 레벨 단말노드는 왼쪽부터 채워짐)

이진트리 종류

→ 일반적으로 완전 이진 트리 형태가 多

(3) 이진 트리의 순차표현 : 1차원 배열로 표현

🎈[배열의 인덱스 연산] 현재 idx기준으로 대상 노드 위치 idx 찾기

1차원 배열로 트리를 표현

1) 루트 노드 찾기

target = idx = 1​

2) 부모 노드 찾기

//단, 현재 노드가 루트 노드 아닌 경우만 부모 노드 찾을 수 있음
target = idx / 2​

3) 왼쪽 자식 노드 찾기

if(idx*2 <= N) {
     //전체 노드 개수 N 범위 벗어나지 않는 한도 내에서
	target = idx * 2;
}​

4) 오른쪽 자식 노드 찾기

if(idx*2 + 1 <= N) {   
      //전체 노드 개수 N 범위 벗어나지 않는 한도 내에서
      target = idx * 2 + 1;
}​

(4) 이진 트리의 연결 리스트 표현

• 각 노드를 3개의 필드 left, data, right(왼쪽 자식, 본인, 오른쪽 자식 ) 형태로 구성

이진트리를 연결 리스트로 표현 시 모습

---

💡 이진트리 (Binary Tree) vs 이진탐색 트리(Binary Search Tree) 차이점

1) 이진트리 : 노드의 최대 차수가 2 인 트리 의미

2) 이진탐색트리

• 이진트리
• 각 노드에 중복되지 않은 키 (key) 존재
• 루트 노드 왼쪽의 서브트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 구성
• 루트 노드 오른쪽의 서브트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 구성
• 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.

💡 이진탐색 트리의 탐색

타겟 값 탐색 목적

1. 루트 노드 키와 찾고자 하는 값 비교 (발견 시 탐색 종료)
2. 찾고자 하는 값이 루트 노드 키보다 작다면 왼쪽 서브트리로 탐색 진행
3. 찾고자 하는 값이 루트 노드 키보다 크다면 오른쪽 서브트리로 탐색 진행