[자료구조] Tree

※ 2022년 1월 2일에 작성된 글입니다.

🌲 Tree

계층적인 구조를 나타내는 자료구조

Tree의 구성

• 노드(node)
  트리를 구성하고 있는 각각의 요소
• 루트(root)
  트리에서 최상위에 있는 노드
• 서브트리(subtree)
  하나의 노드와 그 노드들의 자손들로 이루어진 트리
• 단말 노드(terminal node)
  하위 노드가 없는 노드
• 비단말 노드(internal node)
  적어도 하나의 하위 노드를 가지는 노드

Tree의 용어

• 레벨(level)
  트리의 각 층의 번호
• 높이(height)
  트리의 최대 레벨
• 차수(degree)
  노드가 가지고 있는 하위 노드의 개수

Tree의 응용 분야

• 계층적인 조직 표현
• 파일 시스템
• 인공지능에서의 결정 트리

Binary Tree

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

• 서브 트리는 공집합일 수 있다.
• 이진 트리의 노드에는 최대 2개까지의 하위 노드가 존재한다.
• 모든 노드의 차수가 2 이하가 된다.
  = 구현하기가 편리하다.
• 이진 트리에는 서브 트리 간의 순서가 존재한다.

Binary Tree의 성질

• 노드의 개수가 n개이면 간선의 개수는 n-1개
• 높이가 h인 이진 트리의 경우, 최소 h개의 노드를 가지며 최대 2h-1개의 노드를 가진다.
• n개의 노드를 가지는 이진 트리의 높이는 최대 n이거나 최소 log2(n+1)

Binary Tree의 분류

• Full Binary Tree(포화 이진 트리)
  트리의 각 레벨에 노드가 꽉 차있는 이진 트리
• Complete Binary Tree(완전 이진 트리)
  높이가 h일 때 레벨 1부터 h까지는 노드가 모두 채워져 있고 마지막 레벨 h에서는 왼쪽부터 오른쪽으로 순서대로 채워져 있는 이진 트리

Binary Tree의 표현

• 배열표현법

0	1	2	3	4	5	6	7	8	9
	A	B	C	D	E	F
모든 이진 트리를 포화 이진 트리라고 가정하고 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법
* 링크표현법
```
↙ A ↘
↙ B ↘ ↙ C ↘
↙ D ↘ ↙ E ↘ ↙ F ↘
```
포인터를 이용하여 상위 노드가 하위 노드를 가리키게 하는 방법

Binary Tree의 순회

• preorder traversal(전위 순회)
  루트 → 왼쪽 하위 → 오른쪽 하위
• inorder traversal(중위 순회)
  왼쪽 하위 → 루트 → 오른쪽 하위
• postorder traversal(후위 순회)
  왼쪽 하위 → 오른쪽 하위 → 루트
• level-order traversal(레벨 순회)
  루트부터 계층 별로 방문

수식 트리

산술식을 트리 형태로 표현한 것

• 비단말 노드(internal node) = 연산자(operator)
• 단말 노드(terminal node) = 피연산자(operand)

수식 트리 계산

후위 순회를 사용한다.

• 서브 트리의 값을 재귀 호출로 계산한다.
• 비단말노드를 방문할 때 양쪽 서브 트리의 값을 저장된 연산자를 이용하여 계산한다.

Thread Binary Tree

NULL 링크에 중위 순회 시에 후속 노드인 중위 후속자(inorder successor)를 저장시켜 놓은 트리

• 이진 트리의 NULL 링크를 이용하여 순환 호출 없이도 트리의 노드들을 순회한다.
• 단말 노드와 비단말노드의 구분을 위해 isThread 필드가 필요하다.

Binary Search Tree

탐색 작업을 효율적으로 하기 위한 자료 구조

• 이진 탐색 트리에 저장된 키는 유일하다.
• 왼쪽 서브 트리의 키 <= 루트 노드의 키 <= 오른쪽 서브 트리의 키
• 왼쪽/오른쪽 서브 트리도 이진 탐색 트리이다.
• 이진 탐색 트리를 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있다.

Binary Search Tree의 연산

탐색

• 비교한 결과가 같으면 탐색이 성공적으로 끝난다.
• 비교한 결과가 주어진 키 값이 루트 노드의 키 값보다 작으면 탐색은 이 루트 노드의 왼쪽 하위를 기준으로 다시 시작한다.
• 비교한 결과가 주어진 키 값이 루트 노드의 키 값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작한다.

삽입

• 이진 탐색 트리에 원소를 삽입하기 위해서는 먼저 탐색을 수행하는 것이 필요하다.
• 탐색에 실패한 위치가 새로운 노드를 삽입하는 위치가 된다.

삭제

1. 삭제하려는 노드가 단말 노드일 경우
   해당 노드만 삭제하면 된다.
2. 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우
   해당 노드를 삭제하고 서브 트리는 상위 노드에 붙여준다.
3. 삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우
   해당 노드와 가장 비슷한 값을 가진 노드를 해당 노드 위치로 가져온다.

왼쪽 서브 트리에서 가장 큰 값과 오른쪽 서브 트리에서 가장 작은 값에서 가장 비슷한 값을 찾을 수 있다.

1.  

Binary Search Tree의 성능

이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이 h에 비례한다.

최선

• 이진 트리가 균형적으로 생성되어 있는 경우
• O(log₂ n)

최악

• 한쪽으로 치우친 경사 이진 트리의 경우
• O(n)