99클럽 코테 스터디 15일차 TIL + 트리(Tree)

학습 키워드

- 트리(Tree)

 

공부한 내용

Tree

• 트리(Tree)는 계층적인 구조를 나타내는 비선형 자료구조로 그래프(Graph)의 특수한 형태이다.
• 트리는 노드(Node)와 간선(Edge)으로 이루어져 있다.

→ 트리는 하나의 루트 노드를 가지고 있으며, 각 노드는 0개 이상의 자식 노드를 가질 수 있다. 이러한 구조로 인해 데이터를 계층적으로 표현할 수 있다.

트리의 주요 개념과 용어

• 노드(Node) : 트리의 기본 단위로 데이터를 저장하는 요소이다. 각 노드는 부모 노드와 하위 노드(자식 노드)를 가질 수 있다.
• 루트(Root) : 트리의 맨 위에 있는 노드로 다른 모든 노드는 루트를 향해 이어진 경로를 가진다. 트리는 하나의 루트 노드만을 가진다.

• 루트 노드 : 트리의 시작 노드로 부모가 없는 최상위 노드이다.

• 간선(Edge) : 노드와 노드 간을 연결하는 선
• 경로(Path) : 특정 노드에서 노드까지의 경로(순서) / 한 번 지나쳤던 경로를 다시 지나는 것은 허락하지 않는다.

트리(Tree)의 장점 및 단점

장점

• 계층적 구조 : 트리는 계층적 구조를 가지고 있기 때문에 데이터를 계층적으로 표현할 수 있다. 이로 인해 트리는 현실 세계의 많은 문제를 효과적으로 모델링할 수 있다.
• 빠른 탐색 속도 : 이진 탐색 트리(Binary Search Tree)의 경우 데이터를 정렬된 상태로 유지하므로 탐색, 삽입, 삭제 연산에 대해 평균적으로 O(log n)의 시간 복잡도를 가진다.
• 자기 참조적 구조 : 트리는 자기 참조적인 구조를 가지고 있어 특정 노드에서 서브 트리 전체를 나타내거나 탐색할 수 있다. 이를 활용하여 효율적인 재귀 알고리즘을 구현할 수 있다.
• 정렬 및 범위 검색 : 이진 탐색 트리와 같은 정렬된 트리 구조는 정렬된 상태를 유지하므로 범위 검색에 유리하다. 정렬된 순서로 데이터에 접근할 수 있어 효율적인 검색이 가능하다.

단점

• 삽입 및 삭제의 복잡성 : 트리의 구조를 유지하기 위해 삽입 및 삭제 연산이 복잡할 수 있다. 특히, 불균형한 트리의 경우 트리의 재조정이 필요할 수 있어 추가적인 연산이 필요하다.
• 메모리 사용 : 트리는 포인터로 연결된 노드 구조를 가지고 있기 때문에 메모리 사용이 비교적 크다. 트리의 균형을 유지하기 위해 추가적인 포인터를 사용하는 경우 메모리 사용이 더욱 증가할 수 있다.
• 순회 순서의 의존성 : 트리의 순회 순서는 트리의 구성에 따라 달라진다. 따라서 트리에 저장된 데이터를 순차적으로 접근해야 하는 경우 순회 순서에 따라 접근해야 하므로 일반적인 순차 자료구조보다는 조금 더 복잡할 수 있다.

트리 종류

편향 트리(skew tree)

• 모든 노드들이 자식 노드를  가진 트리입니다. 경사 트리라고도 불린다. 또한 아래 그림은 왼쪽 자식만 존재하기 때문에 left skew tree라고 한다.

이진 트리(Binary Tree)

• 뒤에서 배울 내용으로 각 노드의 차수(자식 노드)가 2이하인 트리 구조이다.

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

• 굉장히 중요한 트리 구조로 BST라고도 하며 순서화된 이진 트리이다.
• 노드의 왼쪽 자식은 부모의 값보다 항상 작은 값을 가져야 하고 노드의 오른쪽 자식은 부모의 값보다 항상 큰 값을 가져야 한다는 규칙이 존재한다.

m원 탐색 트리(m-way Search Tree)

• 최대 m 개의 서브 트리를 갖는 탐색 트리이다.
• 이진 탐색 트리의 확장된 형태로 높이를 줄이기 위해 사용한다.

균형 트리(Balanced Tree, B-Tree)

• m원 탐색 트리에서 높이 균형을 유지하는 트리이다.
• height-balanced m-way tree라고도 한다.

트리 사용예시

트리는 굉장히 많은 곳에서 사용되고 있다.

<계층적인 데이터 저장>

• 트리는 데이터를 계층 구조로 저장하기 때문에 파일 이나 폴더와 같이 계층구조를 갖는 곳에 사용된다.

<효율적인 검색 속도>

• 효율적인 삽입, 삭제, 검색을 위해 트리 구조를 사용한다.

<힙(Heap)>

• 힙(heap)도 트리를 이용한 구조이다.

<데이터 베이스 인덱싱>

• 데이터베이스 인덱싱을 구현하는데 트리를 사용한다.
• 컴퓨터 공학적 지식에서 굉장히 중요한 일이다.
• 예) B-Tree, B+Tree, AVL-Tree

<Trie 자료구조>

• 사전(Dictionary)을 저장하는 데 사용되는 특별한 종류의 트리이다.

 

회고

발생한 문제

- 코딩 문제를 풀다가 트리에 대해 공부하지 못해서 풀지 못했다. 

 

해결 방법

- 트리에 대해 알아보았다. 

 

추후 학습할 내용

- 트리에 대한 공부를 진행했지만 아직 어려워서 추후 더 공부할 예정이다. 

 

 

참고 자료

- https://readerr.tistory.com/35#google_vignette