트리 | 이진트리

이진트리

이진 트리는 배열이나 포인터로 구현할 수 있습니다. 배열로 이진 트리를 구현하는 방법을 먼저 알아본 후, 포인터로 구현하는 방법을 알아보겠습니다. 이진 트리는 아래와 같이 노드 하나가 최대 2개의 자식 노드를 갖습니다.

 

 

배열로 표현하기

배열은 선형 자료구조이고 트리는 계층 자료구조입니다. 따라서 배열로 트리를 표현하려면 다음 3가지 규칙이 필요합니다. 참고로 이 규칙은 루트 노드를 배열 인덱스 1번이라고 생각하여 작성한 규칙입니다.

 

• 루트 노드는 배열 인덱스 1번에 저장합니다.
• 왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 x  2 입니다.
• 오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 x 2 + 1입니다.

 

위 규칙에 맞게 인덱스를 붙이면 다음과 같을 것입니다.

정말 규칙에 맞게 되었는지 역으로 확인해봅니다. 실선 화살표를 따라가며 인덱스를 확인해보면 1 → 2  → 4 → 8 입니다. 익덱스 부모 x 2 로 증가합니다. 점선 화살표를 따라가며 인덱스를 확인해보면 1 → 3 → 7 입니다. 인덱스가 부모 인덱스 x  2 + 1로 증가합니다. 실제 배열에 이진트리를 저장하면 다음과 같습니다.

루트 노드를 인덱스 0 으로 하면 왼쪽 자식 노드는 부모 노드의 배열 인덱스 x 2 + 1이 되고, 오른쪽 자식 노드는 부모 노드의 배열 인덱스 x 2 + 2가 됩니다. 입력값에 따라 루트 노드를 0 혹은 1로 정해야 하는 경우가 있으므로 알아두시면 편합니다. 참고로 인덱스를 0으로 하면 인덱스를 1로 정했을 때와 특정 노드의 인덱스 계산식이 달라집니다. 인덱스를 반드시 1로 해야하는 건 아니므로 필요하다면 인덱스를 0으로 해도 좋습니다.

 

트리를 표현한 배열을 보면 빈 갑싱 꽤 많아 보입니다. 노드들의 부모-자식 관계를 곱셈 연산하여 배열의 인덱스로 사용하기 때문에 실제 노드 개수보다 많은 공간을 사용할 수 밖에 없습니다. 즉, 배열로 트리를 표현하면 자식이 없거나 쓰지 않는 인덱스들은 모두 빈 값이므로 메모리가 낭비된다는 단점이 있습니다. 그렇다고 해서 배열 표현 방법이 나쁘다는 건 아닙니다. 이진 트리를 배열로 표현하는 방식은 굉장히 구현 난이도가 쉬우므로, 메모리만 넉넉하다면 구현 시간을 단축하는 용도로 좋습니다. 다행히도 대부분 코딩 테스트에서는 배열로 이진 트리를 구현해도 괜찮은 경우가 많습니다. 참고로 이진트리의 노드가 N개일 때, 배열로 이진 트리를 생성하면 O(N)이 걸립니다.

 

이진 트리 순회하기

이진 트리 구현 방법을 알았으니 이제는 이진 트리에서 순회하는 방법을 알아봅시다. 순회란 어떤 데이터가 있을 때 그 데이터를 빠짐 없이 방문하는 것을 의미합니다. 트리에서 데이터를 검색하려면 트리를 순회할 수 있어야합니다. 배열에서 인덱스로 데이터를 검색할 때 순회하는 것처럼 트리도 순회할 방법이 필요합니다. 이진 트리에서의 순회는 당므과 같이 총 3가지 방법이 있습니다.

 

• 전위 순회(preorder) : 현재 노드를 부모 노드로 생각했을 때 부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순서로 방문합니다.
• 중위 순회(inorder) : 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드 순서로 방문합니다.
• 후위 순회(postorder) : 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드 순서로 방문합니다.

순회에서 주목해야 할 표현은 '현재 노드를 부모 노드로 생각했을 때' 입니다. 이 컨셉을 이해해야 순회를 쉽게 이해할 수 있습니다. 우선 이 표현에 주목해야 한다는 것만 기억해두고 각 순회 과정의 설명을 보면서 더 깊게 이해해봅시다.

 

