[자료구조] Tree(트리) with Swift - 개념

안녕하세요. 개발하는 정주입니다.

 

오늘은 "Tree(트리) with Swift"을 정리하였습니다.

 

트리는 포스팅 하나에 다 쓰기에는 중요한 내용이 많더라고요. 

그래서 이번 트리 포스팅에서는 통상적인 트리의 개념과 이진 트리에 대해 다루고

다음 포스팅에서 Swift를 이용해 구현해보겠습니다.

 

B 트리와 B+ 트리는 따로 포스팅할 예정입니다.

 

---

트리란?

트리란 노드(Node)와 간선(Edge)을 이용해 사이클을 이루지 않도록 구성한 데이터 구조입니다.

비선형 자료구조로 계층적 관계를 표현하는데 자주 사용합니다. (ex. 디렉터리, 조직도)

 

트리에 값을 아무렇게나 삽입하면 링크드 리스트와 다른 것이 없지만

트리를 잘! 만들면 자료의 삽입, 삭제 속도가 빠르고 참조와 탐색 속도가 사용 가능할 정도입니다. 

따라서 대규모 데이터를 다룰 때 사용하기 좋습니다. 

 

어떻게 잘 만드는지에 대해서는 아래에서 다룹니다!

 

트리 용어

트리에는 용어가 많고 중요한 게 많습니다.

• 노드 (node) : 트리에서 데이터를 저장하는 기본 요소
  • 루트 노드(root node) : 최상위 노드. 트리에서 루트 노드는 단 한 개 존재합니다.
  • 단말 노드(leaf node) : 최하위 노드. 자식이 없는 노드로, 말단 노드라고도 부릅니다.
  • 내부 노드(internal node) : 단말 노드가 아닌 노드.
  • 부모 노드(parent node) : 상위 노드
  • 자식 노드(child node) : 하위 노드. 자식 노드의 자식 노드를 자손 노드라고 하기도 하지만 자식 노드로 말하기도 합니다.
  • 형제 노드(sibiling node) : 같은 부모를 가지는 노드
• 간선(edge) : 노드를 연결하는 선
• 노드의 크기(size) : 자신 + 모든 자손 노드 개수
• 노드의 깊이(depth) : 루트 노드에서 특정 노드까지 거쳐야 하는 간선의 개수. level이라고도 합니다.
  개념적으로 루트 노드의 depth는 0이 맞지만 일부에선 1로 설정하기도 합니다.
• 노드의 차수(degree) : 각 노드가 지닌 가지의 수.
• 트리의 차수 : 트리의 최대 차수
• 트리의 높이 : 트리의 최대 깊이

루트 노드, 단말 노드, 부모 노드, 자식 노드, 간선, 노드의 깊이는 자주 나오는 용어이니 꼭 알아둡시다.

 

---

트리의 특징

트리의 구조에 대한 특징입니다.

• 비선형 자료 구조
• 트리 내에 또다른 트리가 있는 재귀적 자료구조
• cycle이 없는 무방향 그래프 구조

노드에 대한 특징입니다.

• 루트 노드는 단 한 개만 존재함
• 노드 간에 부모 자식 관계가 있는 계층형 구조
• 노드가 n개인 트리는 항상 n-1개의 간선을 가짐

지금까지 다룬 스택, 큐, 연결 리스트는 모두 선형구조였는데요.

트리는 비선형 구조라는 것이 특징입니다.

계층형 구조를 가지고 있기 때문에 디렉터리 관리, 조직도에서 사용하기 좋습니다.

 

---

트리의 종류

트리는 노드의 구조에 따라 종류가 달라집니다.

쓰고 보니 대부분 이진 트리인데요. 그만큼 이진트리가 중요하다는 거겠죠?

 

편향 트리 (skew tree)

모든 노드들이 자식을 하나만 가지는 트리

왼쪽 방향으로만 자식을 가지고 있으면 left skew tree, 오른쪽 방향으로만 자식을 가지고 있으면 right skew tree라고 합니다.

 

불균형 트리는 트리 탐색에 악영향을 줍니다.

편향 트리가 최악의 불균형 트리이기 때문에 탐색 시간복잡도는 O(n)이 됩니다.

 

이진트리 (binary tree)

각 노드의 자식 노드가 최대 2개인 트리이고 왼쪽 자식과 오른쪽 자식으로 분류합니다.

노드 구조, 개수에 따라 완전 이진트리, 전 이진트리, 포화 이진트리로 나눕니다.

 

완전 이진 트리 (Complete Binary Tree)

트리의 모든 높이에서 노드가 꽉 차 있는 이진트리입니다.

즉, leaf 노드를 제외하면 모든 노드가 자식 노드를 2개 가지고 있어야 합니다.

leaf 노드는 반드시 왼쪽 노드 - 오른쪽 노드 순서로 채워져야 합니다.

 

더 정확히는 무조건 위에서 아래로, 왼쪽에서 오른쪽 순서대로 노드가 채워진 트리입니다.

완전 이진트리는 배열을 사용하여 표현하면 효율적입니다.

 

정 이진 트리 (Full Binary Tree)

모든 노드가 자식 노드를 0개나 2개를 갖는 트리입니다.

완전히 비어있거나 완전히 차있기 때문에 Full이라는 이름이 붙었습니다.

완전 이진 트리나 포화 이진 트리에 비해 비중이 작습니다.

 

