[자료구조] C - 이진 트리, binary tree

트리(tree)에 대해 알아봤다.

트리는 자료구조의 하나로 우리에게 가장 익숙한 모양의 자료구조라고 할 수 있다.

탐색기처럼 보여지는 구조가 트리 구조라고 할 수 있다. 

트리가 어떤 건지는 탐색기라는 것으로 이미 이해할 수 있을 것이라고 생각이 된다.

이젠 트리의 특징에 대해서 공부해보자

위의 그림에서 보듯이 트리는 부모와 자식으로 이루어져 있습니다.

트리의 모습을 그림으로 표현할 때,

각각의 노드(node)와 간선(edge)으로 부모자식간의 연결을 표현하고 가장 위부터 한층한층을 레벨로 표현합니다. 

가장 아래층의 레벨이 이 트리의 높이라고 말합니다. 부모가 없는 노드는 항상 최상위 노드이기 때문에 트리의 시작이라는 의미로 루트노드(root node)라고 표현합니다. 그리고 자식이 하나도 없는 노드는 가장 끝부분이기 때문에 단말노드( terminal node)라고 한다는 것을 기억해두시면 나머지 특징을 이해할 때 편합니다.

요약하자면

노드 : 각각의 데이터가 저장되는 곳

간선 : 부모-자식간의 관계 연결

루트노드 : 부모가 없는 최상위 노드

단말노드 : 자식이 하나도 없는 노드(더 이상 하위 노드 탐색이 불가능한 노드)

**부모와 자식으로 표현하는데 이것은 구조를 이해하기 쉬운 표현이지 부모와 자식의 연관성이 있는 것은 아니다.

트리는 크게 두가지 종류로 나뉘는데,

가질 수 있는 최대 자식의 숫자가 2개까지인 이진트리와 제한 없이 부모와 자식간의 연결로 표현하는 일반트리로 나뉘어집니다. 탐색기는 일반트리에 속하는데, 규칙성이 없어서 데이터 탐색시에 효율성이 떨어지는 단점이 있습니다. 반면 이진트리는 자식이 최대 2개라는 규칙성을 가지고 있어서 데이터 탐색시 그 효율성이 최대가 됩니다.

이진트리는 데이터가 들어있는 구조에 따라서 3가지로  나뉘어지는데

완전이진트리     : 왼쪽부터 빈자리 없이 순서대로 차있는 트리.

불완전 이진트리 : 차례대로 차있는 트리에서 중간에 빈 자리가 있는 트리

포화이진트리     : 그림처럼 빽뺵하게 꽉꽉 차있는 트리를 말한다. (노드의 개수가 2^n - 1 (n은레벨) 인 트리)

이렇게 말합니다. 

자료구조 트리에서는 데이터 탐색의 효율이 최대화되는 이진트리만을 다룹니다.

이진트리는 앞서 말했듯이, 가질 수 있는 최대 노드가 2개입니다. 노드가 없을 수도 1개일 수도 2개일 수도 있습니다. 이런특징인 것만 알아두면 되고 이제 이진트리의 특징에서 알아보겠습니다.

이진트리의 특징

이진트리의 노드의 개수가 n개라고 가정을 한다면 n개의 데이터가 있고, 각각의 데이터들은 서로 부모-자식의 연결로 되어있어야 합니다. 그래서 연결하는데 필요한 간선의 개수는 (n-1)개이고. 최대한 높게 만드는 방법은 모든 노드가 한줄로 연결되어 있는 듯이 단말노드를 제외한 모든 노드들이 자식이 1개씩 가지는 모양이됩니다. 그래서 노드의 개수만큼의 높이를 만들 수 있습니다.  반대로, 만들 수 있는 최소 높이는 완전이진트리로 표현하는 것이므로 높이 계산은 가우스기호를 사용하여 구할 수 있고 반대로 해당 레벨이 들어갈 수 있는 최대 노드의 갯수는 (2^n - 1)개로 말할 수 있습니다.

이런 특징을 가지고 있는 이진트리를 어떻게 표현할까요?

이진트리 구현

역시나 배열을 사용하는 방법과 링크드리스트를 사용하는 방법 2가지가 있습니다.

배열이진트리는 이진트리를 최상위 노드부터 왼쪽에서 오른쪽 방향으로 차례차례 풀어썼다고 가정하고 이를 배열로 표현하는 방법을 사용합니다. 아래의 그림을 보면 좀 더 이해가 쉬울 것 같습니다.

배열을 인덱스 0부터 사용하는 방법과 1부터 사용하는 방법 2가지가 있는데 차이는 왼쪽이 짝수냐 오른쪽이 짝수냐로 나뉘어집니다. 부모자식 탐색의 자유도는 1부터 시작하는 것이 더 편한게 개인적인 생각입니다.

부모에서 자식을 찾을 때,

0부터 시작할 경우

p * 2 + 1 = L_c

p * 2 + 2 = R_c

p = (L_c-1)/2 || (R_c-2)/2

이렇게 되고,

1부터 시작하는 경우

p * 2 + 0 = L_c

p * 2 + 1 = R_c

p = (L_c)/2 || (R_c-1)/2 

로 표현합니다.

다음 링크드 리스트로 표현하는 방법은

더블링크드 리스트를 만들어서 각각의 좌우 자식들의 주소를 넣어서 표현하는데, 여기서 주의할점은 링크드 리스트의 경우에는 부모로 다시 올라가는 방법이 없습니다. 만약에 부모로 다시 올라가는 탐색을 하고 싶다면 주소필드에 부모를 저장하는 필드를 넣어서 구조체의 모양을 [데이터, *부모주소, *왼쪽자식, *오른쪽자식] 로 만들어서 표현하면 가능합니다.

만들고 삭제하는 것은 링크드리스트 만들기 처럼 하면 충분하니 자세한 설명은 생략하겠습니다.

이상 이진트리 포스팅을 마칩니다.

코드는 추후에 업데이트 예정입니다.