[알고리즘] 트리 기본 개념

[알고리즘] 🌲 트리 기본 개념

트리

출처: https://pokemon.fandom.com/ko/wiki/%EA%BC%AC%EC%A7%80%EB%AA%A8_(%ED%8F%AC%EC%BC%93%EB%AA%AC)

 

트리(Tree)는 노드(Node)와 엣지(Edge)로 연결된 그래프의 특수한 형태 입니다.

 

특징

• 순환 구조가 아니고, 1개의 루트 노드가 존재
• 루트 노드를 제외한 노드는 1개의 부모 노드가 존재
• 트리에서 임의의 두 노드를 이어주는 경로는 유일함
• 트리의 부분 트리 역시 트리의 모든 특징을 따름

 

트리의 핵심 이론

트리의 구성 요소

 

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

 

코딩 테스트에서 트리🌲 유형

그래프로 푸는 Tree

• Node, Edge를 인접 리스트로 표현
• DFS, BFS 로 해결

 

예시

 

Tree 만을 위한 문제

• Binary Tree(이진 트리)
• Segment Tree(세그먼트 트리)
• index tree(인덱스 트리)
• Lowest Common Ancestor(LCA: 최소 공통 조상)

 

트리를 1차원 배열로 표현
Segment Tree(세그먼트 트리), index tree(인덱스 트리), Lowest Common Ancestor(LCA: 최소 공통 조상)는 1차원 배열로 표현이 가능합니다.

• 부모 노드를 이동할 때 index / 2
• 자식 노드로 이동할 때 index * 2

 

그림으로 설명하면 아래와 같습니다.

부모 노드 이동

 

 

 

 

 

자식 노드 이동