[Java][자료구조] Tree (1) - 트리의 정의와 특성, 이진트리에 대하여

트리란?

트리라는 이름이 나온 이유는 실제 나무를 거꾸로 세워 놓은 듯한 모양이라서 트리라고 부른다고 한다.

 

트리의 유래

우리는 트리를 배우기 전에 아마 단순한 배열 리스트부터 단순 연결 리스트 이중 연결 리스트 등을 봐왔을 것이다.

그렇다면 이런 것들도 있는데 왜 트리라는 자료구조가 나온 것 일까?

 

일반 배열에서는 삽입이나 삭제를 하는데 O(N)의 시간이 걸린다. 첫 번째 배열에 삽입하는 경우 나머지 모든 요소들을 뒤로 한 칸씩 미뤄야 하므로 최악 시간 복잡도가 O(N)이 나온다.  하지만 트리는 편향 트리가 아닌 이상 일반적인 트리에서는 O(logN) 정도의 시간으로 확 줄여진다. 

 

또 트리는 계층구조를 이루는 경우에 굉장히 좋다. 

트리의 계층 구조

 

회사의 조직도를 생각해보면 맨 위에 회장님, 사장님이 있을 것이고, 부서별, 팀별로 각각 트리가 생길 것이다. 이런 경우 원하는 부서를 찾으려면 타고 내려가기만 하면 되므로 다른 자료구조보다 찾기가 훨씬 쉬워질 것이다.

 

이 정도면 어느 정도 트리가 어떤 경우에 좋을지 감이 잡혔을 것이다. 바로 트리의 용어로 넘어가자.

 

트리의 용어

트리

트리에는 차수, 레벨, 높이 등이 있다. 차수는 가장 많이 가지를 뻗은 것의 개수를 기준으로 한다. 위 트리에서는 차수는 3, 각 트리마다 레벨이 있고, 전체 높이는 4가 될 것이다. 자식 노드, 형제 노드, 이파리 노드, 조상 노드 등 용어는 더 있지만 대부분 어느 정도 알 것이라고 가정하고 실제로 자료구조를 쓸 때는 왜 이진트리를 사용하는지를 보도록 하자.

 

만약 트리의 최대 차수가 3이라고 해보자. 그렇다면 각각의 노드는 3개의 자식을 가질 수 있기 때문에 각각 노드마다 자신의 key값과 3개의 자식을 가질 수 있는 레퍼런스를 생성해야 한다. 노드가 N개 최대 차수가 K 개라고 한다면 필요한 레퍼런스의 개수는 몇 개 일까? N*K개이다. 그렇다면 트리에서 부모 자식을 연결하는 레퍼런스 수는? N-1이다.

정리를 해보면, 노드가 N개 최대 차수가 K개인 트리에서는 이런 식으로 나올 것이다.

전체 레퍼런스 수	NK
노드 간 연결된 레퍼런스 수	N - 1
Null 레퍼런스 수	NK - (N-1) = N(K-1) + 1

당연하게도 Null 레퍼런스의 수가 많아지면 공간을 잡아먹어 비효율적으로 될 것이다. 이제 노드의 수가 같으면서 차수가 다를 때의 경우를 생각해보자.

 

첫 번째 트리는, 10개의 노드와 최대 차수가 3이다. 두 번째 트리는, 10개의 노드와 최대 차수가 2이다.

전체 레퍼런스 수	10 * 3 = 30	전체 레퍼런스 수	20
노드간 연결된 레퍼런스 수	9	노드간 연결된 레퍼런스 수	9
Null 레퍼런스 수	30 - 9 = 21	Null 레퍼런스 수	20 - 9 = 11

전체 레퍼런스의 수도 차이가 나고, Null 레퍼런스의 수도 적으니 이진트리가 훨씬 효율적인 것을 볼 수 있다.

이제 이진트리에 대해 알아볼 시간이다.

 

이진트리

이진트리는 각 노드의 자식 수가 2개 이하인 트리이다. 컴퓨터 분야에서 많이 사용되며 정해진 모양이 아니라 다양한 모양의 트리가 이진트리가 될 수 있다.

 

가장 많이 쓰이는 것은 완전 이진트리이다. 완전 이진트리는 마지막 레벨을 제외한 나머지 레벨은 자식 수가 2개로 꽉 차 있고 마지막 레벨에서는 왼쪽부터 자식이 차는 트리라고 할 수 있다. 그리고 한쪽으로 쭉 뻗어있는 편향 트리도 이진트리라고 할 수 있다. 

 

이제 이진트리의 속성에 대해서 알아보자. 먼저 이진트리의 레벨 별 노드 수와 전체 노드 수에 대한 공식이다.

 

포화 이진 트리 일 때, 레벨 별로 노드의 개수가 1,2,4,8,16...으로 늘어난다. 그러므로 일반적인 이진트리에서 각 레벨 별 최대 노드의 개수는 2^k-1 이 될 것이다. 레벨 별 노드는 공비가 2인 공비 수열이라고 볼 수 있으므로 등비수열의 합으로 생각을 하면 높이가 h인 이진트리가 가질 수 있는 최대 노드 수는 2^h - 1이라고 할 수 있다. 

마지막으로 N개의 노드를 가진 완전 이진트리의높이 = log2log2(N+1)인데 정수로 나오지 않을 경우에는 높임을 해줘야 한다. 노드가 1개라도 더 생기면 새로운 레벨을 만들어 아래 넣어줘야 하기 때문이다.

 

다음 시간에는 이진트리의 탐색 방법인 중위 순회, 전위 순회, 후위 순회에 대해 알아보고 직접 코드를 짜 보도록 하겠다.