[자료구조] 트리

✍️ 트리

트리(Tree)란? 계층적인 구조를 나타내는 자료구조

트리는 부모-자식 관계의 노드들로 이루어져있다.

트리의 용어

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

다음은 트리의 예시이다.

트리의 종류로는 이진 트리와 일반 트리가 있는데 뭐가 다른지 살펴보자.

✍️ 이진 트리

이진 트리(binary tree)란? 모든 노드가 2개 이하의 서브 트리를 가지고 있는 트리
서브 트리는 공집합일 수 있다.

이진 트리 vs 일반 트리

• 이진 트리의 모든 노드는 차수가 2 이하이다.
• 이진 트리는 노드를 하나도 갖지 않을 수 있다.
• 이진 트리에는 서브 트리간의 순서가 존재한다.(일반적으로 왼쪽 -> 오른쪽)

이진 트리의 성질

ceiling을 하는 이유? 높이가 소수로 떨어지면 안되므로

이진 트리의 종류로는

• 포화 이진 트리(full binary tree)
• 완전 이진 트리(complete binary tree)
• 기타 이진 트리
  가 있다.
  

🔍 포화 이진 트리(full binary tree)

포화 이진 트리(full binary tree)란? 트리의 각 레벨에 노드가 꽉 차있는 이진트리를 의미

🔍 완전 이진 트리(complete binary tree)

완전 이진 트리(complete binary tree)란? 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리

모든 포화 이진 트리는 완전 이진 트리이다.

🔍 이진 트리

이진 트리를 표현하는 방법으로는

• 배열을 이용하는 방법
• 포인터를 이용하는 방법
  이 있다.
  
  배열을 인덱스 1부터 채웠을 때 장점? 부모의 2배하면 왼쪽 노드이고 2배+1하면 오른쪽 노드이다. 즉, 왼쪽 노드는 2i, 오른쪽 노드는 2i + 1이다.

부모와 자식 인덱스 관계

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

3가지의 기본적인 순회 방법

• 전위순회(preorder traversal): VLR
  자손 노드보다 루트 노드를 먼저 방문
• 중위순회(inorder traversal): LVR
  왼쪽 자손, 루트, 오른쪽 자손 순으로 방문
• 후위순회(postorder traversal): LRV
  루트 노드보다 자손을 먼저 방문

레벨 순회(level traversal)

• 각 노드를 레벨 순으로 검사하는 순회 방법
• 레벨 순회는 원형 큐를 사용한다.

🔍 트리의 응용: 수식트리

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

non leaf node는 연산자(operator), leaf node는 피연산자(operand)이다.
순회 방법에 따라 다르지만 우리는 후위순회를 사용한다.

✍️ 스레드 이진 트리

스레드 이진 트리란? 이진트리의 NULL 링크를 이용하여 순환 호출 없이도 트리의 노드들을 순회
NULL 링크에 중위 순회 시에 후속 노드인 중위 후속자(inorder successor)를 저장시켜 놓은 트리가 스레드 이진 트리(threaded binary tree)이다.

놀고 있는 NULL 링크를 이용하지만 삽입, 삭제가 빈번하게 일어나면 안좋다.

✍️ 이진 탐색 트리

이진 탐색 트리란? 탐색 작업을 효율적으로 하기 위한 자료구조

모든 원소는 서로 다른 유일한 Key를 갖는다.
이진 탐색을 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있다.
key(왼쪽서브트리) ≤ key(루트노드) ≤ key(오른쪽서브트리)

이진 탐색 트리에서의 탐색 연산

• 비교한 결과가 같으면 탐색이 성공적으로 끝난다.
• 주어진 키 값이 노드의 키 값보다 작으면 노드의 왼쪽으로 탐색을 진행한다.
• 주어진 키 값이 노드의 키 값보다 크면 노드의 오른쪽으로 탐색을 진행한다.

탐색을 하는 방법으로는 순환적 방법과 반복적 방법이 있다.

이진 탐색 트리에서의 삽입 연산

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

예제에서 당연히 9가 없겠지만 9를 탐색하고 탐색이 끝난 자리에 9를 삽입한다.

이진 탐색 트리에서의 삭제 연산
CASE 1: 삭제하려는 노드가 단말 노드일 경우
삭제 노드의 부모 노드를 찾아서 연결을 끊는다.

CASE 2: 삭제하려는 노드가 하나의 서브트리만 갖고 있는 경우
삭제 노드는 삭제하고 그 노드의 서브 트리는 부모 노드에 연결한다.

CASE 3: 삭제하려는 노드가 두 개의 서브트리를 갖고 있는 경우
삭제 노드와 가장 비슷한 값을 가진 노드를 삭제 노드 위치로 이동한다. 왼쪽 서브트리에서 가장 큰 애와 오른쪽 서브트리에서 가장 작은 애 둘 중 하나를 그 자리에 놓는다.

이진 탐색 트리의 성능은 최선의 경우 O(logn)이고 최악의 경우 O(n)이다.

✍️ 힙(heap)

힙(heap)이란? 노드의 키들이 최대 힙 기준으로 Key(부모노드) ≥ Key(자식노드) 식을 만족하는 완전 이진 트리

힙은 Key 값의 중복을 허용하는데 힙의 종류는 다음과 같다.

• 최대 히프(max heap): 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  key(부모노드) ≥ Key(자식노드)
  
• 최소 히프(min heap): 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  Key(부모노드) ≤ Key(자식노드)
  

힙에서의 삽입
힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입한다.
삽입 후에 새로운 노드를 부모 노드들과 교환하여 힙의 성질을 만족시킨다.

힙에서의 삭제
최대 히프에서의 삭제는 가장 큰 키 값을 가진 노드 즉, 루트 노드를 삭제한다.
루트 노드를 삭제 -> 마지막 노드를 루트 노드로 이동 -> 루트에서부터 단말 노드까지 경로에 있는 노드들을 교환하여 힙의 성질을 만족