C++ 기초 : tree (2)

---

이진 트리도 종류가 있습니다.

 

'완전 이진 트리'라는 것인데요.

자식 노드를 반드시 2개씩 모두 채워 나가는 트리입니다.

 

 

완전 이진 트리는 배열로 구현을 합니다.

 

아래 그림을 통해 완전 이진 트리를

어떻게 배열로 구현하는지 살펴 봅시다.

 

위와 같은 완전 이진 트리가 있습니다.

 

1번 노드는 해당 트리에서 루트 노드이며

2번과 3번 노드를 자식 노드를 데리고 있습니다.

 

2번 노드는 4와 5번을 자식 노드로,

3번 노드는 6과 7번을 자식 노드로 데리고 있습니다.

 

 

1번 노드를 배열의 0번 인덱스에 넣습니다.

 

이 상태에서 자식 노드인 2번 노드를 넣으려고 합니다.

 

첫 번째 자식 노드의 자리는 

2k + 1입니다.

여기서 k는 부모 노드가 있는 인덱스 번호이죠.

 

두 번째 자식 노드의 자리는 

2k + 2입니다.

 

즉 1번 노드의 첫 번째 자식 노드인 2번 노드의 자리는

2 * 0 + 1 = 1번 인덱스인 것입니다.

 

여기서 4번과 5번 노드는 어디에 들어가야 할까요?

 

4번 노드는 2번 노드의 첫 번째 자식 노드입니다.

2 * 1 + 1 = 3번 인덱스에 들어가야겠죠?

 

그리고 5번 노드는 2번 노드의 두 번째 자식 노드입니다.

2 * 1 + 2 = 4번 인덱스에 들어가야 하는 것이죠.

 

1번 노드의 두 번째 자식 노드인 3번 노드의 자리는

2 * 0 + 2 = 2번 인덱스입니다.

 

또한 3번 노드의 첫 번째 자식 노드인 6번 노드의 자리는

2 * 2 + 1 = 5번 인덱스이고

 

3번 노드의 두 번째 자식 노드인 7번 노드의 자리는

2 * 2 + 2 = 6번 인덱스이죠.

 

 

최종적으로 완전 이진 트리를 배열로 구현하면

 

위 그림과 같은 형태일 것입니다.

 

 

---

 

 

 

이진 트리 중에서도 탐색을 위한 이진 트리가 있습니다.

 

이를 '이진 탐색 트리 (BST, Binary Search Tree) '라고 합니다.

 

 

그러면 이진 탐색이 무엇인지 먼저 알아봐야겠죠?

 

숫자 1 ~ 1000이 있고 이를 100명의 사람이 

뽑았다고 가정해 봅시다.

 

그리고 뽑은 숫자 기준,

오름차순으로 100명의 사람을 정렬합니다.

 

이때 240을 뽑은 사람을 찾고자 합니다.

몇 번째 사람이 240을 뽑았는지 모르기 때문에

처음부터 한 명씩 검사해 나가야 합니다.

최악의 경우는 마지막에 서 있는 사람이 

240을 뽑은 경우겠죠.

 

그래서 조금 더 효율적으로 찾기 위해

50번째 사람에게 물어 봅니다.

이 사람이 648을 뽑았다고 합니다.

 

그러면 뒤에 있는 나머지 50명은 

648보다 더 큰 숫자를 뽑은 사람들이기

때문에 검사할 필요가 없겠죠?

 

이제 25번째 사람에게 물어 봅니다.

159를 뽑았다고 하네요.

 

그러면 24번째부터 그 앞에 있는 사람은

검사할 필요가 없고 26번째 ~ 49번째

사람만 검사하면 되겠죠.

 

다시 해당 범위 내 중간에 있는

사람에게 뽑은 숫자를 물어 보면 될 겁니다.

 

 

이런 식으로 이진 탐색은

데이터를 절반씩 덜어 내는 과정을

반복해 나가며 원하는 값을 찾는 것입니다.

 

중요한 점은 이진 탐색을 하기 위해서는

당연히 데이터가 정렬되어 있어야겠죠?

 

 

---

 

 

데이터가 정렬되어 있는 상태에서 

이진 탐색을 통해 발생할 수 있는

최악의 탐색 횟수는 log2의 N입니다.

 

만약 데이터가 1024개 있다고 합시다.

이 상태에서 특정 데이터를 찾고자 합니다.

vector나 list인 경우 발생할 수 있는

최악의 경우는 1024번째 공간이나 노드에 

찾고자 하는 데이터가 있어,

