[자료구조] 트리

트리란?

 

정점과 간선을 이용하여 데이터 배치 형태를 추상화한 자료구조로, 그래프의 일종이다.

계층적 관계를 표현하는 비선형 자료구조로, 사이클이 없는 하나의 연결그래프이다.

트리의 특징

• 사이클이 없다
• 부모-자식의 계층적 관계로 표현된다,
• 루트노드를 제외한 모든 노드는 단 하나의 부모노드를 가진다.
• 저장된 데이터를 더 효과적으로 탐색하기 위해 사용한다.
• 하나의 루트노드와 0개 이상의 하위 트리로 구성되어있다.
• 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.

트리가 될 수 없는 경우

1. node의 edge가 자기 자신을 향하는 경우
2. path에서 cycle이 생기는 경우
3. node가 2개 이상의 parent를 가지는 경우
4. 서로 연결되지 않은 subtree가 존재하는 경우

트리 관련 용어

 

노드 (Node)

• 트리를 구성하고 있는 기본 요소
• 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음.

간선 (Edge)

• 노드와 노드 간의 연결선

루트 노드 (Root Node)

• 트리 구조에서 부모가 없는 최상위 노드

부모 노드 (Parent Node)

• 자식 노드를 가진 노드

자식 노드 (Child node)

• 부모 노드의 하위 노드

형제 노드 (Sibling node)

• 같은 부모를 가지는 노드

외부 노드(external node, outer node), 단말 노드 (terminal node), 리프 노드(leaf node)

• 자식 노드가 없는 노드

내부 노드 (internal node, inner node), 비 단말 노드 (non-terminal node), 가지 노드 (branch node)

• 자식 노드 하나 이상 가진 노드

깊이 (depth)

• 루트에서 어떤 노드까지의 간선(Edge) 수
• 루트 노드의 깊이 : 0

높이 (height)

• 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선(Edge) 수
• 리프 노드의 높이 : 0

Level

• 루트에서 어떤 노드까지의 간선(Edge) 수

Degree(차수)

• 노드의 자식 수

Path(경로)

• 한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서

Path Length

• 해당 경로에 있는 총노드의 수 (경로 길이)

Size

• 자신을 포함한 자손의 노드 수

Width

• 레벨에 있는 노드 수

Breadth

• 리프 노드의 수

Distance

• 두 노드 사이의 최단 경로에 있는 간선(Edge)의 수

Order

• 부모 노드가 가질 수 있는 최대 자식의 수
• Order 3 : 부모 노드는 최대 3명의 자식을 가질 수 있다.

 

 

이진 트리

이진 트리는 2개 이하의 자식노드를 가지는 트리를 뜻한다. 2개의 자식노드 중 왼쪽 노드를 Left Node, 오른쪽 노드를 Right Node라고 한다.

편향 이진 트리

편향 이진 트리는 하나의 차수로만 이루어져 있는 경우를 의미한다. 이러한 구조는 배열(리스트)와 같은 선형 구조이므로 'Leaf Node'(가장 아래쪽에 위치한 노드) 탐색 시 모두 데이터를 전부 탐색해야 한다는 단점이 있어 효율적이지 못하다.

전 이진 트리

모든 노드가 0개 또는 2개의 자식노드를 갖는 트리이다.

완전 이진 트리

• 완전 이진 트리란 모든 높이에서 노드가 꽉 차있는 이진 트리, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져있다.
• 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽부터 오른쪽 순서대로 채워져야 한다.
• 배열을 통해 효율적으로 표현할 수 있다.

포화 이진 트리

포화 이진 트리는 전 이진트리이면서 완전 이진트리인 형태이다.

• 모든 리프 노드는 같은 높이에 있어야 하며, 마지막 레벨에서 노드의 개수가 최대가 되어야 한다.
• 모든 내부 노드가 두 개의 자식 노드를 가진다.
• 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다.
• 노드의 개수가 정확히 2^(k-1)개여야 한다. (k: 트리의 높이) -> 흔하게 나타나는 경우가 아니다. 즉, 이진 트리가 모두 포화 이진 트리일 것이라고 생각하지 않는다.

이진 탐색 트리

이진 탐색 트리는 탐색을 위한 이진 트리 기반의 자료구조이다.

• left Node에는 부모노드보다 작은 값이 저장된다.
• right Node 에는 부모노드보다 큰 값이 저장된다.
• 모든 노드는 중복된 값을 가지지 않는다.

---

참고 레퍼런스

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

[자료구조] 트리 (Tree)

[자료구조] 트리 (Tree)

[자료구조] 트리 (Tree)