[자료구조] 트리(tress) 정의 및 구현하기

 

 

1. 트리(Tree)란?

데이터가 수직적으로 이루어진 비선형 자료구조

 

트리는 노드(node)들의 집합으로 이루어져있으며, 노드들은 edge로 연결되어있다

 

• 각각의 노드들은 데이터를 포함하고 있다. 
• 트리의 첫번째 노드(가장 위)는 루트 노드(root node)라고 지칭
• 하위 노드들은 자식 노드(children node)라고 칭한다

 

 

• 자식 노드가 없는 노드는 리프 노드(leaf nodes) 또는 외부 노드(external nodes)라고 한다.
• 리프 노드가 아닌 노드는 내부 노드(internal nodes)라고 한다.
• 같은 부모를 가진 노드들은 형제 노드(sibling nodes)라고 한다.

 

 

 

 

• A는 B와 C의 부모 노드이다
• B는 A의 자식 노드이다
• B와 C는 형제 노드 관계이다
• E,F,H,I 그리고 J는 리프 노드이다

 

 

• 깊이(depth)는 루트 노드에서 현재 노드까지의 엣지 수를 의미한다.
  예: 위 그림에서 노드 I의 깊이는 3이다.
• 높이(height)는 현재 노드에서 가장 깊은 리프 노드까지의 엣지 수를 의미한다.
  예: 노드 B의 높이는 2이다. (경로: B → D → H)

 

 

 

---

 

2. 이진 트리(Binary Trees)

이진 트리는 노드들이 자식 노드를 두 개까지만 가질 수 있는 자료구조이다

두 개의 자식 노드는 left node / right node라고 지칭한다

 

이진 트리는 기본적으로 3개의 데이터를 가진다 :

 

1. 노드의 값(value) : integer, string, character, etc

2. left node 포인터

3. right node 포인터

 

 

위 사진은 이진 트리의 일종

 

 

---

 

3. 이진 탐색 트리

이진 탐색 트리는 특정 속성을 만족하는 이진 트리를 지칭한다:

 

하위 트리의 왼쪽 노드는 루트 노드보다 작고, 모든 오른쪽 노드보다 작은 것 

 

위 특성을 이용해서 매우 빠르게 특정 노드를 탐색할 수 있다



 

 

아래처럼, 값 : 4를 탐색하고자 한다면, 10 -> 5 -> 3 3개의 edge만 이용해서 찾고자 하는 값을 탐색할 수 있다!

 

 

 

 

 

트리를 탐색하는 방법으로는 3가지가 있다 :

 

• In-Order Traversal: 왼쪽 → 루트 → 오른쪽 → 결과: A → B → C
• Pre-Order Traversal: 루트 → 왼쪽 → 오른쪽 → 결과: B → A → C
• Post-Order Traversal: 왼쪽 → 오른쪽 → 루트 → 결과: A → C → B

 

4. Full Binary Tree

특성 :

• 모든 잎은 같은 깊이에 존재한다
• 리프가 아닌 모든 노드는 두개의 자식 노드를 가진다

 

5. Complete Binary Tree

특성 :

• 각 레벨에서 가질 수 있는 최대의 노드를 가진다
• 가장 하위 레벨에서 모든 노드들은 가능한 왼쪽에 정렬된다