1024번의 탐색을 진행하는 경우겠죠?

 

근데 이진 탐색을 시도하면 

최악의 경우 탐색 횟수는

log2의 1024입니다. 계산하면 10, 즉 10번이죠.  

(계산하는 방법은 2가 1024가 되려면

몇 제곱을 해야 하는지 계산하면 됩니다.

만약 log10의 1000이면 3이겠죠!)

 

1024개의 데이터를 2로 나눠가면서

절반씩 제외해 나가면 최악의 경우라도

10번이면 원하는 데이터를 찾을 수 있다는 겁니다.

 

 

특히 탐색해야 하는 데이터의 개수가 많을수록

효율적입니다. 만약 데이터가

2의 32제곱(약 42억)개만큼 있다고 합시다.

 

여기서 데이터를 찾으려면 최대 42억 번의

탐색을 진행해야 하지만 이진 탐색을 하면 

log2의 2^32, 계산하면 32죠.

즉 42억 개의 데이터 중 원하는 값을

찾으려면 많아야 32번 정도 탐색하면 되는 겁니다.

 

물론 42억 개의 데이터가

정렬되어 있다는 가정하에 말이죠.

 

 

확실히 효율적이라는 것이 느껴집니다.

 

 

---

 

 

 

최악의 경우를 기준으로 효율을 표현하는

빅오 표기법(Big-O notation)은 계수를 다 무시합니다.

 

O(3 + N), O(1/2 * N)이어도 결국 O(N)짜리 알고리즘인 겁니다.

 

마찬가지로 이진 탐색을 빅오 표기법으로 나타내면

O(log2의 N)이지만 계수를 무시하기 때문에 

O(log의 N)짜리 알고리즘이라고 하는 겁니다.

( log2의 N은 log의 성질로 인해

logx의 N / log2의 N으로 표현할 수 있습니다.

이를 다시 표현하면 ( 1 / log2의 N ) * logx의 N 이죠.

( 1 / log2의 N )는 계수이므로 무시하고

임의의 밑인 x도 상관이 없으므로

logN 이라는 결과가 나오는 거죠.)

 

 

알고리즘 효율 순서를 따질 때

 

O( 1 ) > O( log의 N ) > O( N ) > O( N * log의 N ) > O( N^2 )

 

위 처럼 나열할 수 있습니다.

 

O( 1 )은 데이터의 개수가 늘어나도 

성능에 영향을 미치지 않아 가장 효율이 좋습니다.

 

O( N^2 )이 가장 효율이 좋지 않죠.

 

 

 

---

 

 

 

이진 탐색 트리는 트리는 트리인데

탐색이 가능한 트리이며

이진 트리로 구성된 트리임을 의미합니다.

 

 

이진 탐색 트리가 만들어지는 과정을

그림으로 표현하겠습니다.

 

 

처음에 데이터 100이 들어 왔습니다.

 

처음 들어온 데이터이므로

이것을 루트 노드로 지정합니다.

 

 

다음에는 50이라는 데이터가 들어 옵니다.

 

50은 100보다 작으므로 왼쪽에 둡니다.

(데이터를 오름차순으로 정렬한다고 가정했을 때 기준입니다.)

 

 

이번에는 데이터 300이 들어 왔고

 

이는 100보다 크므로 오른쪽에 위치하게 됩니다.

 

 

마지막으로 데이터 25가 들어 왔습니다.

 

100보다 작으므로 왼쪽에 위치하려고 했는데 

이미 50이라는 데이터가 있네요.

 

25는 50보다 작으므로 50으로부터 왼쪽에 

위치하게 됩니다.

 

 

이로써 데이터가 오름차순으로 잘 정렬되었습니다.

 

물론 vector나 list에서 pus_back 함수를 통해

데이터를 삽입할 때보다는

데이터 삽입 속도가 비효율적일 겁니다.

 

이렇게 데이터 삽입 과정에서 속도 측면에서 손해를 보지만,

정렬을 해 놓았으니 추후 데이터를 찾고자 할 때

이진 탐색을 통해 빠른 속도로 탐색이 가능한 것이죠.

 

 

따라서 단순히 데이터를 보관할 뿐만 아니라 

보관한 데이터를 빠르게 가져와야 하는 경우가

잦다면 탐색에 용이한 자료 구조를 고려해야겠죠.

 

 

 

강의 출처 : https://www.youtube.com/watch?v=PFc4g8mxOiI&list=PL4SIC1d_ab-aOxWPucn31NHkQvNPHK1D1&pp=iAQB

---