[Swift] 스터디 5주차 - 트리 구조 기반의 알고리즘

5/18 진행했던 스위프트 데이터 구조와 알고리즘 책의 5장 '트리 구조 기반의 알고리즘' 스터디 정리입니다!

---

🎄

1. 트리의 특징

2. 트리 vs 그래프

3. 이진 트리, 이진 트리의 종류

4. 이진 탐색 트리(BST, Binary Search Tree)

5. 트리 순회 방식

6. B 트리와 스플레이 트리

---

 

🎄 트리(Tree)

트리는 노드의 집합으로, 계층을 이루고 있는 데이터 구조를 의미합니다. 

트리의 최상위 노드인 루트 노드, 그 아래로 뻗어나가는 자식 노드로 구성됩니다. 

각각의 노드는 키 값, 자식 노드 집합, 부모 노드 링크 등을 포함하고 있는 데이터 구조입니다.

 

트리의 특징

트리는 그래프의 한 종류로, 사이클이 없는 하나의 연결 그래프입니다.

트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있습니다.

트리의 순회 방식은 Pre-order, In-order, Post-order 로 이루어집니다.

---

👀 트리(Tree) vs 그래프(Graph)

그래프는 꼭지점(Vertex, 노드)과 모서리(Edge)의 집합으로 이루어진 데이터 구조입니다.

 

트리는 그래프의 한 종류로, 사이클이 없는 하나의 연결 그래프입니다.

사이클이 없다는 것은 같은 노드를 순환하지 않는다는 뜻입니다. 두 노드 사이에 경로가 하나입니다.

 

Tree vs Graph

 

✔︎ 이진 트리(Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드만 지닐 수 있는 트리입니다.

 

1) 풀 이진 트리(Full binary tree)

각 노드가 0 or 2개의 자식 노드를 갖는 트리입니다.

 

2) 완전 이진 트리(Complete binary tree)

마지막 레벨을 제외한 모든 레벨이 노드로 완전하게 채워진 상태입니다. 마지막 레벨의 노드는 좌측부터 채워져야 합니다.

 

3) 퍼펙트 이진 트리(Perfect binary tree)

모든 내부 노드가 2개의 자식 노드를 지니며, 모든 잎 노드가 동일한 깊이를 가지는 트리입니다.

 

 

4) 균형 이진 트리(Balanced binary tree)

(노드의 삽입과 삭제가 일어나는 경우) 잎 노드까지 이어지기 위한 높이를 작게 유지하도록 하는 트리입니다. 

 

💡 균형 이진 트리(Balanced binary tree) 가 중요한 이유

 

이진 트리는 이진 검색 트리의 기반이고, 이진 탐색 트리에서 L < P, R >= P 규칙을 지켜야하기 때문에 1~4 순서대로 삽입하면 편향된 이진 트리(Skewed Binary Tree)가 됩니다. 이 경우 트리의 높이가 커지게 되고, 4를 찾기 위해서는 4번의 탐색이 필요합니다. 즉, 시간 복잡도는 O(n) 이 됩니다.

 

이러한 최악의 경우를 피하기 위해 균형 이진 트리를 이용합니다. 노드의 삽입과 삭제가 일어나는 경우, 높이가 최소가 되도록 유지하는 것입니다. 이 경우 시간 복잡도는 O(logn) 입니다. 대표적인 균형 이진 탐색 트리는 AVL 트리, 레드-블랙트리가 있습니다.

 

편향된 이진 트리 vs 균형 이진 트리

 

 

✔︎ 이진 탐색 트리(BST, Binary Search Tree)

이진 탐색 트리는 노드 P 가 다음의 조건을 만족하는 트리입니다. 즉, 현재 노드를 기준으로 좌측은 현재 노드보다 작은 값, 우측은 현재 노드보다 큰 값이어야 합니다.

1. 좌측 서브트리에 있는 모든 노드 L.value < P.value
2. 우측 서브트리에 있는 모든 노드 R.value >= P.value 

 

이진 검색 트리는 이진 트리를 기반으로 데이터 접근, 검색, 삽입, 삭제 등을 수행합니다. 시간복잡도는 O(n) ~ O(logn) 으로 트리의 높이에 영향을 받습니다.  이 때, n 개의 노드를 지닌 완전 이진 트리의 경우, O(logn) 의 시간 복잡도. 편향된 이진 트리 (연결 목록)으로 구성된 경우 O(n) 의 시간 복잡도를 갖습니다.

---

✔︎ 이진 탐색 트리 순회 방식

트리를 순회할 때 특정한 순서에 따라 각 노드를 방문합니다.

 

1) 중위 순회(In-order tree walk, in-order traversal)

"좌측 서브트리 -> 루트 노드 값 -> 우측 서브트리" 순서에 따라 각각의 서브트리를 재귀적으로 방문합니다.이진 탐색 트리의 노드 값은 "좌측 값 < 루트 노드 값 < 우측 값" 이므로, 노드의 값이 오름차순으로 정렬된 시퀀스가 반환됩니다.

func traverseInOrder(node: BinaryTreeNode?) {
    guard let node = node else {
        return
    }
    BinaryTreeNode.traverseInOrder(node: node.leftChild)
    print(node.value)
    BinaryTreeNode.traverseInOrder(node: node.rightChild)
}

 

2) 전위 순회(Pre-order tree walk)

"루트 노드 값 -> 좌측 서브트리 -> 우측 서브트리" 순서에 따라 각각의 서브트리를 재귀적으로 방문합니다.

BST 노드를 차례대로 복사할 때 유용합니다.

func traversePreOrder(node: BinaryTreeNode?) {
    guard let node = node else {
        return
    }
    print(node.value)
    BinaryTreeNode.traversePreOrder(node: node.leftChild)
    BinaryTreeNode.traversePreOrder(node: node.rightChild)
}

 

3) 후위 순회(Post-order tree walk)

"좌측 서브트리 → 우측 서브트리 → 루트 노드" 순서에 따라 각각의 서브트리를 재귀적으로 방문합니다.

좌측 하단에서 시작해 우측 상단으로 이동해 올라가면서 노드를 출력합니다. 삭제 작업을 할 때 유용합니다.

func traversePostOrder(node: BinaryTreeNode?) {
    guard let node = node else {
        return
    }
    BinaryTreeNode.traversePostOrder(node: node.leftChild)
    BinaryTreeNode.traversePostOrder(node: node.rightChild)
    print(node.value)
}

 

✔︎ B 트리

이진 탐색 트리(BST)와 비슷하지만, 두 가지 차이점이 있습니다.

1. 자식 노드의 수가 2개로 한정되지 않습니다.
2. 노드가 지닌 key 데이터 역시 1개로 한정되지 않습니다.

 

B 트리는 스스로 균형을 잡고, 스스로 정렬, 루트 노드를 스스로 설정하는 트리입니다. 균형이 잡혀있기 때문에 O(logn) 내에 노드의 삽입, 검색, 삭제, 접근이 가능합니다.

 

데이터베이스와 파일시스템에서 많이 사용되는 자료구조입니다.

---

✔︎ 스플레이 트리 (Splay tree)

이진 탐색 트리(BST)의 특수한 형태로 최근에 접근한 노드가 트리의 상위로 이동하는 트리입니다. 노드에 대한 접근이 매우 빈번한 상태에서 최근 방문한 노드를 골라낼 수 있어, 노드 검색 시간을 줄일 수 있습니다.

---

참고링크

• [geeksforgeeks] Difference between graph and tree
• https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

 

더 알아보기

• 이진 힙(최대힙, 최소힙)
• 그래프(Graph)