[알고리즘]트리(Tree)

트리

• 비선형 자료구조
• 계층적인 자료를 표현하는데 적합한 자료구조
  ex) 컴퓨터 디렉토리 구조, 인공지능 문제(결정트리)

트리는 한 개 이상의 노드로 이루어진 유한 집합이다.

이진 트리

• 모든 노드가 2개의 서브 트리를 가지고 있는 트리

-서브 트리는 공집합일 수 있음
-서브트리간에 순서가 존재함
-n개의 노드를 가진 이진 트리는 n-1개의 간선을 가짐
-높이 h일때 노드 개수 : 최소 h , 최대 2^h-1

이진 트리 분류

포화이진트리(full binary tree)

-트리의 각 레벨에 노드가 꽉 차있는 이진트리
-전체 노드 개수는 정확히 2^h-1
-번호 매기는 방법 : 레벨 단위로 왼쪽에서 오른쪽으로

완전 이진 트리(complete binary tree)

-높이가 k일때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 
 마지막 레벨에서는 왼쪽부터 오른쪽으로 순서대로 채워져 있는 이진트리
-따라서 포화이진트리는 항상 완전이진트리
-노드번호는 포화 이진 트리와 동일

스레드 이진 트리(threaded binary tree)

이진 트리의 NULL 링크를 활용하여 순환 호출 없이도 트리의 노드들을 순회 할 수 있음

이진 트리 표현 방법

• 배열
• 포인터

배열을 이용한 이진 트리

노드 i의 부모 노드 인덱스 = i / 2
노드 i의 왼쪽 자식 노드 인덱스 = 2i
노드 i의 오른쪽 자식 노드 인덱스 = 2i + 1

링크 표현법

왼쪽 포인터
오른쪽 포인터
데이터

순회 방법

VLR : preorder traversal(전위순회)
LVR : inorder traversal(중위순회)
LRV : postorder traversal(후위순회)

이진 탐색 트리(BST)

이진 탐색 트리 : 이진 탐색 트리의 성질을 만족하는 이진트리

- 모든 원소의 키는 유일한 키를 가진다.
- 왼쪽 서브 트리 키들은 루트 키보다 작다.
- 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

삭제 연산

삭제 연산 시에는 세 가지 경우를 고려해야 한다.

1. 삭제하려는 노드가 단말 노드일 경우
2. 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우
3. 삭제하려는 노드가 두개의 서브 트리 모두 가지고 있는 경우

이진 탐색 트리의 분석

• 레벨 당 두배로 노드의 개수가 늘기 때문에 이진탐색 트리의 높이는 log N
• 이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간복잡도는 O(트리의 높이)
• 따라서 이진 탐색 트리의 평균적인 경우의 시간 복잡도는 O(log h)
• 단 최악의 경우(경사 트리) : O(N)