자료구조 - 트리, 트리용어

why?

트리를 이용하면 계층적 데이터를 효율적으로 다룰 수 있습니다.

 

 

 

 

 

 

 

 

구성

트리는 노드와 엣지로 구성되어 있습니다.

 

트리의 노드 수는 엣지 수보다 하나 많은 상태를 유지합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

정의

트리의 정의는 재귀적 정의와 비재귀적 정의로 분류할 수 있습니다.

 

 

---

재귀적 정의

1. 비어 있는 것은 트리이다.(null tree)

2. 노드 하나만 있는 것은 트리이다.

3. 트리에 자식노드를 추가한 것은 트리이다.

 

비재귀적 정의

사이클(루프)이 없는 연결된 그래프

 

---

 

 

 

 

 

 

 

 

 

 

 

트리 용어

트리의 용어들은 각각의 노드들을 지칭하거나

관계를 설명할 때 사용하기 때문에 알아두어야 합니다.

 

---

루트

루트란 트리의 최상위에 있는 노드를 의미합니다.

 

 

 

어떠한 트리도 루트를 2개 이상 가질 수 없습니다.

 

또한 루트노드는 전체 트리를 대표합니다.

 

 

 

 

 

 

 

부모 노드

부모 노드란 하위 노드들과 연결되어 있는 노드입니다.

 

 

 

 

 

 

 

 

 

자식 노드

자식 노드란 상위 노드들과 연결되어 있는 노드를 의미합니다.

 

루트 노드는 자식노드가 될 수 없으며,

루트 노드를 제외한 모든 노드는 자식 노드입니다.

 

 

 

 

 

 

 

 

 

형제(siblings)

같은 부모를 가지는 노드들을 형제라고 합니다.

 

 

 

 

 

 

 

 

조상노드

특정한 노드에서 위쪽으로 간선을 따라

만나는 모든 노드들을 조상노드라 합니다.

 

 

 

 

 

 

 

 

자손노드

특정한 노드에서 아래쪽으로

간선을 따라 만나는 모든 노드를 자손노드라 합니다.

 

 

 

 

 

 

 

 

리프노드

자식이 없는 노드를 리프노드라 합니다.

 

외부노드 or 단말노드 라고도 불립니다.

 

 

 

 

 

 

 

내부노드

자식이 있는 노드를 내부노드라 합니다.

 

비단말이라고도 불립니다.

 

 

 

 

 

 

 

레벨

루트에서 얼마나 멀리 떨어져 있는 지를 나타내는 것입니다.

 

깊이라고도 하며, 루트의 레벨은 0입니다.

 

루트에서 간선이 아래로 하나씩 뻗어 내려 갈 때마다

레벨이 1씩 증가하게 됩니다.

 

 

 

 

 

 

 

 

차수(degree)

노드가 가지는 자식의 수를 의미합니다.

A의 자식노드는 B와 C이므로 A의 차수는 2이며,

B의 차수는 3,

C의 차수는 2입니다.

 

 

 

 

 

 

 

서브트리(subtree)

트리에서 루트의 자식을 새로운 노트로 한 후,

그 새로운 루트의 자손노드들을 모두 포함하는 트리를 서브트리라 합니다.