[자료구조] Tree

1. tree 란?

순차적 자료구조 : 리스트, 연결리스트, 스택, 큐 등 저장되어 있는 순서가 있음.(자료를 순서를 매겨 나열한 구조)

비선형 자료구조 : 일렬로 나열하기 힘들고, 자료의 순서가 불규칙해서 연결관계가 복잡한 구조.

tree는 비선형 자료구조에 해당한다.

 

형태가 나무를 뒤집힌 모양과 유사해서 tree라고 부른다.

부모와 자식 간의 관계(계층적 관계)를 표현. (링크드 리스트는 사실상 자식이 한개만 가지고 있는 경우임)

 

 

2. 알아야 할 용어 

노드 : 각 원소

root 노드 : 부모 노드가 없는 최상단 노드.

leaf 노드(terminal 노드) : 자식 노드가 없는 말단 노드.

internal 노드 : leaf 노드를 제외한 모든 노드.

엣지 : 노드들을 잇는 선

경로(path) : 노드와 노드 간 엣지로 연결된 시퀀스를 의미(a노드에서 b노드까지 가는 경로). 경로의 길이(path length)는 경로에 속한 엣지수를 가르킴.

레벨(level) : 노드들의 깊이. root 노드에서 특정 노드간의 깊이 차이.

높이 : 루트노드에서 가장 깊은 노드까지의 레벨(혹은 그 사이의 노드 수)

 

 

3. 트리의 속성

“루트 노드를 제외한 모든 노드는 단 하나의 부모 노드만 가진다.”

→

• 임의의 노드에서 다른 노드로 가는 경로(path)는 유일하다.
• 회로(cycle)가 존재하지 않는다.
• 모든 노드는 서로 연결되어 있다.
• 엣지(edge)를 하나 자르면 트리가 두 개로 분리된다.
• 엣지(edge)의 수 |𝐸| = 노드의 수 |𝑉| - 1