[자료구조] 트리 1. 이진 트리

트리: 계층적인 관계를 가진 자료의 표현에 유용한 자료구조
앞에서 배운 리스트나 스택, 큐, 덱 등은 모두 자료들이 일렬로 나열된 선형 자료 구조였으나, 트리는 계층적인 구조를 가지고 있다.

• 회사의 조직도
• 컴퓨터의 폴더 구조
• 인공지능 바둑 프로그램에 쓰이는 결정 트리

 

트리의 용어

• 루트 노드: 계층적인 구조에서 가장 높은 곳에 있는 노드
  모든 노드는 자신의 서브 트리의 루트 노드이다.
• 간선: 노드와 노드를 연결하는 선
• 부모 노드와 자식 노드: 간선으로 직접 연결된 노드 중에 상위 노드와 하위 노드
• 형제 노드: 동일한 부모 노드를 가지는 노드
• 조상 노드와 자손 노드: 어떤 노드에서 루트 노드까지의 경로상에 있는 모든 노드들과, 어떤 노드 하위에 연결된 모든 노드
• 단말 노드(리프 노드): 자식 노드가 없는 노드
• 노드의 차수: 어떤 노드가 가지고 있는 자식의 수
• 트리의 차수: 트리가 가지고 있는 노드의 차수 중에서 가장 큰 차수
• 레벨: 트리의 각 층에 번호를 매기는 것.
  루트의 레벨은 1이 되고 한 층씩 내려갈수록 1씩 증가한다.
• 트리의 높이: 트리가 가지고 있는 최대 레벨

트리는 하나의 노드가 여러 개의 무수히 많은 자식 노드를 가질 수 있다.
그러나 굳이 방대한 자식의 양을 가지게 만든다면 효율적이지도 않고, 관리하기도 힘들기 때문에 우리는 트리에서도 가장 보편적으로 사용되는 이진 트리를 다룰 것이다.
이진 트리란 모든 노드에서 자식 노드의 개수가 2개 이하인 트리를 말한다.

(사진 출처:  https://www.upgrad.com/blog/5-types-of-binary-tree/)

이진 트리의 특성

• 모든 노드가 2개 이하의 서브 트리를 갖는다. 서브트리는 공집합도 가능하다.
• 모든 노드의 차수가 2 이하이다.
• 자식들 사이에도 순서가 존재한다. 왼쪽 자식이 더 빠른 순서이다.
  따라서 왼쪽 자식과 오른쪽 자식이 확실히 구분된다!

이진 트리의 종류

• 포화 이진 트리: 각 레벨에 노드가 꽉 차있는 이진 트리
• 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨에서 모든 노드가 꽉 차있는 이진 트리. 마지막 노드는 가득 차있지 않아도 되지만 왼쪽부터 차례로 노드가 채워져 있어야 한다.

이진 트리의 성질

• n개의 노드를 가진 트리는 n-1개의 간선을 가진다.
• 높이가 h인 이진 트리는 h개 이상, 2h-1개 이하의 노드를 가진다.
  하나의 노드는 최대 2개의 자식을 가질 수 있으므로 레벨 i의 노드의 최대 개수는 2i-1
• n개의 노드를 가지는 이진트리의 높이는 log2(n+1) 이상이고 n 이하이다.

이진 트리의 표현법

이진 트리는 선형 자료 구조들과 같이 배열과 연결된 구조로 나타낼 수 있다.

• 배열로 표현한 이진 트리
  1) 트리의 높이를 구한다. 트리의 높이가 k라면 길이가 2k-1인 배열이 필요하다.
  2) 포화이진트리의 번호를 인덱스로 사용하여 배열에 노드들을 저장한다. (인덱스 0은 사용하지 않는다)
  배열 표현법은 간단하지만 메모리의 낭비와 표현할 수 있는 트리의 높이가 제한된다는 단점이 있다.
• 연결된 구조로 표현한 이진 트리
  각 노드들은 (왼쪽 자식, 데이터 필드, 오른쪽 자식)의 구조로 구성되어 있으며, 링크 필드를 2개 가진다.
  위 노드를 생성하여 데이터를 추가할 때마다 자식 링크 필드와 연결시켜주면 된다.

class TNode: # 연결된 구조로 표현한 이진 트리의 노드
    def __init__(self, data, left, right):
        self.data = data
        self.left = left
        self.right = right

 

 

작성일자: 2023-03-13