-Today's Learning Content-

• 이진트리와 이진탐색트리
• Heap(힙)

---

1. 이진트리

개념 정리

이진트리란 트리 구조의 일종으로, 각 노드가 최대 두개의 자식 노드(왼쪽, 오른쪽)를 가지는 계층적 데이터 구조이다.

1) 이진트리가 뭐야?

트리가 뭘까? 🌲 <- 이거?
아무래도 나무를 말하는 것은 아닐 것이다.

트리(Tree)는 계층적 데이터 구조의 종류로, 노드와 간선, 레벨 등으로 데이터 구조를 표현하는 방법이다.

그 중에서도 오늘은 이진트리(Binary Tree)에 대해 공부를 해보았다.

우선 트리는 위에서 말했듯이 노드, 가지, 레벨로 구성되어 있는데, 각각의 요소의 특징들은 아래와 같다.

1. 노드(Node)
   트리의 기본 구성 요소로, 데이터를 저장하고 다른 노드들과 연결된다
   • 루트(Root): 트리의 최상단 노드
   • 리프(Leaf): 자식 노드가 없는 마지막 노드
2. 간선(Edge)
   부모와 자식 노드를 연결하는 선이다. 가지(Branch)라고 부르기도 한다.
3. 높이(Level)
   트리구조에서 노드의 깊이를 나타내는 단위이다.
   최상위 노드인 루트는 Level0 이며, 최하위 노드는 Level(n)으로 Depth라고도 한다.

트리구조는 그렇다고 치고... 그렇다면 이진트리는 무엇일까?
간단히 모든 노드가 자식 노드를 최대 2개씩만 가질 수 있는 트리구조를 이진트리라고 한다. 이진트리는 부모 노드를 기준으로 간선을 오른쪽, 왼쪽으로 이어 자식 노드를 가질 수 있다.

2) 이진트리의 종류

이진트리는 다양한 종류가 있는데 대표적으로 아래와 같은 것들이 있다.

1. 완전 이진 트리
왼쪽 자식 노드부터 차례대로 채워지며, 마지막 레벨(Depth)을 제외한 모든 노드의 자식 노드가 채워져 있는 상태를 말한다.

2. 포화 이진 트리
모든 노드가 0개 혹은 2개의 자식 노드를 가지며, 모든 Leaf 노드의 Level이 똑같은 경우를 말한다.(즉, Leaf 노드 = Depth)

3. 정 이진 트리
모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리로 포화 이진 트리의 하위호환과 같은 느낌이다.

4. 편향 이진 트리
모든 노드들이 한 방향으로 편향된 트리를 말한다.

3) 이진 탐색 트리는 뭐야?

이진트리를 공부하다보니 이진 탐색 트리(BST)(BTS 아님)에 대한 내용도 나왔다. '탐색'이라는 단어가 들어간만큼 이진트리와 다른 점이 있는데, 그것은 이진트리에 조건을 추가한 것이다.

이진 탐색 트리의 조건

• 모든 노드가 자신의 왼쪽 자식 노드에는 자신보다 작은 값이 있어야 한다.
• 모든 노드가 자신의 오른쪽 자식 노드에는 자신보다 큰 값이 있어야 한다.
• 모든 노드의 데이터 값은 유일해야 한다(중복X)
• 모든 노드의 데이터 값은 항상 존재한다(nil X)

위의 조건을 모두 만족하는 이진트리를 이진 탐색 트리라고 한다.
아래의 코드는 이진 탐색 트리를 표현한 모습이다.

  ┌──37
 ┌──35
 │ └──nil
┌──30
│ └──nil
20
│ ┌──16
└──15
 └──12
 
 // nil 값은 무시

위의 코드에서 루트 노드는 20이고 루트 노드를 기준으로 작은 값은 왼쪽(아래), 큰 값은 오른쪽(위)으로 배치되어 있고, 루트 노드의 자식 노드들도 큰 값은 오른쪽, 작은 값은 왼쪽에 가지고 있는 모습을 확인할 수 있다.

4) 이진트리를 사용하는 이유?

그렇다면 이진트리는 왜 사용하는걸까??
그 이유는 다음과 같다.

1. 효율적인 데이터 관리
   • 탐색 속도 향샹: 이진 탐색 트리는 데이터를 정렬된 형태로 저장하여 탐색, 삽입, 삭제 작업을 평균 O(logn) 시간에 처리할 수 있다.
   • 빠른 우선순위 관리: 힙(Heap) 구조를 통해 최대값, 최솟값을 빠르게 찾아내거나 삭제할 수 있다.

2. 계층적 데이터 표현
   • 계층적 구조를 표현하는데 적합하여 파일 시스템, 디렉토리 구조, 조직도와 같은 데이터를 효과적으로 관리할 수 있다.

3. 다양한 문제 해결에 활용 가능
   • 압축: 허프만 코딩(Huffman Coding)과 같은 알고리즘에서 데이터 압축에 사용
   • 수식 계산: 표현식 트리(Expression Tree)를 통해 수학식 계산에 활용
   • 경로 검색: 그래프 문제에서 최단 경로나 경로를 표현하는데 활용 가능

4. 유연성
   • 다양한 형태로 확장 가능: 완전 이진트리, 포화 이진트리, 이진 탐색 트리 등 다양한 변형 구조를 통해 문제에 맞는 최적의 트리 구조를 설계 가능

5. 재귀적 성질로 구현 용이
   • 이진트리는 재귀적인 정의를 가지므로, 트리의 탐색 및 처리 로직을 간결하고 직관적으로 작성할 수 있다.

