자료구조: 트리

트리

 

트리의 정의

 

 

계층형 트리 구조를 시뮬레이션 하는 추상 자료형(ADT)으로,
루트 값과 부모-자식 관게의 서브트리로 구성되며, 서로 연결된 노드의 집합

 

트리의 각 명칭

 

• 루트: 자식 노드를 가지며 간선으로 연결되어 있음
• 차수: 자식 노드의 개수
• 크기: 자신을 포함한 모든 자식 노드의 개수
• 높이: 현재 위치에서부터 리프까지의 거리
• 깊이: 루트에서부터 현재 노드까지의 거리

 

 

 

트리의 특징

 

• 트리는 재귀로 정의된 자기 참조 자료구조이다. -> 자식도 트리고 또 그 자식도 트리
• 레벨은 0에서부터 시작한다.
• 항상 단방향이기 때문에 간선의 화살표는 생략 가능하다.
• 방향은 보통 위에서 아래이다.

 

 

 

 

 

 

 

 

 

트리 vs 그래프

 

 

트리는 순환 구조를 갖지 않는 그래프이다.

 

 

차이점

 

• 트리는 특수한 형태의 그래프의 일종이며 크게 그래프의 범주에 포함됨
• 트리는 그래프와 달리 어떠한 경우에도 한번 연결된 노드가 다시 연결되는 법이 없음
• 트리는 그래프와 달리 단방향임
• 트리는 하나의 부모 노드와 하나의 루트를 가짐

 

 

 

 

 

트리가 아닌 예

 

트리가 아닌 예

 

• 1) 순환구조임
• 2) C 노드의 부모가 A, D 둘임
• 3) A->B 와 D<-C->E가 서로 연결되어 있지 않으며 루트가 둘임 

 

 

 

 

 

 

 

 

 

 

이진 트리

 

 

이진 트리와 이진 탐색 트리(BST)의 정의

 

• 각 노드가 m개 이하의 자식을 가지고 있으면, m-ary 트리(다항트리, 다진 트리)이며 여기서 m=2일 경우, 즉 모든 노드의 차수가 2 이하일 때는 특별히 이진 트리라고 구분해서 부름
• 이진 트리는 왼쪽, 오른쪽, 최대 2개의 자식을 갖는 매우 단순한 형태로, 다진 트리에 비해 훨씬 간결할 뿐만 아니라 여러가지 알고리즘을 구현하는 일도 좀 더 간단하게 처리할 수 있다.
• 대체로 트리는 이진 트리이다.

 

 

이진 트리의 유형

 

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

 

 

 

 

 

 

 

출처: 파이썬 알고리즘 인터뷰