파이썬 알고리즘 인터뷰 - 트리

트리

• 계층형 트리 구조를 시뮬레이션 하는 추상 자료형(ADT)으로 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드 집합
• 재귀로 정의된 자기 참조 자료구조(여러 개의 트리가 쌓아 올려져 큰 트리가 됨)

 

트리의 각 명칭

 

트리의 명칭

루트 : 자식 노드를 가지며, 간선으로 연결되어 있는 것

차수 : 자식 노드의 개수

높이 : 현재 위치에서부터 리프까지의 거리

깊이 : 루트에서부터 현재 노드까지의 거리 

 

 

 

그래프 vs 트리

 

트리는 순환 구조를 갖지 않지만 그래프는 순환 구조를 가지고 있다.

트리가 아닌 예시

(a) 같은 경우는 순환 구조를 가지고 있지 않기에 트리지만

(b) 같은 경우는 A-B-C-F 순환 구조를 가지고 있기에 그래프이다.

 

 

이진 트리

 

모든 차수가 2 이하 일때를 말한다. 왼쪽, 오른쪽 최대 2개의 자식을 갖는 매우 단순한 형태로 다른 트리에 비해 간결 하고 여러 가지 알고리즘을 구현하기 쉽다. 일반적으로 트리를 말할 떄 이진트리를 일컫는다.  다음 그림은 이진트리의 유형이다.

 

이진 트리의 유형

• 정 이진 트리(Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는다
• 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.
• 포화 이진 트리(Perfect Binary Tree) : 모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다.