[트리] 트리

✔ 트리

트리란?

• 노드와 엣지로 연결된 그래프의 특수한 형태
• 그래프의 형태이므로 그래프의 표현으로도 트리를 표현할 수 있음
• 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재함
• 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가짐
• 트리에서 임의의 두 개의 노드를 연결하는 경로는 유일 
• 트리의 부분 트리 역시 트리의 모든 특징을 따름

트리의 구성 요소

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

코딩 테스트에서의 트리

• 그래프로 푸는 트리 문제
  • 노드와 엣지를 인접 리스트로 표현하고 DFS, BFS
• 트리만을 위한 문제
  • 1차원 배열로 표현하고 이진트리, 세그먼트 트리 (Index Tree), 최소공통조사 (LCA)

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn