자료구조 - 트리란?

자료구조( 트리 )

계층적인 관계(Hierarchical Relationship)을 나타내는데 편리한 것이 트리(Tree) 입니다.

가령, 조부모, 부모, 자식, 손자 같은 족보라던가, 사장, 전무, 상무, 부장, 과장 등의 조직도 역시

마찬가지로 계층적인 관계입니다.

다음은 컴퓨터의 디렉터리 계층 구조를 나타내는 그림입니다.

계층적으로 묘사될 수 있는 것은 무엇이든지 트리로 나타낼 수 있으며,

이러한 현상은 매우 많다. 예를 들어 우리가 의사결정하기 위한 과정 역시 트리로 표현 할 수 있습니다.

다음은 수신된 메일이 스팸메일인자 아닌지를 결정하기 위한 결정트리 입니다.

● 트리의 구성 요소

트리의 구성요소에 해당하는 A,B, C ~ F 가 바로 노드라고 합니다. A 바로 밑에 있는 B, C를 A 의 자식노드(Child Node) 라고 하며, A 는 B, C의 부모노드(Parent Node) 입니다.   D,E,F 는 서로 자매노드(Sibling Node) 라고 부릅니다. 주어진 노드의 상위노드들은 해당 노드의 조상노드(Ancestor Node) 라고 하며, 반대로 하위노드들은 후손노드(Descendant Node) 라고 합니다.   A처럼 부모가 없는 최상위 노드를 루트노드(Root Node) 라고 하며 D, E, F 처럼 자식이 없는 노드를 단말노드(Leaf Node) 리프노드를 제외한 모든 노드들을 내부노드(Internal Node) 라고 합니다.

● 트리의 종류와 특징

둘 이상의 자식을 가질 수 있는 노드를 일반트리(General Tree) 라고 하며, 최대 두 개 까지

자식을 가질 수 있는 트리를 이진트리라고 합니다.

트리의 레벨 이란 루트노드를 레벨 0 으로 하여, 아래로 내려오면서 증가합니다.

트리의 높이 는 트리의 최대레벨을 뜻 합니다.

(높이가 3인 완전이진트리)

- 정 이진트리(fully binary tree)

 모든 노드가 0 또는 2개의 자식을 지님. 즉 단말노드를 제외한 모든 노드가 2개의 자식을 지님.

- 포화 이진트리(perfect binary tree)

 기본적으로 정 이진트리의 속성을 만족 하며, 모든 단말노드가 같은 레벨에 있는 트리를 말한다.

 즉 높이 h 인 트리에서 모든 단말노드가 h레벨에 존재해야 한다.

- 완전 이진트리(complete binary tree)

 완전 이진트리란, 트리의 높이를 h라 할 때, 높이가 h - 1(마지막 이전 레벨) 까지는 포화 이진트리

 이고, 마지막 레벨은 왼쪽부터 채워나가는 형태의 이진트리를 의미한다.

- by Raimondo