자료구조(3) : 트리(Tree) 알아보기 및 용어

컴퓨터공학의 자료구조란 데이터를 효율적으로 다루기 위한 규칙이며, 이전 게시물에서 ‘선형구조’를 가진 스택과 큐에 대해 배웠습니다. 이번에는 ‘비선형구조’인 트리(Tree)와 그래프(Graph)에 대해 알아봅시다. 둘 다 데이터가 일렬로 나열되지 않고, 순서도 불규칙적으로 저장되는 형태입니다.

 

자료구조(1) : 자료구조(Data Structure)를 왜 알아야 하나요?

자료구조(2) : 스택(Stack)과 큐(Queue)

 

---

 

트리(Tree)

트리는 그래프의 한 종류로, 최상위가 존재하는 계층적 형태입니다. 실생활에서 가장 쉽게 찾아볼 수 있는 트리는 파일 탐색기입니다. 라이브러리라는 최상위 폴더 아래 폴더가 위치하고, 각각의 폴더 아래에 또 여러 폴더나 파일이 들어 있습니다.

• 트리는 그래프의 여러 구조 중 하나로, '단방향 그래프'의 한 구조입니다.
• 데이터는 하나 이상의 데이터와, 한 방향으로, 한 개의 경로로만 이어지는 '계층적 구조'입니다.
• 데이터 아래에 여러 데이터가 존재할 수 있는 '비선형 구조'입니다.
• 트리는 시작 노드에서 출발해 다시 돌아올 수 없습니다. 사이클이 없는 '연결 그래프' 라고도 합니다.

 

트리 구조의 용어

기본 단위

• 노드(Nood) : 트리를 구성하는 개별 데이터입니다.
• 간선(Edge) : 노드와 노드를 잇는 연결선입니다. 노드가 N개인 트리는 항상 N-1개의 간선을 가집니다.

노드의 구성

• 루트 노드(Root Node) : 단 하나만 존재하는, 트리의 최상단에 있는 노드입니다.
• 부모 노드(Parent Node) : 자식 노드를 가지고 있는, 상대적으로 루트 노드에 가까운 상위 노드입니다.
• 자식 노드(Child Node) : 부모 노드 하위의 노드입니다. 아래에 또 자식 노드를 가질 수 있습니다.
• 형제 노드 (Sibling node) : 같은 부모를 가지는 노드입니다.
• 리프 노드(Leaf Node) : 트리가 더 뻗어 나갈 수 없는 가장 마지막 노드입니다.

레벨 단위

• 깊이(Depth) : 루트에서 특정 노드에 도달하기 위해 거쳐야 하는 간선의 수입니다.
• 레벨(Level) : 같은 깊이를 가지고 있는 노드의 집합입니다.
• 높이(Height) : 리프 노드를 기준으로 루트까지 거쳐야 하는 간선의 수입니다.
• 서브 트리(Sub tree) : 루트에서 뻗은 큰 트리 내부에 트리 구조를 갖춘 작은 트리입니다. 즉, 트리는 트리 안에 또 다른 트리를 가진 재귀적 형태를 가집니다.