포화 이진 트리 (Perfect Binary tree)

모든 레벨의 노드가 꽉 차있는 트리입니다.

 

모든 부모 노드는 자식 노드를 두 개씩 가지고 있고

모든 노드가 가득 차있어 2^h - 1 공식을 이용해 노드의 개수를 구할 수 있습니다.

 

이진 탐색 트리 (Binary Search Tree)

이진 탐색이 항상 동작하도록 구현하여 탐색 속도를 O(log N)으로 극대화시킨 자료구조입니다.

이진 탐색 알고리즘은 반씩 소거하여 탐색하는 알고리즘인데요.

 

일반적인 트리는 편향 트리로 쌓일 가능성이 존재합니다.

따라서 데이터를 쌓을 때 이진 탐색이 동작하게끔 쌓으면 되는데요.

 

자신의 왼쪽 자식 노드에는 자신보다 작은 값이,

자신의 오른쪽 자식 노드에는 자신보다 큰 값이 오는 규칙을 만족해야 합니다.

이때, 모든 노드의 데이터 값을 유일하며 노드의 데이터 값은 항상 존재한다는 가정 하에 구현됩니다.

 

BST는 탐색 속도가 매우 빠릅니다.

그림에서 보면 배열이 10번에 걸쳐 탐색할 동안 BST는 3번 만에 값을 찾을 수 있습니다.

 

---

트리의 순회 (Tree Traversal)

트리의 모든 노드들을 방문하는 과정을 트리 순회라고 합니다.

트리가 비선형 구조이기 때문에 노드를 탐색하기 위한 방법이 필요합니다.

트리 순회는 재귀를 이용해 쉽게 구현할 수 있습니다.

 

트리 순회는 세 가지로 나눕니다. 

• 전위 순회 (Pre-order) : 루트 노드 - 왼쪽 서브 트리 - 오른쪽 서브 트리 순서로 재귀적으로 탐색한다.
• 중위 순회 (In-order) : 왼쪽 서브 트리 - 루트 노드 - 오른쪽 서브 트리 순서로 재귀적으로 탐색한다.
• 후위 순회 (Post-order) : 왼쪽 서브 트리 - 오른쪽 서브 트리 - 루트 노드 순서로 재귀적으로 탐색한다.

순회 구현은 아래 문제에서 다루었으니 참고해주시길 바랍니다.

[Swift 알고리즘] 프로그래머스(Lv.3) - 길 찾기 게임 / 2019 카카오 블라인드

 

---

트리의 활용

트리의 대표적인 활용처는 Heap과 데이터 베이스 인덱싱(Indexing)입니다.

 

Heap

Heap은 완전 이진트리를 기본으로 한 자료구조로, 시간 복잡도 O(log N)을 가집니다.

최댓값 또는 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었고 

최댓값을 찾는 Heap을 Max Heap, 최솟값을 찾는 Heap을 Min Heap이라고 합니다.

 

Max Heap은 부모 노드의 값이 자식 노드의 값보다 항상 큰 Heap입니다.

Min Heap은 부모 노드의 값이 자식 노드의 값보다 항상 작은 Heap입니다.

 

Heap에 대해서는 포스팅을 따로 작성할 예정입니다.

 

데이터 베이스 인덱싱(Indexing)

데이터 베이스 인덱싱에서는 B+ 트리를 사용합니다.

데이터는 모두 Leaf 노드에 들어 있고 이외 노드에 Index가 들어가 있습니다.

 

B 트리는 탐색 성능을 높이기 위해 이진 탐색 트리의 높이를 균형 있게 유지하는 balanced Tree입니다.

이진 탐색 트리처럼 균형 있게 데이터를 삽입하기 때문에 탐색 속도가 빠릅니다.

하지만 데이터를 얻기 위해 항상 Root 노드부터 탐색을 해야 한다는 단점이 있습니다.

 

 

B+ 트리는 B 트리의 단점을 해소하기 위해 만들어졌습니다.

B+ 트리는 B 트리에서 Leaf 노드를 연결 리스트 형태로 변경한 버전입니다.

데이터가 들어있는 Leaf 노드 간 이동이 가능하여 보다 효율적인 탐색이 가능합니다.

 

데이터 베이스에서 가장 중요한 것은 검색 속도이기 때문에 B+ 트리는 데이터 베이스에 없어서는 안 될 자료구조이죠.

 

Trie

Trie라는 자료 구조도 트리의 응용으로  문자열 자동 완성 알고리즘에 사용되는 자료구조입니다.

[Swift 알고리즘] 프로그래머스(Lv.4) - [3차] 자동완성 / 2018 카카오 블라인드

 

코딩 테스트 문제에서 처음 알게 된 자료구조로 위 포스팅에 소개가 되어서

이번 포스팅에서는 아주 간단하게만 작성했습니다 ^^!

 

---

마무리

이번 포스팅에서는 트리의 개념에 대해 다루었습니다.

실제 구현도 중요하고 개념도 무척이나 중요한 자료구조입니다.

꼭 알아둡시다!

 

다음 포스팅에서는 Swift를 이용해 직접 구현해보겠습니다.

 

 

---

출처

https://babbab2.tistory.com/91?category=908011 

 

잘못된 점이 있다면 댓글로 알려주시면 감사하겠습니다.

감사합니다.