이진 트리 Binary Tree

1. 이진 트리

트리마다 자식 노드 수가 제각각이라면, 연산에 대해서 오버헤드가 굉장히 버겁고, 구현도 복잡해지게 됩니다. 그래서 이런 문제를 해결하기 위해 트리의 구조를 일정하게 만드는데, 그 구조 중 대표적인 것이 이진 트리입니다. 이진 트리란, 모든 노드의 차수를 2 이하로 제한 시켜 트리의 차수가 2차 이하인 트리를 의미합니다.

이진 트리는 노드의 차수가 2이하 이므로, 자식 노드가 0개, 1개, 2개까지는 모두 허용이 됩니다. 여기서 트리의 모든 노드의 차수가 2인 트리를 완전 이진 트리라고 하고, 차수가 2미만인 트리가 하나라도 있으면 이진 트리라고 합니다. 다음 그림을 이진 트리라고 합니다. 모든 노드의 차수가 2이하임을 볼 수 있습니다.

이진 트리의 한 모습

 

 

2. 일반 트리를 이진 트리로 바꾸기

일반 트리는 이진 트리에 비해서 효율이 좋지 않기 때문에 구현하는데 애로사항이 있습니다. 그래서 일반 트리를 이진 트리로 바꿔줄 수 있는 방법이 있어서 소개하려고 합니다. 다음 일반 트리를 이진 트리로 변경해보겠습니다.

 

1) 각 노드의 가장 왼쪽 자식 노드 간선만 남기고 나머지 간선을 지웁니다.

2)형제 노드 끼리 간선을 연결합니다.

3) 트리를 시계 방향으로 45도 회전시킵니다. 이때, 루트 노드는 변하지 않습니다.

모양이 조금 이상해 보이지만, 트리를 깔끔하게 정리하면, 모든 노드의 차수가 2이하인 이진 트리가 완성됐음을 알 수 있습니다.

 

 

3. 이진 트리의 특징

이진 트리는 다음과 같은 두가지 특징이 있습니다.

• 노드가 n개인 이진 트리의 간선의 수는 n-1개이다.
• 트리의 높이 h인 이진 트리가 갖는 노드의 개수는 h+1~2^(h+1)-1개이다.

이진 트리의 한 모습

위 트리에서 노드의 수는 12입니다. 이 트리의 간선의 수는 n-1개인 11개입니다.

이 트리의 높이는 3입니다. 이 트리의 노드 개수는 최소 4개~최대 15개 입니다.

최소 4개와 최대 15개

 

 

 

4. 이진 트리의 종류

서론에 짧막하게 완전 이진 트리라는 것을 소개했습니다. 이처럼 이진 트리는 구성에 따라 몇가지 다른 이름을 갖습니다.

 

4-1. 포화 이진 트리

다음 그림과 같이 모든 노드의 자식 노드가 꽉차서 트리의 높이를 증가시켜야지만 노드를 추가할 수 있는 트리를 포화 이진 트리라고 합니다. 포화 이진 트리는 언제나 노드의 수가 높이 h에 대하여 최대 수인 h^(h+1)-1개를 갖습니다.

 

4-2. 완전 이진 트리

완전 이진 트리는 트리에 노드가 n개 있을 때, 노드 위치에 번호를 매겼을 때 마지막 n번까지의 위치가 포화 이진 트리와 일치하는 트리입니다. 말로는 어려운 것 같지만, 그림으로 이해하면 쉽습니다.

다음과 같은 그림처럼 포화 이진 트리에 대해서 번호가 일치해야만 완전 이진 트리라고 합니다.

 

반면, 아래와 같은 그림은 이진 트리이지만, 완전 이진 트리는 아닙니다.

포화 이진 트리가 아님!

 

4-3. 편향 이진 트리

편향 이진 트리는 트리의 높이 h에 대해 노드 갯수가 h+1개를 갖으면서 한 쪽으로만 자식 노드를 갖는 트리를 말합니다. 이때 서브 트리의 방향에 따라 왼쪽/오른쪽 편향 이진 트리라고 합니다.

왼쪽 편향 이진 트리와 오른쪽 편향 이진 트리

---

이진 트리들 간의 상관 관계는 다음과 같습니다.