[내일배움캠프 13일차 TIL] 자료구조 - 트리

사담 💬

오늘 과제 발표가 있었는데 다른 조들 한거 보니까 상대적으로 우리 조가 부족해보였다,,, 우리 조는 요구사항에만 맞춰서 과제 제출했는데 다른 조들은 더 예쁘게, 더 많은 기능을 넣어서 만들어서 놀랬다.... 

---

트리(Tree)?

트리(Tree) 자료구조는 비선형 구조로 계층적인 관계를 표현하는데 사용한다. 트리는 데이터의 저장과 검색, 탐색을 효율적으로 수행할 수 있는 구조를 제공한다.

 

 

트리는 노드(node)와 엣지(edge)로 구성되어있다

노드는 트리의 기본 구성 요소로, 데이터와 자식 노드에 대한 정보를 포함하며,

엣지는 노드와 노드를 연결하는 링크로 부모 노드와 자식 노드 간의 관계를 정의한다.

 

노드는 부모노드, 자식노드, 형제노드, 리프노드가 있다

 

• 부모 노드 (Parent Node): 다른 노드(자식 노드)를 가진 노드
• 자식 노드 (Child Node): 부모 노드에 의해 연결된 노드
• 형제 노드 (Sibling Node): 같은 부모를 가진 노드
• 리프 노드 (Leaf Node): 자식 노드가 없는 노드, 즉 트리의 끝에 위치한 노드

 

그 이외에 트리에서 나오는 용어들은 다음 그림을 참고하자!

 

 

레벨(Level)은 최상위 노드를 Level 0으로 했을 때, 하위 브랜치(Branch)로 연결된 노드의 깊이를 나타낸다

따라서 위 그림의 깊이는 3이 되는 것이다

 

 

 

트리의 종류

트리의 종류에는 아래와 같은 특징을 가진 다양한 트리가 있다.

1. 이진 트리 (Binary Tree): 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리. 자식 노드는 왼쪽 자식과 오른쪽 자식으로 나뉜다
   • 완전 이진 트리 (Complete Binary Tree): 모든 레벨이 가득 차 있고, 마지막 레벨은 왼쪽에서 오른쪽으로 채워져 있는 이진 트리
   • 완전 이진 트리 (Full Binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 가지는 이진 트리
   • 이진 검색 트리 (Binary Search Tree): 모든 노드에 대해 왼쪽 서브트리의 모든 값은 현재 노드의 값보다 작고, 오른쪽 서브트리의 모든 값은 현재 노드의 값보다 큰 이진 트리
2. AVL 트리 (AVL Tree): 자가 균형 이진 검색 트리로, 모든 노드에 대해 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하인 트리
3. 레드-블랙 트리 (Red-Black Tree): 자가 균형 이진 검색 트리로, 노드의 색깔과 규칙을 통해 트리의 균형을 유지
4. B-트리 (B-Tree): 데이터베이스와 파일 시스템에서 사용하는 자가 균형 다진 트리. 각 노드는 여러 자식 노드를 가질 수 있음
5. 힙 (Heap): 우선순위 큐를 구현하기 위한 이진 트리로, 최대 힙과 최소 힙이 있음. 최대 힙은 부모 노드가 자식 노드보다 큰 값을 가지며, 최소 힙은 부모 노드가 자식 노드보다 작은 값을 가짐
6. 트라이 (Trie): 문자열 검색을 위한 트리로, 각 노드는 문자열의 문자를 나타내며, 공통 접두사를 공유하는 문자열들을 효율적으로 저장함

 

 

 

완전이진트리의 배열로 표현

위에 있던 그림이 완전이진트리로 배열로 표현하면

[None, A, B, C, D, E, F, G, H, I]가 된다

트리를 구현할 때는 편의성을 위해 0번째 인덱스는 사용하지 않느다고 한다. 따라서 첫 번째에는 None을 넣어 주어 배열을 만든다.

 

이런 완전이진트리는 다음과 같은 방법으로 트리의 구조를 파악할 수 있다

현재 인덱스를 idx라고 하자, 그러면

• 왼쪽 자식의 인덱스 : idx*2
• 오른쪽 자식의 인덱스 : idx*2+1
• 부모의 인덱스 : idx//2

라는 결과가 나오게 된다.

예를 들어 현재 인덱스를 3이라고 가정해보자. 그럼 현재 인덱스의 값은 "C"일 것이다

3*2 = 6으로 6번째 인덱스의 값은 F로 C의 왼쪽 자식이다.

3*2+1 = 7로 7번째 인덱스의 값은 G로 C의 오른쪽 자식임을 알 수 있다

그리고 3//2 = 1로 1번째 인덱스의 값은 A이다. 이는 C의 부모 노드를 나타낸다.

 

 

---

 

파이썬 주차가 마무리되고 내일부터는 알고리즘 주차가 시작된다. 지금까지는 할만했다 이지만 알고리즘주차가 들어가면 진짜 여러 번 머리를 쥐어뜯게 되지 않을까,,, 다가올 미래가 너무나 두렵지만 어쩌겠어 견디고 버텨야지!