전위 순회 과정 살펴보기

그럼 전위 순회부터 봅시다. 전위 순회는 현재 노드를 부모 노드로 생각했을 때 부모노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순서로 방문합니다.

 

01단계

루트 노드에서 시작합니다. 현재 노드를 부모로 생각하면 방문 순서는 1 → 4 → 8 입니다. 그러니 노드 1(자신, 현재부모)을 방문한 다음 왼쪽 자식인 노드 4로 이동합니다. 

 

02단계

노드 4로 이동했습니다. 방문 순서는 4 → 3 → 5 이므로 자신을 방문하고 3으로 이동합니다.

 

03단계

노드 3으로 이동했습니다. 방문 순서는 3 → 2 → (오른쪽 자식 없음)이므로 자신을 방문하고 2로 이동합니다.

 

04단계

노드 2로 이동했습니다. 2  → (왼쪽 자식 없음) → (오른쪽 자식 없음)이므로 자신을 방문하고, 더 방물할 자식이 없으므로 3으로 거슬러 올라 값니다.

노드 3은 3 → 2 → (오른쪽 자식 없음)입니다. 자신과 왼쪽 자식은 이미 방문했고 더 방문할 자식도 없습니다. 부모로 거슬러 올라갑니다.

노드 4에서는 4 → 3 → 5입니다. 5로 이동합니다.

 

05단계

마찬가지로 노드 5는 본인을 출력하고 방문할 자식이 없으므로 거슬러 올라가 노드 1까지 갑니다. 노드 1은 오른쪽 자식만 남았으므로 노드 8로 이동합니다.

 

06단계

이런 방식으로 출력하면 1  → 4 → 3 → 2 → 5 → 8 → 7 → 6 순서로 트리를 순회하게 됩니다.

 

전위 순회는 이렇게 거치는 노드를 우선 방문(출력)하므로 직관적으로 이해하기 쉽습니다. 전위 순회는 트리를 복사할 때 많이 사용합니다.

 

중위 순회 과정 살펴보기

중위 순회는 현재 노드를 부모 노드로 생각했을 때 방문 우선순위가 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드입니다. 다시 말해 중위 순회는 거쳐가는 노드, 즉, 현재 노드를 거치기만 할 뿐 '방문'하지 않습니다. 바로 이 지점이 처음 공부하는 사람에게 '중위 순회는 난해하다'라고 여기게 만듭니다.

 

방문이란?

방문이라는 표현을 자주 사용하고 있습니다. 탐새에서 방문이란 탐색을 마친 상태를 말합니다. 탐색 과정에서 지나치는 것과 그렇지 않은 것을 구분하기 위해 방문이라는 용어를 사용합니다. 다음 그림을 보면 가운데 노드는 지나가기만 했고, 나머지 노드는 방문을 완료했습니다.

 

01단계

1에서 방문 우선순위는 4 → 1 → 8이므로 우선 4로 이동합니다. 이렇게 중위 순회는 현재 자신을 부모 노드로 생각했을 때 왼쪽 자식 노드를 우선해야 하므로 부모노드는 지나갈 뿐 방문하지는 않습니다.

 

02단계

노드 4에 와서도 마찬가지입니다. 자신을 부모 노드로 생각했을 때 방문 우선순위는 3 → 4 → 5이므로 노드 3으로 이동합니다.

 

03 단계

노드 3은 2 → 3 → (오른쪽 자식 없음) 입니다. 2로 이동합니다.

 

04단계

노드 2는 (왼쪽 자식 없음) → 2 → (오른쪽 자식 없음)입니다. 자신을 방문하고 거슬러 올라갑니다.

 

05단계

노드 3은 2 → 3 → (오른쪽 자식 없음)입니다. 즉, 방문 순서가 이제 자신입니다. 자신을 방문하고, 오른쪽 자식이 없으므로 거슬러 올라갑니다.

 

06단계

노드 4는 3 → 4 → 5 입니다. 자신을 방문하고 오른쪽 자식 5로 갑니다.

 

07단계

노드 5는 (왼쪽 자식 없음) → 5 → (오른쪽 자식 없음)입니다. 자신을 방문하고 거슬러 올라갑니다. 노드 4는 모든 노드를 방문했습니다. 1로 거슬러 올라갑니다.

