자료구조 트리(Tree) 간단하게 알아보기

Data Structure Tree 자료구조 트리

 

트리(Tree) 란 무엇인가?

트리는 계층 구조(Hierarchical structure)로 이루어진 노드(Node)와 간선(Edge)의 집합이다.

1. 부모-자식 관계의 계층 구조.
2. 다음 노드는 여러 개가 될 수 있지만 이전 노드는 반드시 하나이다.

간선(Edge) 이란?

노드 사이를 연결하는 선이다. 부모-자식간의 관계를 나타내기 위해서 간선을 사용한다.

 

노드의 종류

트리에서 노드의 위치에 따라 구별되는 노드

• 루트(Root) 노드 - 트리의 첫번째 노드이다.
• 단말(leaf) 노드 - 자식 노드가 없는 노드이다.
• 내부(Internal) 노드 - 자식 노드가 있는 노드이다.

트리에서 노드 사이의 관계에 따라 구별되는 노드

• 부모(Parent) 노드 - 자식 노드 바로 위에 연결되어 있는 노드
• 자식(Child) 노드 - 어떤 노드의 아래에 연결되어 있는 노드
• 선조(Ancestor) 노드 - 어떤 노드의 바로 위에 있는 노드부터 루트 노드까지에 있는 모든 노드
• 후손(Descendent) 노드 - 특정한 노드 아래에 연결되어 있는 모든 노드
• 형제(Sibling) 노드 - 같은 - 같은 부모 노드를 가지고 있는 노드

 

 

루트와 간선

맨 위에 있는 노드가 루트(Root) 노드, 노드 사이를 연결하는 간선(Edge)

루트 노드와 간선

 

 

 

내부 노드와 단말 노드

 

자식 노드를 가지고 있는 모든 노드를 내부(Internal) 노드라고 하며, 자식 노드가 없는 모든 노드를 단말(leaf or terminal) 노드라고 한다.

내부 노드와 단말 노드

 

 

 

부모 노드, 자식 노드 와 형제 노드

노드 B에 대해서 알아볼때, B의 부모 노드는 A, B의 형제 노드는 같은 부모인 A를 가지고 있는 C, B의 자식 노드는 D와 E가 된다.

부모 노드와 자식 노드

조상과 후손 노드

이 트리에서 B의 조상 노드는 A, 후손 노드는 D, E, H가 된다.

 

노드의 용어

노드의 용어들

• 레벨(Level) - 루트 노드부터의 거리이다.
• 높이(Height) - 루트 노드로 부터 가장 멀리 있는 노드까지의 간선 개수 + 1이 된다.
• 차수(Degree) - 한 노드가 가지고 있는 자식 노드의 개수이다.

 

레벨의 예시

1. A는 루트 노드이기 때문에 level 1
2. B와 C는 루트 노드로부터 1만큼 떨어져 있기 때문에 level 2
3. D, E, F, G는 루트와 2 만큼 떨어져 있기 때문에 level 3
4. H는 루트와 3만큼 떨어져 있끼 때문에 level 4

노드 레벨

 

 

높이의 예시

1. H는 자식이 없기 때문에 높이가 1
2. E, F, G 도 마찬가지로 자식이 없기 떄문에 높이가 1
3. D 와 C는 가장 멀리있는 노드의 간선이 1개이기 때문에 높이가 2
4. B는 가장 멀리 있는 노드 H까지 간선이 2개이기 때문에 높이가 3
5. A는 가장 멀리 있는 노드 H까지 간선이 3개이기 때문에 높이가 4

노드의 높이

 

 

차수의 예시

1. H, E, F, G는 자식이 없기 때문에 차수는 0
2. D는 자식이 H 하나로 차수는 1
3. B 는 자식이 D 와 E, C는 자식이 F 와 G 2개이기 때문에 차수는 2
4. A는 자식이 B와 C 2개로 차수는 2

노드의 차수

 

서브 트리

• 한 노드의 아래에 있는 모든 노드가 하나 하나의 서브 트리를 이룬다.
  • 왼쪽에 있는 서브 트리가 '왼쪽 서브 트리', 오른쪽에 있는 서브 트리가 '오른쪽 서브 트리'가 된다.

서브 트리의 예시