[자료구조] 비선형 자료 구조 ②

1. 트리 자료구조

1) 트리란?

그래프 중 하나로 그래프의 특징처럼 정점 & 간선으로 이루어지며, 트리 구조로 배열된 일종의 "계층적" 데이터의 집합

트리의 특징

① 루트 노드, 내부 노드, 리프 노드로 구성

② 부모, 자식의 계층 구조를 가진다.

• 5번 노드는 6,7번 노드의 부모 노드이고, 6,7번 노드는 5번 노드의 자식 노드이다.
  ③ V-1=E 를 만족, 즉 간선의 수는 (노드의 수-1)이다.
  ④ 임의의 두 노드 사이에는 단 1개의 경로가 반드시 존재한다. 즉 간선이 없는 두 노드는 없으며, 여러 간선을 가지는 두 노드 또한 없다.

2) 트리의 깊이와 높이

① 깊이

• 트리에서의 깊이는 각 노드마다 다르며, 루트 노드부터 특정 노드까지의 최단거리의 거리
• 가령, 5번노드의 깊이는 2이다. (1->3, 3->5)
  ② 높이
• 트리의 높이는 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리를 의미하며, 깊이와 유사한 의미로 혼용해도 무방하다.
  ③ 서브 트리
• 트리 내의 하위 집합

2. 이진 트리

이진트리는 자식의 노드 수가 2개 이하인 트리

1) Types of Binary Tree

① 정이진 트리(full binary tree) : 자식 노드가 0 또는 2개인 이진 트리
② 완전 이진 트리(complete binary tree) : 왼쪽에서부터 채워진 이진 트리. 마지막 레벨을 제외하고는 모든 레벨은 완전히 채워져 있으며(2개의 자식 노드를 가지는 상태), 마지막 레벨의 경우 왼쪽부터 채워져 있다.
③ 변질 이진 트리(degenerate binary tree) : 자식 노드가 하나밖에 없는 이진 트리
④ 포화 이진 트리(perfect binary tree) : 모든 노드가 꽉 차있는 이진 트리
⑤ 균형 이진 트리(balanced binary tree) : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리를 의미

2) 이진 탐색 트리(BST)

노드의 오른쪽 하위 트리에는 노드 값보다 큰 값을 가지는 노드만 & 왼쪽 하위 트리에는 노드 값보다 작은 값을 가지는 노드로만 구성된 트리

• 위와 같이 "검색에 용이"하다는 특성을 가진다.

  Best → O(${log{n}})$
  Worst → O(${n})$

• 최악의 경우 BST는 트리 데이터의 삽입 순서에 따라 "선형적"으로 구성될 수 있기 때문이다.
  

3. AVL 트리

BST가 선형적인 경우 Worst case를 방지하고자 스스로 균형을 잡는 BST이다.

• 두 자식 서브트리의 높이는 항상 최대 1만큼 차이가 난다.