#자료구조_03_트리

Abstract

데이터를 표현하는 한 방법인 트리는 정점과 선분으로 형성된 그래프의 특수한 형태이며, 임의의 두 정점 사이에 사이클을 형성하지 않는 비선형 데이터 구조이며, 주로 포인터를 사용하여 표현한다.

 

1. 트리

트리 구조는 정보의 항목들이 가지(Branch)로 연관되어 데이터를 구성하고 있다. 트리는 어떤 데이터를 저장하는 노드들이 루트 노드라 불리는 노드를 가장 상위로 하여 계층적으로 구성되어 있는 데이터 구조로써, 한 노드에는 그의 자식(child) 노드들이 연결되며, 자식 노드들은 또 자신의 자식을 가지는 계층 구조이며, 사이클을 허용하지 않는다. 임의 노드의 바로 상위 노드를 그 노드의 부모(Parent) 노드라고 한다.

 

트리는 계층적인 데이터를 표현하는 데 사용되며 여러 분야에서 매우 널리 사용되는 중요한 데이터 구조이다.

 

1.1 트리의 정의

트리의 정의는 다음과 같은 조건을 만족하면서 하나 이상의 노드로 구성된 유한된 집합체이다.

1. 단 하나의 루트 노드가 존재해야 한다.
2. 루트 노드에서 각 노드로 가지로 연결되어야 한다.
3. 순환(Loop)를 허용하지 않는다.
4. 루프 노드를 제외한 나머지 노드들은 n(n>=0)개의 서로 분리된 부분집합으로 나누어 진다. 임의의 각 부분집합도 트리 구조이며 이것을 서브 트리라고 한다.

 

트리의 구조

 

1.2 트리 용어

트리에서 사용되는 용어를 설명하기 위해 다음 그림을 예로 들어본다.

트리의 예

노드(Node)는 트리를 구성하는 정점(Vertex)이며, A,B,C,D,E 등을 말한다. 가지(Edge)는 노드 간의 관계를 표시하는 연결선이며, 레벨(Level)은 루트 노드의 레벨을 1로 하고, 그 다음 자식 노드는 2, 그 다음 자식 노드의 자식 노드는 3.. 으로 표시 하는 것이다.

 

루트 노드(Root Node)는 레벨이 가장 낮은 노드인 A가 그림에서의 루트 노드가 되며, 차수(degree)는 서브 트리의 개수로써 A의 차수는 3, B의 차수는 2, C의 차수는 1, K,L,F,G,M,I,J의 차수는 0이 된다.

 

깊이(depth)는 임의의 트리에서 노드가 가지는 최대 레벨이며, 앞의 그림에서는 4가 깊이가 된다. 자식(child) 노드는 어떤 노드에 연결된 다음 레벨의 노드이다. 예를 들어 A의 자식 노드는 B,C,D이며 B의 자식 노드는 E,F 이다.

 

부모(Parent) 노드는 어떤 노드에 연결된 상위 노드이다. 예를 들어 B의 부모 노드는 A이다. 형제(Sibling) 노드는 같은 부모 노드를 가진 노드를 말한다. 예를 들어 B,C,D 노드는 형제 노드이다.

 

단말 노드(Terminal Node 또는 Leaf)는 차수가 0인 노드이며, 앞의 그림에서는 K,L,F,G,M,I,J 가 해당한다. 중간 노드는 차수가 0이 아닌 노드이며, 단말 노드를 제외한 노드를 말한다.

 

숲(Forest)는 분리된 트리의 집합으로써 앞의 그림을 가지고 다음과 같이 표현할 수 있다.

 

숲의 표현