[자료구조] 트리 & 트라이 Tree & Trie

트리 Tree

 

노드(Node)와 엣지(Edge)로 이루어진 자료구조이다.

 

트리는 값을 가진 노드(Node)와 노드를 연결해주는 간선(Edge)으로 이루어져있다.

 

위 이미지에서 1을 가진 노드는 루트 노드이다.

 

모든 노드들은 0개 이상의 자식노드를 가지고 있으며 부모 - 자식 관계로 부른다.

 

용어

• 루트 노드(root node): 부모가 없는 노드이다. 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드이다. ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
• Sibling: 같은 부모를 가진 노드이다.

 

 

특징

• 사이클이 존재하지 않는다.
  • 사이클이 존재한다면 이는 트리가 아닌 그래프이다.
• 모든 노드는 자료형으로 표현이 가능하다.
  • 각 노드는 어떤 자료형으로도 표현이 가능하다.
• 루트에서 한 노드로 가는 경로는 유일하다.
  • 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
• 노드의 개수가 N개이면 간선은 N-1개이다.
• 비선형 자료구조로 계층적 관계를 표현한다.
• 최소 연결 트리라고도 불린다.
• 계층 모델이다.

 

종류

전위 순회(pre-order)

각 루트(Root)를 순차적으로 먼저 방문하는 방식이다.

Root → 왼쪽 자식 → 오른쪽 자식 
왼쪽부터 순회한다.

1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14

 

 

중위 순회(in-order)

왼쪽 하위 트리를 방문 후 루트(Root)를 방문하는 방식이다.

 

왼쪽 자식 → Root → 오른쪽 자식

8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 →14 → 7

 

후위 순회(post-order)

왼쪽 하위 트리부터 하위를 모두 방문 후 루트(Root)를 방문하는 방식이다.

 

왼쪽 자식 → 오른쪽 자식 → Root

8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1

 

레벨 순회(level-order)

루트(Root)부터 계층 별로 방문하는 방식이다.

 

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14

 

 

 

트라이 Trie

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.

 

자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어 있는 자료구조이다.

 

래딕스 트리(radix tree) or 접두사 트리(prefix tree) or 탐색 트리(retrieval tree)라고도 불리는데, 

retrieval tree에서 trie를 따온 말이다.

 

예를 들어, 'Datastructure'라는 단어를 검색하기 위해서는 제일 먼저 'D'를 찾고, 다음에 'a', 't', ... 의 순서로 찾게된다.

이러한 개념을 적용한 것이 트라이이다.

 

 

정수형에서 이진탐색트리를 이용하면 시간복잡도 O(logN) 하지만 문자열에서 적용했을 때, 문자열 최대 길이가 M이면 O(M*logN)이 된다.

트라이를 활용하면 O(M)으로 문자열 검색이 가능하다고 한다.

 

 

장점

• 문자열 검색을 빠르게 한다.
• 하나씩 비교하면서 탐색하는 것보다 시간 복잡도 측면에서 더욱 효율적이다.

 

단점

• 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있으므로 저장 공간의 크기가 크다.
  • 메모리 측면에서 비효율적이다.

 

 

구현

 

'abc' 트라이(Trie)에 삽입

1. 자료구조 내에 아무것도 존재하지 않을 때 Head의 자식노드에 'a'를 추가한다.
2. 'a' 노드에 자식 노드가 존재하지 않으므로 'b'를 자식노드로 추가한다.
3. 2번과 마찬가지로 'c'를 'b'의 자식노드로 추가한다.
4. 'abc' 단어를 모두 다 저장했으므로 'c' 노드에 'abc'라고 표시한다. 

 

'abc'  탐색

1. Head의 자식 중 'a' 존재 유무를 확인한 후 'a'로 이동한다.
2. 'a'의 자식노드인 'b'를 찾은 후 'b'로 이동한다.
3. 2번과 마찬가지로 'c'로 이동한다.
4. 'c' 노드에 Data값인 'abc'를 발견하게 된다.