트리의 계층 구조와 기본 개념부터 힙에서 우선순위를 다루는 구조까지 개념을 이해하고, 차이점을 알아보자.

트리란 무엇인가?

트리는 나무를 뒤집어 놓은 모양과 같은 구조를 가지고 있다.

왼쪽의 실제 나무를 보면 뿌리가 아래에 있고 가지가 위로 뻗어나간다.
자료구조에서는 트리를 뒤집어서, 루트가 위에 있고 아래로 뻗어나가는 형태이다.

우리 주변에서 트리와 같은 구조를 예로 들면 아래와 같은 개념이 존재한다.

• 회사 조직도: CEO 아래에 임원, 임원 아래에 팀장, 팀장 아래에 팀원
• 컴퓨터 폴더 구조: C드라이브 안에 Users, Users 안에 Documents
• 가계도: 조부모, 부모, 자식 순서

이렇게 계층이 있는 데이터를 표현할 때 트리를 사용한다.

트리를 해부 해보자

트리의 각 부분을 뭐라고 부르는지 용어를 정리해보았다.
회사 조직도 예시로 한 트리구조 이미지를 AI로 생성했다.

• 루트(Root): 최상위 노드, 트리의 시작점이다.
• 부모(Parent): 특정 노드의 상위 단계 노드, CTO는 Dev1, Dev2의 부모노드인 셈이다.
• 자식(Child): 부모노드의 아래에 연결된 노드, Dev1, Dev2는 CTO의 자식노드이다.
• 리프(Leaf): 자식이 없는 말단 노드, Dev1, Dev2는 자식이기도 하면서 리프이기도하다.
• 깊이(Depth): 루트부터 특정 노드까지의 거리, CEO에서 Dev1까지 깊이는 2 / CEO에서 CTO까지는 1
• 높이(Height): 트리에서 가장 긴 경로의 길이, 이미지 상의 트리는 높이가 2이다.

이진 트리 규칙

이진 트리의 핵심은 각 노드가 최대 2개의 자식만 가질 수 있다는 것이다.

왼쪽의 일반 트리를 보면 자식이 3개, 4개 붙어있는 것에 비해
오른쪽 이진 트리는 자식이 무조건 최대 2개이다.

이진 트리는 탐색과 정렬에 효율적으로 사용할 수 있다.
컴퓨터가 0과 1, Yes와 No 이진 논리로 작동하기 때문이다.

이진 트리에 규칙 추가하기

이진 트리에 규칙을 하나만 더 추가하면 BST, 즉 이진 탐색 트리가 된다.
바로, 각 노드에 할당된 값의 크기가 순서를 갖게 된다는 것이다.

이미지를 보면 루트 노드의 값은 8이다.
8을 기준으로 왼쪽 서브트리에는 3, 1, 6이 있는데 전부 8보다 '작음'을 알 수 있다.
오른쪽에는 10과 14가 배치되어있고 전부 8보다 '큼'을 알 수 있다.

이 규칙은 모든 노드에 전체적으로 성립된다.
루트를 기준으로 트리 전체에도 적용되며, 각각의 서브 트리에도 적용된다.

BTS를 쓰면 뭐가 좋은거지?

일반 배열에서 선형탐색 방식으로 '6'이란 값을 찾아보자.
선형탐색은 아래와 같이 1부터 시작해서 하나씩 값을 비교해야 값을 찾을 수 있다.

반면, BST 탐색은 루트에서부터 타고 내려가면서 값을 찾아낸다.
루트 노드의 값인 8보다 6은 작으니까 작은 숫자가 배치된 왼쪽 줄기를 타고 내려간다.
3번 노드에 도착하여 6과 비교했을 때 6이 더 큰 숫자이니 오른쪽 줄기를 타고 내려간다.

이렇게 매 단계마다 절반의 데이터를 제외하기 때문에,
데이터가 100만 개여도 절반씩 비교하고 제외하면 선형탐색에 비해 빠르게 값을 찾을 수 있다.

힙이란 무엇인가?

힙은 우선순위가 가장 높은 요소를 빠르게 꺼내기 위해 고안된 완전 이진 트리이다.

