이진 트리 표현하는 방법

이진 트리를 표현하는 방법은 크게 두 가지가 있습니다.

1. 배열을 통해서 표현하는 방법

2. 포인터를 통해서 표현하는 방법

 

배열을 통해서 표현하기

이 방법으로 트리를 표현하게 되면, 특정 위치의 트리 값을 찾을 때 0(1)의 빠른 속도로 가능하나는 장점이 있지만, 편향된 트리 구조에서는 낭비되는 공간이 많다는 단점이 있습니다. 따라서 포화 이진 트리인 경우에는 이 방법을 활용하는 것이 좋겠습니다.

 

구현하는 아이디어는 간단합니다. 아래 그림처럼 루트 노드부터 한 depth씩 내려오면서 배열에 하나씩 기록하는 것입니다.

 

그리고 아래의 몇 가지 규칙을 기억하면 좋습니다.

• level별 노드의 개수 = 2^level
  • ex) depth가 2인 level의 노드의 개수  = 2^2 = 4
• 만들어야할 배열의 크기  = 2^(높이 - 1) - 1
• N개의 노드를 가지는 트리의 높이의 최대 값은 N -1, 최소 값은 log₂N
• 인덱스 i의 노드의 부모 노드의 인덱스는 는 ( i - 1 )/ 2 
• 인덱스 i의 왼쪽 자식 노드는 i * 2 + 1, 오른쪽 자식 노드는 i * 2 + 2

 

포인터를 통해서 표현하기

이 방법은 특별 트리 값을 찾을 때 LogN의 속도가 걸리는 단점이 있지만, 편향된 트리 구조에서도 N만큼의 공간만 있으면 되기 때문에 효율적입니다. 구현하는 방법은 더욱 간단합니다. 제목 그대로 부모노드가 직접적으로 자식 부모를 가리키면 됩니다.