04 트리와 이진트리 (Tree & Binary Tree) 기본

트리 (Tree)

---

계층적인 구조를 표현하기 위한 자료구조로 여러 노드가 한 노드를 가리킬 수 없는 구조를 의미합니다. 일반적으로 조직도, 디렉토리 구조등을 생각하면 됩니다. 스택이나 큐와 같은 선형구조가 아닌 뒤집어놓은 나무 모양 같은 계층구조를 가지며, 탐색이나 계층적 구조를 가져야 하는 데이터를 다루는데 많이 사용됩니다.

 

 

 

트리의 특징

---

▶ 트리는 노드(A,B,C,D,E,F)와 노드들 사이를 이어주는 링크로 이루어져 있습니다. 트리의 노드가 n개라면 링크의 개수는 n-1개가 됩니다. 최상위 노드 A를 루트 노트라고 부르며 B,C를 가지노드라 하며 D,E,F와 같이 자식을 가지지 않는 최하위 노드들을 리프노드라고 부릅니다.

 

▶ 트리는 기본적으로 부모-자식 관계를 가집니다. A노드 입장에서는 B,C의 자식 노드를 가지고 B,C 노드 입장에서는 A노드의 자식 노드가 됩니다. 그리고 같은 부모노드로부터 파생된 B,C 노드를 형제노드라고 부릅니다.

▶ 트리에서 차수는 한 노드가 가지는 자식 노드의 수를 의미합니다. A노드의 차수는 2이며 C 노드의 차수는 1입니다. 일반적으로 트리의 차수라고 함은 해당 트리에서 가장 높은 차수를 의미합니다.

 

▶ 트리의 레벨은 루트 노드를 1번으로 하는 각 층의 번호입니다. Level1은 A에 해당되며 Level2는 B와 C에 해당이 됩니다. 그리고 트리의 높이라 함은 트리의 가장 높은 레벨인 3을 의미하게 됩니다.

 

 

이진트리 (Binary Tree)

---

이진 트리(Binary Tree)는 최대 2개의 자식 노드를 가질 수 있는 노드를 의미합니다. 즉 한개의 노드가 2개의 자식노드를 가지거나 한개를 가지거나 아예 안 가질수 있습니다.

 

 

완전 이진 트리 (Complete Binary Tree)

---

▶위의 트리는 완전 이진 트리로 루트 노드를 시작으로 하여 왼쪽에서부터 오른쪽으로 빠지지 않고 채워져 있는 트리입니다. 만약 중간에 노드가 하나라도 빠지면 그것은 완전 이진 트리가 아닙니다. 예를 들어 위에 트리에서 C노드가 빠진다면 위의 트리는 완전 이진 트리라고 부를 수 없습니다. 완전 이진 트리는 왼쪽 자식과 오른쪽 자식에 따라 다른 트리라고 봅니다. 예를 들어 A노드의 왼쪽 자식 노드가 B이고 오른쪽 자식 노드를 C인 완전 이진 트리와 반대로 A노드의 왼쪽 자식 노드가 C이고 오른쪽 자식 노드가 B인 경우에는 서로 다른 완전 이진 트리라고 합니다. 이것은 자식이 한 개인 경우에도 동일합니다.

 

포화 이진 트리 (Full Binary Tree)

---

▶ 포화 이진 트리는 완전 이진 트리처럼 왼쪽에서 오른쪽으로 채워져 있는 노드입니다. 다만 차이점은 리프 노드를 제외하고 모든 노드들의 차수가 2이며, 리프 노드는 자식을 가지지 않는다는 것입니다. 말 그대로 트리가 가득 차 있는 형태를 의미합니다.

 

▶ 포화 이진 트리에서 높이가 h인 경우의 노드의 개수는  

개입니다.

 

▶ 포화 이진 트리와 완전 이진 트리에서 노드가 n개인 이진 트리의 높이는 O(logn)이 됩니다. 최악의 경우네는 n이 될수도 있습니다.

 

출처 : https://lktprogrammer.tistory.com/67?category=676210