만약 선형 배열과 이진트리에서 데이터를 찾을 때, 선형 배열의 시간 복잡도는 O(n) 이고 이진트리에서는 O(logn)이기 때문에 더 빨리 처리할 수 있다고 한다.

이진트리의 단점도 있는데, 아래와 같다

1. 불균형 트리로 인한 성능 저하
   • 편향 이진트리(Skewed Binary Tree)가 되면 탐색, 삽입, 삭제의 시간 복잡도가 O(n)으로 증가하여 연결 리스트 수준의 비효율성을 보일 가능성
   • 해결책: 균형 잡힌 트리(예: AVL 트리, 레드-블랙 트리) 사용

2. 추가적인 저장 공간 필요
   • 각 노드에 왼쪽/오른쪽 자식 노드의 포인터(또는 참조)를 저장해야 하므로, 배열이나 리스트보다 메모리 소비가 크다
   • 특히 노드 수가 적거나 간단한 데이터를 관리할 경우 비효율적.

3. 복잡한 구현
   • 기본적인 삽입, 삭제, 탐색은 간단하지만, 균형 유지, 재구성, 회전 작업은 구현이 까다로울 수 있음
   • 특히 균형 트리(AVL, 레드-블랙 트리 등)는 구현 복잡도가 높음

4. 고정된 구조
   • 이진트리는 각 노드에 최대 2개의 자식만 허용하므로, 노드의 자식 수가 유동적인 경우에는 적합하지 않음
   • 해결책: k-ary 트리 또는 그래프 구조 사용

5. 순서에 의존
   • 데이터 삽입 순서에 따라 트리의 모양이 달라지고, 효율성에 영향을 줄 수 있음
     예: 정렬된 데이터를 삽입할 경우, 트리가 한쪽으로 치우쳐 비효율적

6. 노드 간 비교 연산 비용
   • 데이터를 탐색하거나 삽입/삭제할 때, 노드 간 비교 연산이 필요하므로, 값의 비교가 복잡하거나 연산 비용이 큰 경우 성능 저하가 발생할 가능성

7. 동적 크기 제약
   • 이진트리의 크기는 노드 추가/삭제에 따라 동적으로 변화하지만, 여전히 힙 기반 구조나 해시 테이블에 비해 공간 활용의 유연성이 떨어질 수 있음

결국 상황에 맞는 데이터 구조를 사용해야 하는 것이 옳다. 이진트리가 유리하다고 생각한다면 이진트리를, 그렇지 않은 경우 다른 데이터 구조를 사용하는 것을 고려해보자.

---

2. Heap(힙)

개념 정리

이진트리에서 Heap(힙)은 특정 조건을 만족하는 완전 이진트리(Complete Binary Tree)이다. 데이터 정렬이나 우선순위 관리에 자주 사용된다.

1) Heap의 종류

힙은 데이터에서 최대값과 최소값을 빠르게 얻고자 고안된 완전 이진트리이다. 어떻게 최대값과 최소값을 빠르게 얻을 수 있을까?

우선 힙은 최대힙과 최소힙의 2가지 종류를 가진다.

최대힙	최소힙

그림으로 보면 이해가 빠를 것이다.
최대힙은 트리의 최상단 노드인 루트가 항상 최대값을 가지는 트리 구조이다.
반대로 최소힙은 트리의 최상단 노드인 루트가 항상 최소값을 가지는 트리 구조이다.

즉, 최대힙은 특정 노드의 자식 노드의 값은 오른쪽 왼쪽 상관없이 항상 같거나 작아야한다. 최소힙은 그 반대인 경우이다.

이러한 특성 덕분에 최대힙의 루트는 항상 최대값이 되고, 최소힙의 루트는 항상 최소값이 된다.

2) Heap의 Index

힙은 완전 이진트리의 구조라고 하였다. 완전 이진트리의 특성상 항상 값은 왼쪽 자식 노드를 우선으로 채워지게 되는데, 때문에 힙의 노드는 Index 값을 가질 수 있다.

그리고 힙의 인덱스는 특징을 가지고 있는데, 자식 노드의 인덱스를 사용하여 부모 노드의 인덱스를 구할 수 있다는 점이다.
위의 사진에서 자식 노드를 사용하여 인덱스 4를 구하기 위해서는 어떻게 하면 될까?

방법은 간단하다. 자식노드의 인덱스를 2로 나누면 된다.

자식 노드 6의 인덱스 = 8
자식 노드 10의 인덱스 = 9

부모 노드 42의 인덱스 4 = 8 / 2,
부모 노드 42의 인덱스 4 = 9 / 2 // 인덱스는 정수형이기 때문에 4.5 = 4가 된다

그리고 부모 노드의 인덱스로 자식 노드의 인덱스도 구할 수 있는데, 먼저 왼쪽 자식 노드는 부모 노드의 인덱스에 2를 곱해주면 된다.

부모 노드 42의 인덱스 = 4

자식 노드 6의 인덱스 8 = 4 * 2

오른쪽 자식 노드는 부모 노드의 인덱스에 2를 곱한 후 1을 더해주면 된다.

부모 노드 42의 인덱스 = 4

자식 노드 10의 인덱스 9 = 4 * 2 + 1

힙은 이처럼 인덱스를 가질 수 있고, 서로의 인덱스 값을 구할 수 있는 특성 덕에 선형 데이터 구조처럼 활용할 수도 있다.

(위의 결과에서 Index0 값 30은 무시한다)

---

-Today's Lesson Review-

오늘은 데이터 구조의 종류인 이진 트리에 대해 공부하였다.
데이터 구조는 공부할 때마다 어려움을 느끼는 것 같다...
자료구조에 약한 것 같아서 더욱 노력을 해야겠다는 생각을 했지만,
쉽지 않은 것 같다...