• 계층적인 데이터 구조, 데이터 Node와 간선 Edge로 연결되는 비선형 자료구조

기본 구조

• 상위 Node에서 하위 Node의 관계를 가지며, 각 관계별 Node를 아래 용어로 일컫는다
  • Root : 최상단 노드, 트리는 하나의 Root를 가짐
  • Leaf : 끝단 노드
  • Internal : 중간 중간의 일반 노드
  • Sibling : 같은 부모를 가지고 있는 노드

특징

• 계층 구조 : Root에서 시작해 여러 가지를 통해 데이터를 구성한다
• 비선형 구조 : Node의 관계가 선형적이지 않고 계층을 이룬다
• 부모, 자식 관계 : 각 Node는 하나의 부모 Node를 가지며, 하나 이상의 자식 Node를 가질 수 있다

종류

기본 트리

이진 트리, Binary Tree

• 모든 Node가 최대 두 개의 자식을 가질 수 있는 구조

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

• 이진 트리의 종류로써, 왼쪽 자식 Node는 부모보다 작고, 오른쪽 자식 Node는 부모보다 큰 값을 가진다
• 위 특징은 검색에 용이한데, 숫자로 된 데이터를 이진 탐색 트리에 저장하고 탐색한다 치면, 기준값 Root로 바로 비교해서 검색해볼 수 있기 때문

균형 트리

AVL Tree

• 균형을 유지하는 이진 탐색 트리, 삽입, 삭제 후에도 높이의 균형을 유지한다

Red-Black Tree

• 각 Node를 Red 또는 Black의 색깔을 가지며 균형을 유지하는 이진 탐색 트리