13장 트리(Tree)[PYTHON]

이번 장에서는 트리가 무엇인지 알아보도록 하자.
트리는 그래프 개념을 이해한다면 그리 어렵지 않은 개념이다.
트리의 특징은 다음과 같다.

• 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다.
• 루트 노드를 제외한 노드는 1개의 부모 노드를 가진다.
• 트리의 부분 트리도 트리이다.

그림으로 이해하면 다음과 같다.

트리의 구성 요소에 대해 더 자세히 알아보자.

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

그래프와 가장 큰 차이점이라고 하면 순환이 안된다는 점이다.
트리 자료구조 자체와 관련된 이해를 물어 보는 문제도 출제된다고 하니 잘 숙지해두자.

참고자료
DO IT 알고리즘 코딩 테스트 파이썬 편 - 김종관