[자료구조] 트리 (Tree)

📌 Questions

1. BST와 Binary Tree에 대해서 설명하세요. (N사 전화면접)
2. Tree가 무엇인가?
3. 이진검색트리에서 검색속도가 가장 느린케이스는 데이터가 어떻게 저장되어 있는 경우인가?

 

---

Tree의 개념

비선형 구조로, 원소들 간에 1:n 관계를 가지는 자료구조

💡 데이터를 어떻게 삽입하고 삭제할 것인지에 대해 관심이 많았던 선형 자료구조에 비해 비선형 자료구조는 데이터의 삽입/삭제보다는 '표현'에 포커스가 맞춰져있다.

트리를 이용해서 무엇인가를 저장하고 꺼내기 보다 트리는 '무엇인가를 표현하는 도구'로 자주 사용되기 때문이다.

드디어 큐를 마지막으로 선형(linear)자료구조 내용이 마무리되고 이제부터는 비선형 자료구조에 대한 내용이 시작된다. 비선형 자료구조의 대표적인 자료구조는 바로 트리(Tree)자료구조다.

가계도나 조직도 등 선형 자료구조로 계층형 구조를 표현하기 어려울 때가 있다. 계층형 구조를 가진 문제를 해결하기 위한 자료구조 형태가 트리이다.

Tree 구성요소

• Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
• Root Node : 트리 맨 위에 있는 노드
• Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 = 부모노드
• Child Node : 어떤 노드의 상위 레벨에 연결된 노드 = 자식노드
• Ancestor node : 어떤 노드보다 위(루트쪽)에 위치한 노드(연결되 있어야 됨) -> 10,5는 6의 조상노드 / 15는 6의 조상노드가 아님.
• descendant node : 조상노드의 역 -> H는 F,G,I의 후손노드.
• Sibling (Brother Node) : 동일한 Parent Node를 가진 노드. = 형제노드
• Leaf Node (Terminal Node) : Child Node가 하나도 없는 노드. = 단말노드
• Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Depth : 트리에서 Node가 가질 수 있는 최대 Level
• Sub Tree : 어떤 노드를 루트로 하고 그 자손으로 구성된 트리
• Null Tree : 노드와 가지가 전혀 없는 트리, 널 트리라고도 함

Tree의 특징

• 그래프의 한 종류이다. '최소 연결 트리' 라고도 불린다.
• 트리는 계층 모델이다.
• 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다.
• Loop나 Circuit이 없다. 당연히 Self-loop도 없다.
• 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.
• 루트에서 어떤 노드로 가는 경로는 유일하다.
• 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
• 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS안에 있다.
• 트리의 종류
  • 이진트리
  • 스레드 이진 트리
  • 최소 신장 트리
  • 이진탐색트리
  • 균형트리 (AVL Tree, Red Black Tree)
  • 이진 힙

 

---

 

Binary Tree

이진트리. 프로그래밍에서 가장 많이 쓰이는 트리

• 이진 트리는 모든 노드들이 두 개의 서브 트리를 갖는 특별한 형태의 트리이다.
• 각 노드가 자식 노드를 최대 두 개까지만 가질 수 있기 때문에 각 노드의 자식 노드를 왼쪽 자식 노드, 오른쪽 자식 노드라고 한다.

 

Binary Tree의 특징

• 레벨 i 에서의 노드의 최대 개수 : 2ⁱ개
• 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수 : (h+1) 개, 최대 개수 : 2^(h+1)-1개

 

Binary Tree의 종류

이진트리는 자식노드가 어떻게 구성되어 있냐에 따라 다음과 같이 5가지로 구분된다.

1. Perfect Binary Tree (포화 이진 트리)

• 모든 레벨의 노드가 포화 상태 (left, right 자식노드가 모두 존재) 이진 트리
• 높이가 h일 때 최대의 노드 개수인 2^(h+1)-1개의 노드를 가진다.
• 루트를 1번으로 하여 2^(h+1)-1까지 정해진 위치에 대한 노드 번호를 가진다.

 

2. Complete Binary Tree (완전 이진 트리)

• 높이가 h이고 노드 수가 n개일 때, 정 이진 트리의 노드 번호 1~n번까지 빈자리가 없는 이진 트리
• 마지막 레벨을 제외한 나머지 노드가 꽉 차 있어야 하며(마지막 레벨을 제외하고 포화 이진 트리이어야 하며), 마지막 레벨의 노드는 왼쪽 부터 차있어야 한다.

 

3. Full Binary Tree (정 이진 트리) :

• 모든 레벨에서 노드들이 모두 채워져 있는 트리 = Leaf Node를 제외한 모든 노드의 차수가 2개로 이루어져 있음

• 해당 차수에 몇 개의 노드가 존재하는지 바로 알 수 있으므로 노드의 개수를 파악할 때 용이함

 

4. Skewed Binary Tree (편향 이진 트리)

• 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리
• 왼쪽 편향 이진 트리, 오른쪽 편향 이진 트리가 있음
• 편향 이진 트리는 검색에 성능 이슈가 있음

⇒ 이런 문제점을 극복하기위해 균형트리(AVL트리, 레드-블랙트리) 같은 변종이 생겨났다.

 

5. Balanced Binary Tree (균형 이진 트리) :