완전 이진 트리라는 개념은, 2가지 특징이 있다.

1. 윗 레벨부터 채운다.
2. 같은 레벨에서는 왼쪽부터 채운다.

최소 힙 이미지를 기준으로보면, 1번 노드의 자식으로 2번만 존재할 수는 있지만
2번 없이 3번만 존재할 순 없다. 왼쪽부터 채운다는 특징 때문이다.

2번 노드가 존재하고 3번 노드가 없는 상태에서 4번이나 5번 노드가 달릴 수도 없다.
윗쪽 레벨부터 채워야되기 때문에 반드시 3번까지 채우고 나서 4번과 5번이 채워질 수 있다.

우선순위 전문가 힙

우선 순위는 두 종류가 있다.

• 최소 힙(Min Heap): 부모가 자식보다 작거나 같다. 루트는 항상 최솟값이다.
• 최대 힙(Max Heap): 부모가 자식보다 크거나 같다. 루트는 항상 최댓값이다.

BST와는 다르게 형제 노드끼리의 순서는 상관없다.
오직 부모-자식 관계만 신경쓰면 된다.

힙의 작동 원리

INSERT

최소 힙에 '0'을 추가해보자.

1. 완전 이진 트리 특징인 '위/왼쪽 부터 채운다'를 따라서 왼쪽 아래에 0이 추가된다.
2. 0이 부모인 4보다 작다. 최소 힙 규칙을 위반했기 때문에 둘의 자리를 교환해야한다.
3. 다시 2와 비교했을 때 0이 작기 때문에 한 단계 위로 올라가고,
4. 최종 1과 비교하여 0이 한단계 더 올라가게된다.

결국 C와 같은 형태로 최소 힙의 INSERT가 마무리가 된다.
이와 같은 과정을 거품이 떠오르는 행태와 같아서 BubbleUp 이라고 칭한다.

Extract

이번엔 최솟값 '1'을 꺼내보자.

1. 루트에 있는 1을 제거하면, 마지막 노드인 7을 루트로 옮긴다.
2. 루트에는 최솟값이 와야하니, 루트 값인 7과 그 자식들의 값을 비교하여
   2와 3 중 더 작은 자식인 2를 올리고 7이 내려간다.
3. 다시 내려온 7의 자식들 4와 5를 비교하여 더 작은 값이 4와 자리를 바꾼다.

최솟값 제거를 완료하면 C와 같은 형태가 되는 것을 알 수 있다.
이렇게 하나씩 값을 비교하면서 자리를 찾아가는 방식을 Trickle Down 이라고 칭한다.

힙이 값을 저장하는 방식

힙은 배열 형태로 값을 저장한다. 메모리 효율이 좋기 때문이다.
부모 자식 간의 관계를 계산해서 인덱스를 구하는 방법을 알아보자.

자식 인덱스를 구할 때 i의 값으로 부모의 인덱스 값이 쓰인다.

• 왼쪽 자식 인덱스: 2 * i + 1
• 오른쪽 자식 인덱스: 2 * i + 2

루트에 있는 값은 0번 인덱스에 저장되고,
상위 자식 인덱스부터 순차적으로 계산식이 적용하여 인덱스를 구할 수 있다.

• 부모 인덱스: (i - 1) / 2

부모 인덱스를 구할 땐 i의 값으로 자식의 인덱스 값이 쓰인다.
나머지를 제외한 정수값만 쓰이게 된다.

BST VS 힙

BST와 힙, 둘 다 이진 트리인데 어떤 점이 다른걸까?

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드	부모노드 < 자식 노드

BST

BST는 가로로 정렬된 구조이다.
앞서 언급했던 것 처럼 특정 값을 탐색하는데 유리하다.
자식노드가 가진 값의 규칙이 적용되어있어서,
절반씩 소거해가며 원하는 값을 찾는 속도가 빠르기 때문이다.

힙

힙은 세로로 정렬된 구조이다.
최소 힙, 최대 힙과 같이 값의 크기가 부모 자식 관계로 정렬되어있기 때문에,
실시간 검색어 랭킹, 지도에서 최단 경로 찾기와 같이 제품에 우선순위를 적용할 수 있다.