※ 굵은 선이 이동, 색칠한 원이 방문입니다. 여기부터는 말푼선 표시를 하지 않겠습니다.

 

08단계

노드 1은 4 → 1 → 8 입니다. 자신을 방문하고 오른쪽으로 이동합니다.

 

09단계

노드 8은 (왼쪽 자식 없음) → 8 →  7 입니다. 자신을 방문하고 오른쪽으로 이동합니다.

 

10단계

노드 7은 6 → 7 → (오른쪽 자식 없음)입니다. 6으로 이동한 다음 6은 자식이 없으므로 방문합니다.

 

11단계

마지막 노드 7을 방문합니다. 중위 순회는 2 → 3 → 4 → 5 → 1 → 8 → 6 → 7 순서로 노드를 방문합니다.

 

중위 순회 방문 과정을 살펴보았습니다. 이를 통해 현재 자신을 부모로 생각했을 때 방문 우선순위를 따지는 방법을 알았기 바랍니다. 중위 순회는 이직 탐색 트리에서 정렬된 순서대로 값을 가져올 때 사옵됩니다.

 

후위 순회 과정 살펴보기

후위 순회는 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 → 오른쪽 자식 →부모 순서로 방문합니다.

 

01단계

노드 1부터 시작합니다. 4 → 8 → 1이므로 일단 4로 이동합니다.

 

02단계

노드 4도 마찬가지입니다. 3 → 5 → 4 이므로 3으로 이동합니다.

 

03단계

노드 3은 2 → (오른쪽 자식 없음) → 3 이므로 2로 이동합니다.

 

04단계

노드 2는 (왼쪽 자식 없음) → (오른쪽 자식 없음) → 2 이므로 자신을 방문하고 3으로 거슬러 올라갑니다. 아마 중위 순회를 이해했다면 이후 과정도 쉽게 상상할 수 있을 것입니다.

 

05단계

노드 3은 2 → (오른쪽 자식 없음) → 3입니다. 2는 이미 방문했고, 오른쪽 자식이 없으니 자신을 출력하고 거슬러 올라갑니다.

 

06단계

이런 식으로 방문하면 2 → 3 → 5 → 4 → 6 → 7 → 8 → 1 순서로 방문합니다.

 

지금은 이해가 잘 되지 않겠지만 노드를 삭제할 때는 부모를 먼저 삭제하면 안됩니다. 자식 노드 부터 삭제해야 트리를 유지하며 재귀로 루트 노드까지 삭제할 수 있기 때문입니다. 그래서 자식 노드부터 방문한다는 특성이 있는 후위 순회는 트리 삭제에 자주 활용됩니다.

 

포인터로 표현하기

이번에는 포인터로 트리를 표현하는 방법을 알아보겠습니다. 포인터로 트리를 표현하려면 노드부터 정의해야 합니다. 다음 그림처럼 노드는 노드의 값, 왼쪽 자식 노드와 오른쪽 자식 노드를 가집니다.

 

이 노드 구성을 트리에 적용하면 다음과 같습니다.

 

포인터로 표현한 트리는 배열과 달리 인덱스 연산을 하지 않으므로 메모리 공간을 낭비하지 않습니다만 실제 노드를 따라가도록 구현해야 하므로 구현 난이도는 배열로 표현한 트리에 비해 조금 높습니다.

 

인접 리스트로 표현하기

이번에는 인접 리스트로 트리를 표현하는 방법을 알아보겠습니다. 인접 리스트로 트리를 표현하려면 정점의 번호(수)만큼 리스트를 만들어야 합니다. 리스트는 해당 정점에서 연결된 노드의 번호가 됩니다.

 

인접 리스트로 표현하면 자식 노드의 수가 2개 이상일 경우도 표현하기 좋습니다. 또한 메모리 공간이 크게 낭비되지도 않고, 어떤 정점에서 이동할 수 있는 다음 정점을 빠르게 탐색할 수도 있어 시간 복잡도 면에서도 상당히 이점이 많아 인접 리스트는 트리를 포함한 그래프 문제에서 가장 많이 사용하는 표현 방식입니다.