[ 자료구조 ] 트리(Tree)란?

트리(Tree)란

• 트리는 노드로 이루어진 자료구조
  • 트리는 하나의 루트 노드를 갖는다.
  • 루트 노드는 0개 이상의 자식 노드를 갖는다.
  • 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.
• 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다.
• 트리에는 사이클(cycle)이 존재할 수 없다.

https://code-lab1.tistory.com/8

• 노드들은 특정 순서로 나열될 수 도 있고 그럴 수 없을 수도 있다.
• 각 노드는 부모 노드로의 연결이 있을 수도 있고, 없을 수도 있다.
• 각 노드는 어떤 자료형으로 표현 가능하다.
• 비선형 자로구조로 계층적 관계를 표현한다.
  • Ex) 디렉터리 구조, 조직도
• 그래프의 한 종류
  • 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)
  • DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류
• 컴퓨터의 directory 구조가 트리 구조의 대표적인 예다.

출처: https://yoongrammer.tistory.com/68

 

 

트리(Tree) 관련 용어

출처: https://yoongrammer.tistory.com/68

• 노드(Node)
  • 트리를 구성하고 있는 기본 요소
  • 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음
• 루트 노드(root note): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, '말단 노드' 또는 '잎 노드'라고 부른다.
• 내부(internal) 노드: 단말 노드가 아닌 노드
• 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
• 형제(sibling): 같은 부모를 가지는 노드
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

트리(Tree)의 특징

• 그래프의 한 종류이다. '최소 연결 트리'라고도 불린다.
• 트리는 계층 모델이다.
• 루트에서 어떠 노드로 가는 경로는 유일하다.
  • 임의의 두 노드 간의 경로도 유일하다.
• 한 개의 루트 노드만이 조재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.

트리 자료구조의 필요성

• 계층적인 데이터 형태들을 트리에 저장하면 자연스럽게 표현된다.
  • 회사나 정부의 조직 구조
  • 나라, 지방, 시 군별, 계층적인 데이터의 저장
  • 인덱스 (인덱스는 계층적 자료구조로 검색을 쉽게 해준다.)

REFERENCE

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

[자료구조] 트리(Tree)란 - Heee's Development Blog

https://yoongrammer.tistory.com/68

[자료구조] 트리 (Tree)

https://code-lab1.tistory.com/8

[자료구조] 트리(Tree)의 개념 | 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