트리(Tree)의 개념과 종류들

비선형 자료구조, 트리

 

이전까지의 자료구조들은 모두 선형 자료구조였다. 

배열, 리스트, 스택, 큐 등 모두 선의 모양으로 쭉 나열된 형태의 모양이었다면 

트리는 그러한 모양을 띠지 않기 때문에 대표적인 비선형 자료구조라고 불린다. 

 

 

자료구조의 근본적인 모양이 이전과는 다르므로 용어자체도 다른 부분이 많다. 

 

트리 용어

 

위 그림을 보면 용어를 알 수 있는데 정리해보면 다음과 같다. 

 

• 노드(Node) : 각 데이터
• 간선(edge) : 각 노드를 잇는 선
• 부모노드: 현재 노드에서 간선을 통해 위쪽으로 연결된 노드, 1개만 가질수 있다.  
• 자식 노드: 현재 노드에서 간선을 통해 아래쪽으로 연결된 노드  
• Root(+node): 가장 윗부분에 위치한 노드, 부모노드가 없다. 
• 리프 노드: 가장 바깥쪽에 있는 노드
• 내부 노드: 리프노드를 제외한 모든 노드 
• 형제 노드: 부모노드를 공유하는 서로 다른 노드

 

 

 

---

 

 

 

트리는 구조와 특징에 따라 다음과 같이 여러가지 트리로 나뉜다. 

 

 

 

1) 그냥트리 -> 루트노드를 제외한 나머지 노드가 부모노드는 1개만 갖는다는 조건을 제외하면 어떠한 조건도 없다. 

 

2) 이진트리 -> 1) + 자식노드의 개수를 최대 2개로 제한 

 

+ 이진탐색트리 -> (왼쪽자식노드< 현재 노드 < 오른쪽 자식노드)의 기준을 유지, 노드의 값은 유일!  

 

3) 편향트리 -> 한쪽으로만 노드가 치우친 트리  

 

3) 완전이진트리 -> 노드가 위 -> 아래, 왼쪽->오른쪽으로 순서대로 채워진 트리의 형태 

 

4) 포화이진트리 -> 완전이진트리의 조건 + 마지막 리프노드들의 단계에서도 모두 채워진 트리의 형태

 

5) 힙 -> 완전이진트리의 일종으로, 부모노드가 자식노드보다 항상크다, 상황에 따라 항상작게 구현해도 상관없음

(이진탐색트리와 조건 헷갈리지 말것!!)