트리 구조, tree 구조

wkdgusrhkd·2021년 2월 22일
0

자료 구조?

목록 보기
1/3
post-thumbnail

데이터를 효율적으로 다루기 위해서는 자료를 체계적으로 정리해야 합니다. 이 때, 데이터의 저장 형식을 자료 구조라 합니다.
여러 자료 구조 中 트리 구조에 대한 공부 내용을 정리해보았습니다.

트리 구조 🌳

트리는 나무를 뜻할 때의 Tree가 맞습니다. 데이터가 나뭇가지처럼 여러 갈래로 뻗어나가는 모습을 닮았기에 트리 구조라 합니다.
아래의 사진을 참고하세요.

↑ 트리 구조, 이미지 출처 ↑

노드와 엣지 🌟

트리 구조의 각 요소들은 노드(node)라고 부르며 서로 연결된 노드들은 부모 or 자식 관계를 가집니다. 부모 노드가 없는 최상위의 노드를 루트(root, 뿌리)라고 하며, 자식 노드가 없는 최하위의 노드를 리프(leaf, 잎)라 부릅니다.
또한 노드와 노드를 잇는 각 선들은 엣지(edge)라고 부릅니다.


트리 구조는 루트에서부터 자식 노드의 개수가 몇 개인지에 따라,

  • 2개면 2진 트리(binary tree)
  • 3개 이상의 n개면 n항 트리(n-way tree)
    혹은 다중 트리(multi-way/branch tree)

라고 지칭합니다.

↑ 2진 트리, 이미지 출처 ↑

레벨, 높이 🚀

트리 구조에서는 부모 노드자식 노드간의 계층이 생깁니다. 이 계층을 레벨 혹은 높이라고 부르는데요. 위의 2진 트리 사진을 보세요.

  • 루트(= 1)레벨 0
  • 2와 3은 레벨 1
  • 4 ~ 7은 레벨 2
  • 8 ~ 15는 레벨 3
  • 리프(= 16 ~ 31)레벨 4

라고 지칭하며, 위 자료구조를 높이가 4인 트리 구조라 합니다.

언제 유용할까? 이진 검색(이진 탐색 트리)

트리 구조는 어떨 때 유용할까요?
이를 알아보기 전에, 이진 검색(binary search)을 먼저 알아 보겠습니다. 이진 검색은 검색 범위를 반으로 나누어 원하는 데이터를 찾을 때까지 반복하는 알고리즘입니다. 이 때, 데이터는 오름차순 or 내림차순으로 정렬되어 있어야만 합니다.

위의 숫자 배열에서 8을 찾기 위한 과정을 나열해 보겠습니다.

  1. 중간값인 11에서 시작합니다.
  2. 8 < 11이므로 왼쪽의 중간값인 3으로 이동합니다.
  3. 8 > 3이므로 오른쪽으로 이동하게 됩니다.
  4. 남은 숫자가 8뿐이므로 원하는 숫자를 찾았습니다.

이진 검색을 트리 구조화시키면 아래의 그림과 같습니다.

위 트리에서 각 노드의 관계는 부모 노드를 기준으로 왼쪽은 작고, 오른쪽 큽니다 자식 노드들이 오도록 되어 있습니다.
이를 2진 탐색 트리라고 부릅니다.

검색에 쓰이는 이진트리의 각 노드에 하나씩 데이터를 격납하는 데이터 구조의 하나. 뿌리의 데이터보다 작은 데이터는 모두 왼쪽 트리 안에 있고, 뿌리의 데이터보다 큰 데이터는 오른쪽 트리 안에 있다. 각 부분 트리는 다시 이진 검색 트리가 되는 순환적인 성질을 띠고 있다. 뿌리의 데이터와 비교하여 목적이 되는 데이터가 좌우 어느 쪽의 부분 트리에 있는가를 판단하여 나누어 간다.

- 네이버 국어사전 -

트리 구조를 사용하는 쉬운 예를 들어봤는데 이해가 잘 되셨을지 모르겠습니다.

트리의 순회 🔄

트리 자료 구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법을 의미합니다. 대표적인 트리 순회 방법은 다음과 같습니다.

  • 전위 순회
  • 중위 순회
  • 후위 순회

균형 트리와 B 트리 🍀

루트에서 가장 아래에 있는 리프까지 높이가 일정하도록 만들어진 트리 구조를 균형 트리(balanced tree)라고 부릅니다.
참고로, 위에서 제시한 예시와 달리 이진 탐색 트리가 항상 균형 트리인 것은 아닙니다. 기준을 어떤 것으로 삼느냐에 따라 균형 트리가 아닐수도 있습니다.

B 트리(B-tree)다중 트리이면서 균형 트리 구조를 가진 트리 구조를 말합니다. B 트리는 노드 하나가 자식 노드를 3개 이상 가질 수 있으며, 어떤 리프에서도 트리의 높이가 거의 같다(평균 트리)는 특징이 있습니다.

B 트리에 대한 추가 내용은 이 영상을 참고 하세요.

profile
프론트!

관심 있을 만한 포스트

0개의 댓글