[자료구조] 트리(Tree)

트리(Tree)

파이썬 리스트나 연결리스트는 데이터를 일렬로 저장하기 때문에 탐색 연산이 순차적으로 수행된다.

이진탐색을 사용하면 효율적인 탐색이 가능하기 때문에 삽입이나 삭제 후에도 정렬 상태를 유지해야한다.

트리는 이러한 문제점을 보완한 계층적 자료구조이다.

 

일반적인 트리

1. 트리의 루트는 A이다.

2. B, C, D는 각각 A의 자식노드이고 A는 이들의 부모노드이다. 따라서 A의 차수는 3이다.

3. K, L, F, M, N, I, O, P는 트리의 이파리이다.

4. {B, C, D}, {E, F, G}, {H, I}, {K, L}, {O, P}는 각각 서로 형제노드이다.

5. C를 루트로 하는 서브트리는 C와 C의 후손노드({H, I, N})로 구성된 트리이다.

6. P의 조상노드는 {J, D, A}이다.

7. 트리의 높이는 4이다.

 

일반적인 트리를 메모리에 저장하기 위해서는 각 노드에 키와 자식 수만큼의 레퍼런스를 저장해야한다.

따라서 트리 노드의 최대 차수가 k라면, k개의 레퍼런스 필드를 선언해야한다.

최대 차수가 k인 트리에 N개의 노드가 있다면, None 레퍼런스 수는 N*k - (N - 1) = N(k - 1) + 1 이다.

N*k는 총 레퍼런스 수, (N - 1)은 트리에서 실제 부모 자식을 연결하는 레퍼런스 수이다.

 

따라서 k가 클수록 메모리의 낭비가 심해지고 트리를 탐색하는 과정에서 None 레퍼런스를 확인해야 하므로 시간적으로도 매우 비효율적이다.

왼쪽자식-오른쪽형제(Left Child-Right Sibling)

위의 단점을 보완해주는 자료구조이다. 노드의 왼쪽 자식과 왼쪽 자식의 오른쪽 형제노드를 가리키는 2개의 레퍼런스를 사용하여 표현한다.

(a) 일반적인 트리

(b) 왼쪽자식-오른쪽형제 표현 트리

 

(a)의 일반적인 트리를 왼쪽자식-오른쪽형제로 표현하면 (b)형태의 트리를 얻는다.

왼쪽자식-오른쪽형제 표현은 노드의 차수가 일정하지 않은 일반적인 트리를 구현하는 매우 효율적인 자료구조이다.

HTML, XML의 문서 트리, 운영체제의 파일시스템, 탐색트리, 이항힙과 같은 우선순위 큐에서 사용된다.

 

정리

1. 트리는 계층적 자료구조로서 파이썬 리스트나 연결리스트의 단점을 보완하는 자료구조이다.

2. 일반적인 트리는 최대 차수가 클수록 메모리의 낭비가 심해지고 시간적으로도 비효율적이다. 

3. 왼쪽자식-오른쪽형제 표현은 노드의 차수가 일정하지 않은 일반적인 트리를 구현하는 매우 효율적인 자료구조이다.