• 트리에 삽입과 삭제가 일어나는 경우에 자동으로 그 높이(루트에서부터 내려갈 수 있는 최대 레벨)를 작게 유지하는 노드기반 이진 탐색 트리
• 왼쪽 그림은 균형이 맞지 않는(unbalanced) 트리 : 루트 → 특정 노드 : 평균 3.27회의 노드 접근
• 오른쪽 그림은 동일한 자료지만 트리 높이 균형을 맞춘 상태 (균형이진트리) : 평균 이동 비용이 3.00 노드 접근
• AVL트리, 레드-블랙트리가 있다.

 

---

 

순서 트리의 순회

- 너비 우선 검색(BFS)

낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법, 즉 맨 위에서부터 왼쪽에서 오른쪽, 왼쪽에서 오른쪽으로 검색하는법

- 깊이 우선 검색(DFS)

전위순회 : 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식
중위순회 : 왼쪽 자식 -> 노드 방문 -> 오른쪽 자식
후위순회 : 왼쪽 자식 -> 오른쪽 자식 -> 노드 방문

리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 하는 방법, 리프에 도달해서 더 이상 검색할 곳이 없으면 일단 부모 노드로 돌아가고 그 뒤 다시 자식 노드로 내려간다.

 

---

 

Binary Tree Traversal

1. 전위 순회 (preorder traversal) : DLR 순서로, 현재 노드를 방문하여 처리하는 작업 D를 가장 먼저 수행
2. 중위 순회 (inorder traversal) : LDR 순서로, 현재 노드를 방문/처리하는 작업 D를 작업 L과 작업 R의 중간에 수행
3. 후위 순회 (postorder traversal) : LRD 순서로, 현재 노드를 방문하여 처리하는 작업 D를 가장 나중에 수행

 

1. Preorder Traversal

전위 순회는 VLR 순서로 순회한다.

1. V : 현재 노드를 출력한다
2. L : 현재 노드 왼쪽 서브트리로 이동한다
3. R : 현재 노드 오른쪽 서브트리로 이동한다

def preorderTraversal(self, node):
    print(node, end='')
    if not node.left  == None : self.preorderTraversal(node.left)
    if not node.right == None : self.preorderTraversal(node.right)

해당 노드를 출력하고 왼쪽으로 이동한다. 왼쪽 노드가 존재하면 계속해서 왼쪽으로 이동하여 출력하고 왼쪽이 끝나는 노드부터 오른쪽 노드를 순회한다.

 

 

2. Inorder Traversal (중위순회)

중위 순회는 LVR 순서로 순회한다. 왼쪽 순회가 우선이고 출력이 중앙에 위치한다.

def inorderTraversal(self, node):
    if not node.left  == None : self.inorderTraversal(node.left)
    print(node, end='')
    if not node.right == None : self.inorderTraversal(node.right)

 

 

3. Postorder Traversal (후위순회)

후위 순회는 LRV로 순회한다. 출력이 마지막에 위치한다.

def postorderTraversal(self, node):
    if not node.left  == None : self.postorderTraversal(node.left)
    if not node.right == None : self.postorderTraversal(node.right)
    print(node, end='')

 

 

---

 

Binary Tree의 표현방법

1. 배열

1-1. 1차원 배열에 저장하는 방법

완전이진트리의 순서와 동일하게 인덱싱한다. 편의상 배열의 첫 번째 요소는 사용하지 않는다.

 

 

1-2. 2차원 배열에 자식 노드를 저장하는 방법 (이진 트리의 경우)

모든 트리가 가능한 것이 아니며, 이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리이기 때문에 2차원 배열로 가능한 것이다. A[i][0]은 왼쪽 자식, A[i][1]은 오른쪽 자식을 의미한다.

장점 : 노드의 위치를 색인에 의해 쉽게 접근할 수 있다. 배열을 기반으로 했을 때 용이한 트리 관련 연산도 존재한다.
단점 : 특정 트리에서 기억 공간 낭비가 심할 수 있다.

공간 낭비의 실제 예시

 

2. 연결 리스트로 표현

• 이진트리를 표시하는 가장 일반적인 방법
• 연결리스트 기반에서는, 트리의 구조와 리스트의 연결 구조가 일치
• ⇒ 구현과 관련된 직관적인 이해가 더 좋은 편
• 왼쪽 자식을 가리키는 포인터 필드, 요소 필드, 오른쪽 자식을 가리키는 포인터 필드를 포함하는 노드로 표현하는 방법
• 모든 이진 트리의 노드들은 데이터타입이 binaryTreeNode인 오브제로 표현된다.
• 필요한 공간 : n * sizeof(binaryTreeNode)     

장점 : 기억 장소를 절약할 수 있고, 노드 삽입과 삭제가 용이
단점 : 이진 트리가 아닌 일반 트리의 경우 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 하기 때문에 접근상의 어려움이 있음

 

 

• 참고자료
  • 윤성우의 열혈 자료구조
  • SW Expert Academy
  • https://www.fun-coding.org/Chapter10-tree.html
  • [https://blex.me/@baealex/파이썬으로-구현한-자료구조-트리]
  • [https://jackpot53.tistory.com/7]
  • [https://smujihoon.tistory.com/153]