[Do it!_Algorithm with Python] 6.1 트리 기본

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python'

 

 

 

▪️트리의 특징

 

트리는 그래프의 형태 중 하나로, 다음과 같은 특징이 있다.

 

• 순환구조(cycle) 이 없고, 1개의 root node 가 존재한다
• root node를 제외한 노드는 단 1개의 부모 노드를 갖는다.
• subtree 또한 트리의 모든 특징을 따른다.
• 연결된 트리에서 임의의 두 노드를 이어주는 경로는 유일하다

 

Tree vs Graph

 

 

	그래프	트리
방향성	방향, 무방향	방향만 존재
사이클	순환, 비순환, 자기순환	비순환만 허용
루트 노드	루트 개념이 없다.	한개의 루트만 존재
부모-자식 관계	이런 개념이 없다	1개의 부모노드에여러개의 자식 노드 가능 단, 각 자식 노드는 하나의 부모노드만 가짐
모델	네트워크 모델	계층모델
간선 수	제한 없음	N-1개

 

 

▪️트리의 구성요소

구성요소	설명
노드	데이터의 index와 value를 표현하는 요소
엣지	노드와 노드의 연결관계를 나타내는 간선
루트 노드	트리에서 가장 상위에 존재하는 노드
부모 노드	두 노드 사이의 관계에서 상위노드에 해당
형제 노드	동일한 부모노드를 갖는 노드이다
자식 노드	두 노드 사이의 관계에서 하위노드에 해당
리프 노드	트리의 가장 하단에 존재하는 노드. 자식 노드가 없다!
중간 노드	root도 아니고, 리프 노드도 아닌 노드
차수 (Degree)	각 노드의 서브트리 개수
조상 (ancestor)	해당 노드에서 루트까지 가는 경로 상에 나타난 모든 노드들
자손 (descendant)	해당 노드에서 잎노드에 이르는 경로상에 나타난 모든 노드들
Level	루트의 level은 0이다. 자손 노드로 내려가면서 하나씩 증가한다
트리의 height (or depth)	트리에서 노드가 가질 수 있는 최대 level과 같다

 

 

 

▪️코딩 테스트에서의 tree 문제

 

1) 그래프로 푸는 tree

tree 또한 그래프의 특수한 형태이기때문에 인접리스트로 표현이 가능하다.

따라서 그래프 탐색 알고리즘에서 가장 많이 사용되는 DFS, BFS를 적용해서 푸는 tree문제가 있다.

이 경우, tree를 인접 리스트로 표현하고, 우리가 배운 DFS, BFS 알고리즘으로 풀면된다.

 

2) Tree 만을 위한 문제

이진 트리, segment (index) tree, LCA 와 같이 tree 구조에서만 나오는 알고리즘들이 있다.

이 경우 1차원 배열로 tree를 표현한다. 이와 관련한 내용은 이후 블로그에서 자세히 알아보도록 하자.