자료구조 - 트리(Tree)

트리의 정의

: 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조.
[네이버 지식백과] 트리 [tree] (천재학습백과 초등 소프트웨어 용어사전)

앞서 보인 큐(Queue), 스택(Stack) 은 자료구조에서 선형 구조라고 한다. 선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미한다. 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다.

자료 1) 트리의 구조 (출처)

트리 용어 설명

• Node: 트리에서 데이터를 저장하는 기본 요소
• Root Node: 트리 맨 위에 있는 노드
• Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
• Child Node: 어떤 노드의 하위 레벨에 연결된 노드
• Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
• Sibling: 동일한 Parent Node를 가진 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level

트리의 종류

: 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등 되게 다양한 종류가 있다.

이진트리(Bionary Tree)

: 각 노드가 최대 두개의 자식을 갖는 것을 특징으로 하는 트리

자료 2) 이진트리 예시

자료에서 위의트리는 level 0의 자식 노드가 3개. 따라서 이진트리가 아니다.

• 완전 이진 트리(Complete Binary Tree)
  : 노드가 최하단 왼쪽 노드부터 차례대로 삽입된 형태의 트리
  자료 3) 완전 이진트리 예시
  

트리를 배열로 표현하는법

: 트리를 구현할 때는 편의성을 위해 0번째 인덱스는 사용되지 않는다 => null값을 배열에 넣고 시작

자료 4) 트리의 표현 방법 - 배열을 이용

이때,
1. 현재 인덱스 * 2 => 왼쪽 자식의 인덱스
2. 현재 인덱스 * 2 + 1 => 오른쪽 자식의 인덱스
3. 현재 인덱스 / 2 => 부모의 인덱스