[파이썬 자료구조] 트리(Trees) - 트리의 개념, 이진트리의 개념

1. 트리(Trees)

트리 (Trees) 란?

→ node와 edge 를 이용하여 테이터의 배치 형태를 추상화한 자료구조

 

https://s3.us-west-2.amazonaws.com/secure.notion-static.com/c0ce3895-a6b3-48af-86c8-b33bf0a1024f/Untitled.png?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Credential=AKIAT73L2G45O3KS52Y5%2F20210830%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20210830T081925Z&X-Amz-Expires=86400&X-Amz-Signature=42dd9d63508d6253440ffe82af1ceedb84d67bea76e6feeff3bade56d920699a&X-Amz-SignedHeaders=host&response-content-disposition=filename%20%3D%22Untitled.png%22

개념 이해를 위해 적당한 그림을 가져왔다.

위의 그림을 보면

• 9개의 노드, 8개의 edge
• Root node = A -> 가장 머리가 되는 노드
• Leaf node = H, I, E, F, G -> 가장 끝에 있는 노드, 즉 자식 노드가 없는 노드
• Internal node = 그외의 노드
• 부모 자식 관계 (parent, child) 그리고 같은 부모 아래 child 들은 sibling 관계
• 부모의 부모 - 조상(ancestor), 자식의 자식 - 후손(descendant)
• 노드의 level → Root 부터 level 0으로 지정 (그림 참조)
• 트리의 높이 (Height) = 최대 수준 (level) +1  (여기서는 4)

• 노드의 차수 (Degree) - 자식(서브트리)의 수

→ 따라서 degree가 0인 노드들은 leaf node 이다.

 

이 정도로 트리의 기본 골격 구조를 설명할 수 있다.

 

 

2. 이진 트리 (Binary Tree)

모든 노드의 차수가 2 이하인 트리 ⇒ 이진트리 (Binary Tree)

 

이진트리는 재귀적으로 정의 할 수 있다.

 

빈트리 (empty tree)이거나

루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리

(단, 이때 왼쪽과 오른쪽 서브트리 또한 이진트리)

=> 이진트리

 

• 포화 이진 트리 (Full Binary Tree)

→ 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리

→ 높이가 k 이고 노드의 개수가 2^k-1 인 이진트리

• 완전 이진 트리 (Complete Binary Tree)

→ 높이 k 인 완전 이진트리

→레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리

→레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리

 

따라서 위의 그림의 경우 완전 이진트리 임을 알 수 있다.