Tree?

Tree란?

- 노드들이 나무 가지처럼 연결된 비선형(acyclic) 계층적 자료구조이다.

- 트리는 트리 내에 다른 하위 트리(sub tree)가 있고 하위 트리 안에 또 다른 하위트리가 있는 재귀적 자료구도이다.

 

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
• 내부 노드(internal): 단말 노드가 아닌 노드
• 간선(edge): 노드를 연결하는 선, link, branch라고도 부른다. - 간선은 정점의 개수 -1개를 가진다. (노드 5개면 간선 4개)
• 형제(sibling): 같은 부모를 가진 노드
• 노드의 크기(size): 자신을 포함한 모든 자식 노드의 수
• 노드의 깊이(depth): 루트에서 해당 노드까지 도달할 떄 거치는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선(degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

트리의 특징

• 하나의 루트 노드와 0개 이상의 하위 트리로 구성되어 있습니다.
• 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조입니다.
• 트리내에 또 다른 트리가 있는 재귀적 자료구조입니다.
• 단순 순환(Loop)을 갖지 않고, 연결된 무방향 그래프 구조입니다.
• 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며 모든 자식 노드는 하나의 부모 노드만 갖습니다.
• 노드가 n개인 트리는 항상 n-1개의 간선(edge)을 가집니다.

이진트리(Binary tree)

- 노드가 왼쪽 자식노드와 오른쪽 자식노드 하나씩만 가지는 자료 구조

 

이진 트리 종류



Full binary tree : 모든 노드의 자식이 0이거나 2인 이진 트리

complete binary tree : 마지막 노드(리프 노드)를 제외하고 모든 노드의 두명의 자식이 있는 트리 마지막 노드의 삽입은 왼쪽으로 되어있어야 한다.

perfect binary tree : 리프노드를 제외한 모든 노드가 2개의 자식노드를 가져야하면 루트노드를 기준으로 좌우가 균형이어야 한다.

balanced binary tree : 모든 노드의 왼쪽과 오른쪽 하위 트리의 높이차가 최대 1만큼 차이가 날 수 있는 트리이다.