트리 (구성 요소, 이진 트리, 세그먼트 트리, 인덱스 트리, 최소공통 조상 LCA)

➊ 특징

• 노드와 에지로 연결된 그래프의 특수한 형태
• 그래프의 표현으로도 트리를 표현할 수 있음
• 순환구조 X, 1개의 루트노드
• 루트노드를 제외한 노드는 1개의 부모노드를 가짐
• 트리의 부분 트리 역시 토리의 모든 특징을 따름

그래프의 표현 및 비교 (간선 리스트, 인접 행렬, 인접 리스트)

 

 

➋ 트리의 구성요소

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

 

➌ 코딩테스트에서 트리

1. 그래프로 푸는 트리 ➜ 노드, 에지
   • 인접리스트로 표현
   • DFS, BFS
2. 트리만을 위한 문제
   • 1차원 배열로 표현
   • 이진트리
   • 세그먼트 트리(index트리)
   • LCA(최소공통조상)

 

➍ 이진트리

• 각 노드의 자식 노드(차수)의 개수가 2이하로 구성돼 있는 트리
• 편향 이진 트리, 포화 이진 트리, 완전 이진 트리
• 리스트로 표현
• 🌟 인덱스 연산 방식 :  세그먼트 트리, LCA 알고리즘

 

 

이동 목표 노드	인덱스 연산	제약조건(N=노드갯수)
루트 노드	index = 1
부모 노드	index = index / 2	현재 노드가 루트 노드가 아님
왼쪽 자식 노드	index = index ∗ 2	index ∗ 2 ≤ N
오른쪽 자식 노드	index =index ∗ 2 + 1	index ∗ 2 + 1 ≤ N

 

➎ 세그먼트 트리

세그먼트 트리, 인덱스 트리, 구간합

➏ 최소 공통 조상

[11437] 최소 공통 조상 (트리, LCA)

최소 공통 조상 빠르게 구하기 (트리, 제곱수 LCA, LCA 시간초과)