야매 개발자 자료구조 가이드[트리(tree)]

트리(Tree)라는 자료 구조에 대해서 알아보자.

트리는 말그대로 나무와 유사한 자료 구조이다. 

뿌리에서 시작해 가지가 뻗어나가고 뻗어나간 가지에서

다시 잎사귀가 생긴것과 유사한 모양을 가지고 있는데 그 나무를 뒤집어 놓은것과 같다.

아래 그림을 보도록 하자

<트리는 위와 같은 구조를 가지고 있다.>

부모자식관계 : B의 부모는 A , B의 자식은 D,E 

루트 : 트리구조에서 가장 위에 있는 노드, 부모가 없다.

노드 : 트리를 이루는 한 요소 (ex 위 그림의 A, B, C , D ....)

차수 : 어떤 노드가 가지고 있는 자식의 노드 개수를 말한다. 예를 들어 B노드의 차수는 2이다.

        (트리의 차수를 말할땐 가장 높은 차수를 말한다. 예를들어

         D노드에 자식이 하나 더 생긴다면 위 트리의 차수는 3이다)

레벨 : 트리를 이루는 각 층의 번호이다. 깊이 내려갈 수록 레벨이 높아진다. 

높이,깊이 : 루트 노드부터 가장 끝에 있는 노드 까지의 깊이(경로의 길이) 

               위 트리의 깊이는 3이다.

Left chaild-right Sibling 표현법

트리의 표현법이다. 아래의 그림처럼 한개의 노드에 자식과 형제의 포인터를 지니는 구조이다.

Child : 자식노드를 가르킨다

Sibling : 형제노드를 가르킨다

가장 위에 있는 노드부터 시작해 왼쪽에 있는 자식노드를 구하고 그 노드의 자식노드와 형제 노드를 구한다

이렇게 반복을 하면 모든 자식 노드를 찾을 수 있게 된다.

이진 트리 (Binary Tree)

최대 2개의 자식 노드를 가질 수 있는 트리이다.

한 노드당 자식을 1개만 가질 수도 있고 아무것도 없을수도 있고 2개를 가질수도 있다.

이진트리의 종류에는

완전 이진 트리(Complete Binary Tree)와 사향 이진 트리(Skewed Binary Tree), 포화 이진 트리(Full Binary Tree)가 있다.

<완전 이진트리(Complete Binary Tree)>

완전 이진트리는 어떤 노드 두개의 레벨차가 1이하 이며 왼쪽부터 오른쪽으로 채워지는 트리 이다.

만약 왼쪽에서 오른쪽으로 가다가 중간에 노드가 비어있다면 그건 완전 이진트리가 아니다.

예를들어 위의 그림에서 E노드 아래에 자식노드가 생성되면 완전 이진트리가 아니게 된다.

<사향 이진트리(Skewed Binary Tree)>

사향 이진트리는 루트노드를 제외한 모든 노드가 부모 노드의 왼쪽 자식 노드이거나 반대로 오른쪽 자식 노드인 것을 말한다. 즉 노드의 방향이 한쪽 방향으로만 치우쳐진 트리이며 다른말로 경사,편향 이진트리 라고 불리기도 한다.

<포화 이진트리(Full Binary Tree)>

포화 이진트리는 완전이진트리와는 다르게 최대한 노드가 가득차 있는 트리를 말한다. 가장 마지막 노드를 제외한 모든 노드가 자식노드를 2개씩 가지고 있다. 

(모든 포화 이진트리는 완전 이진트리 라고 부를수 있지만 그 반대는 성립하지 않는다.). 

이러한 뭔가 당연한것 같은(따로 공부하지 않아도 될것 같은) 트리구조를 왜 알아야 하는지 얼마 전까진 사실 잘 몰랐다. 

그러나 후에 포스팅할 트리의 순회구조와 그 다음 위상정렬(DFS 깊이 우선 탐색), 너비 우선탐색(BFS)를 거쳐

다익스트라 알고리즘과 같은 조금더 난이도 있는 알고리즘을 이해하기 위해선 이 트리구조에 대해서

기본적인 이해가 필요하기 떄문이라는걸 근 일주일간의 삽질 끝에 체감했다.

역시 기초가 중요하다.

참조: http://blog.eairship.kr/215