[트리] Tree 개념 정리

트리 (Tree)

노드와 엣지로 연결된 그래프의 특수한 형태

→ 그래프의 표현으로도 Tree를 표현할 수 있다.

 

• 순환 구조(Cycle)을 지니지 않고, 1개의 루트 노드가 존재한다.
• 루트노드를 제외한 노드는 단 1개의 부모노드를 가진다.
• 트리의 부분트리(SubTree) 역시 트리의 모든 특징을 따른다.
• 연결된 트리에서 임의의 두 노드를 이어주는 경로는 유일하다.

Tree 구성요소
전체 트리	서브트리
ⓐ ← 루트 노드 (부모) 　　∧ ← 엣지 　ⓑ ⓒ  ←자식 노드 　∧ 　 ⓓ ⓔ	ⓑ ←부모 노드 　∧ 　 ⓓ ⓔ ←리프노드

 

구성요소	설명
노드	데이터의 index와 value를 표현하는 요소	] 그래프와 유사
엣지	노드와 노드의 연결 관계를 나타내는 선
루트노드	트리에서 가장 상위에 존재하는 노드		ⓐ
부모노드	두 노드 사이의 관계에서 상위 노드에 해당하는 노드		ⓑ, ⓓ 중 ⓑ
자식노드	두 노드 사이의 관계에서 하위 노드에 해당하는 노드		ⓑ, ⓓ 중 ⓓ
리프노드	트리에서 가장 하위 노드에 존재하는 노드 (자식노드가 없는 노드)		ⓓ, ⓔ
서브트리	전체 트리에 속한 작은 트리		ⓑ ∧ ⓓ ⓔ

 

---

코딩테스트 유형 Tip

 

① 그래프로 푸는 Tree

Tree는 Node와 Edge로 구성됨

1.  인접 리스트로 표현이 가능
2. 인접리스트 활용 DFS, BFS 적용한 Tree문제 (그래프 탐색 알고리즘)

② Tree만을 위한 문제

이진트리, 세그먼트(index)트리, LCA(최소공통조상)

세가지 유형중 세그먼트 트리와 LCA는 Trre문제 유형 중어려운 난이도이며
그중 세그먼트 트리 출제율이 높다.

세그먼트 트리는 드라마틱 하게 데이터를 관리한다.

자료구조로는 1차원 배열로 Tree를 표현한다.

인덱스	0	1	2	3	4	5	6	7
노드	X	A	B	C	D	E

( 0번 인덱스는 사용하지 않는다. )

 

• 부모 노드로 이동
  자신의 index / 2
  5/2 = 2 = E(5) → B(2)
  3/2 = 1 = C(3) → A(1)
  4/2 = 2 = D(4) → B(2)
• 자식 노드로 이동
  자신의 index * 2 혹은 index * 2 +1
  좌측노드: index * 2
  우측노드: index * 2 +1

1차원 배열로 표현도 가능하고, index 연산을 통해 부모, 자식으로 이동도 가능하다.
데이터 합 뿐만 아니라 데이터 수정에도 용의하다.

 

그래프로 푸는 인접 리스트를 활용한 DFS, BFS 탐색 유형과
Tree만을 위한 1차원 배열 유형이 있다.