17 Jan 2020

Sanjoy Dasgupta가 저술한 책인 Algorithms과 이기창님의 블로그를 참고하였다.

1-1. Binary Search(이진탐색)

Binary Search Tree(이하 BST)를 이해하기 위해서는 먼저 Binary Search에 대해 알아야한다.

Binary Search : 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 탐색 알고리즘. 중앙값보다 크면 오른쪽, 작으면 왼쪽으로 재귀적으로 탐색한다.

• 정렬된 리스트에만 사용 가능
• 탐색이 반복될 때마다 탐색 대상이 되는 데이터 수가 절반이 되므로 속도가 빠름

cf) Binary Search와 K-ary Search

둘 다 정렬된 리스트에서 특정값의 위치를 탐색하는 알고리즘이다. 하지만 Binary Search의 경우 중앙값을 대상으로 탐색값이 이 값보다 크냐 작냐에 따라 왼쪽, 오른쪽으로 움직이면 되는 반면, K-ary Search는 $k$ 개의 그룹 중 특정값이 어느 그룹인지 정해야하기 위해 같은 레벨에서 또 다시 비교를 해야한다. 따라서 시간복잡도의 경우 Binary Search가 $O(\log_2n)$, k-ary Search가 $O(\log_kn)$으로, Binary Search가 더 효율적인 것을 알 수 있다.

1-2. Binary Search(이진탐색)의 수행 과정

Binary Search는 Quick Sort와 그 방식이 약간 유사하다. 퀵 소트에서 pivot을 선정해 pivot의 앞 뒤로 리스트를 나누었던 것처럼, Binary Search도 중앙값을 기준으로 리스트를 앞, 뒤로 나누며 원하는 값을 탐색한다. 위의 그림을 예로 하여, 리스트에서 7을 찾아보자

1. 리스트의 중앙값을 찾아 탐색값과 비교
2. if 중앙값 > 탐색값 : 중앙값보다 큰 값들을 탐색 대상에서 제외
3. if 중앙값 < 탐색값 : 중앙값보다 작은 값들을 탐색 대상에서 제외
4. 2, 3 중 한 과정을 거쳐 남은 탐색 대상을 대상으로 1~3 과정 반복

따라서 위 그림에서는 중앙값(14) > 탐색값(7)이므로, 중앙값(14)보다 큰 18, … , 71을 제외한 뒤 다시 1, … , 14를 대상으로 또 중앙값(6)과 탐색값(7)을 비교하며 Binary Search를 진행하는 것이다. 그렇게 되면 최종적으로 중앙값 = 탐색값이 되어 탐색하고자 하는 값을 찾을 수 있다.

1-3. Binary Search(이진탐색)의 시간복잡도

데이터의 총 개수가 $n$개일 때, 이 데이터들은 Binary Search를 거치며 $n/2, n/4 …$로 개수가 줄어들게 된다. 따라서 시행횟수를 $k$라고 한다면, 최종적으로 Binary Search를 마쳤을 때 남은 데이터의 개수는 $n(\frac 1 2)^k$이 된다. 그리고 이 값은 중앙값 = 탐색값이므로 1이라고 할 수 있다. 따라서 $n(\frac 1 2)^k \approx 1$이므로 양변에 $2^k$를 곱해주면 $n \approx 2^k$가 된다. 즉, $k \approx log_2 n$이고, $k$는 시행 횟수이므로 시간복잡도는 $O(\log_2n)$이다.

2-1. Binary Search Tree(BST. 이진탐색트리)

BST : Binary Search와 연결리스트를 결합한 자료구조. Binary Search를 기반으로 연결리스트를 이용하여 원하는 값을 탐색하는 알고리즘

Binary Search의 경우 시간복잡도가 $O(\log_2n)$으로 빠르지만 자료의 입력, 삭제가 불가능

연결리스트의 경우 자료의 입력, 삭제가 가능하지만 시간복잡도가 $O(n)$으로 느림

따라서 이 두 놈들의 장점을 서로 보완하며 탄생된 것이 바로 BST이다.

• 값의 크기가 왼쪽서브트리 $\leq$ 노드 $\leq$ 오른쪽서브트리이다. 이는 앞서 공부한 Tree Traversal 방식 중 Inorder(중위순회)방식을 사용하고 있는 것을 알 수 있다.

  cf) Max Heap or Min Heap : 부모노드가 자식보다 크거나 or 작다.

• 모든 노드의 Key값은 유일하다. 즉, 중복된 노드가 없어야한다.

2-2. Binary Search Tree(이진탐색트리)의 수행과정

Binary Search의 경우 리스트의 중앙값을 찾아 이를 기준으로 앞, 뒤를 나누는 과정을 반복하며 원하는 값을 탐색했다. BST도 이와 유사하다.

1. 루트노드의 값와 탐색값을 비교
2. if 루트노드 > 탐색값 : 왼쪽 서브트리로 이동
3. if 루트노드 < 탐색값 : 오른쪽 서브트리로 이동
4. 2, 3 중 한 과정을 거쳐 남은 트리를 대상으로 1~3 과정 반복

따라서 위 그림의 경우 내가 12를 찾고 싶다고 하자. 루트노드의 값이 18이므로 18 < 12이다. 따라서 왼쪽 서브트리로 이동한다. 그 다음 루트노드인 7과 비교하자. 7 < 12이다. 따라서 오른쪽 서브트리로 이동한다. 그 다음은? 루트노드 = 탐색값이다. 탐색이 끝났다.

2-3. Binary Serach Tree(이진탐색트리)의 시간복잡도

BST는 Binary Search의 특성인 탐색과 연결리스트의 특성인 삽입, 삭제가 모두 가능하다. 따라서 시간복잡도도 위의 경우를 모두 고려해야한다. 먼저 트리의 높이를 $h$라고 하자.

• 탐색

  이는 앞서 2-2에서 말한 수행 과정과 같다. 이 경우 탐색 알고리즘을 수행하는 데 소요되는 시간은 트리의 높이에 비례한다. 따라서 시간복잡도는 $O(h)$이다.

• 삽입

  새로운 데이터를 트리에 삽입할 수 있다. 새로운 데이터를 삽입하고자 할 때, 가장 먼저 중복된 데이터가 있는지 탐색이 이루어진다. 예를 들어보자.

  

  6을 삽입한다고 하자. 먼저 루트노드 7과 비교해 6이 더 작으므로 왼쪽 서브트리로 이동한다. 그 다음 3보다는 크므로 오른쪽 서브트리로 이동하고, 5보다도 크므로 오른쪽 서브트리로 이동한다. 이 때, 더이상 찾을 노드가 없으므로 NULL(중복된 데이터가 없음)이라는 결과가 나오게 된다. 따라서 NULL이 나온 그 위치에 6이 삽입된다. BST의 Inorder 트리순회 방식의 특성을 깨트리지 않기 위해, 새로운 데이터는 항상 잎새노드로 삽입되는 것이다.

  삽입 알고리즘을 수행하는 데 소요되는 시간은 중복 여부를 체크하는 과정에서 탐색 알고리즘과 소요시간이 같으므로 $O(h)$이고, 삽입하는데 걸리는 시간은 $O(1)$이므로 시간복잡도는 $O(h)$이다.

• 삭제

  삭제 알고리즘을 수행할 때는 다음의 경우를 고려해야한다.

  (1) 삭제하려는 노드가 잎새노드일 경우(자식노드가 없는 경우)

  (2) 삭제하려는 노드가 하나의 서브트리만 갖는 경우

  (3) 삭제하려는 노드가 두 개의 서브트리를 모두 갖고 있는 경우

  위 경우들을 하나씩 살펴보자.

  
  

  (1) 삭제하려는 노드가 잎새노드일 경우(자식노드가 없는 경우)

  

  위 그림에서 22, 28, 42를 삭제할 때이다.

  이 경우에는 그냥 없애면 된다. 자식 노드가 없기 때문에 그냥 다짜고짜 삭제해도 트리의 특성을 깨트리지 않기 때문이다.

  (2) 삭제하려는 노드가 하나의 서브트리만 갖는 경우

  

  위 그림에서 20을 삭제할 때이다.

  이 경우에는 해당 노드를 지우고, 해당 노드의 부모노드와 자식노드를 연결해주면 된다. 따라서 20을 삭제했다면, 20의 부모노드인 30과 자식노드인 25를 서로 연결해준다. 이렇게 마음 편하게 연결할 수 있는 이유는 부모노드는 자기보다 크고, 자식노드는 자기보다 분명히 작기 때문에 트리의 특성을 깨트리지 않기 때문이다.

  (3) 삭제하려는 노드가 두 개의 서브트리를 모두 갖고 있는 경우

  

  위 그림에서 16을 삭제할 때이다.

  이 경우에는 해당 노드의 왼쪽 서브트리에 있는 값 중 가장 큰 값, 혹은 오른쪽 서브트리에 있는 값 중 가장 작은 값을 해당 노드의 자리에 채워주면 된다(이 값들을 Successor라고 한다). 따라서 16을 삭제했다면, 오른쪽 서브트리에 있는 값 중 최솟값인 20을 그 자리에 채워준다.

  이때, 20을 해당 노드의 자리에 채워준다는 것은 달리 말하면 20을 삭제하는 것이다. 따라서 이 경우 다시 (1), (2) 중 하나의 경우의 과정을 거쳐야한다.

  위 그림에서 20은 (2)의 경우처럼 하나의 서브트리만 갖고 있기 때문에 20의 부모노드 30과 자식노드 25를 이어준다. 만약 (1)의 경우처럼 20이 잎새노드라면 그냥 지워주면 된다.

  정리하면 다음과 같다.

  1. 삭제되는 노드를 찾는다
  2. 삭제되는 노드의 왼쪽서브트리의 최소값과 오른쪽서브트리의 최대값을 찾는다.
  3. 2에서 찾은 값 중 한 값을 삭제해 삭제되는 노드의 그 자리에 채워준다.
  4. 2에서 찾은 값 중 삭제되는 값을 대상으로 위의 (1)과 (2) 중 한 과정을 진행한다.

  
  

  시간복잡도는 항상 최악의 경우를 대상으로 하기 때문에, 삭제 알고리즘의 경우 가장 연산량이 많고 복잡한 (3)이 시간복잡도의 대상이다.

  먼저 삭제되는 노드의 레벨이 $d$라고 하자. 1번 과정에서 삭제되는 노드를 찾기 위해서는 $d$만큼의 시간이 걸린다. 이후 2번 과정을 수행하기 위해서는 서브트리의 높이($h - d$)만큼의 시간이 걸린다.

  

  (예를 들어, 위의 트리의 높이는 5이고, 삭제 되는 노드가 30이라고 하면 $d = 3$이다. 따라서 서브트리의 높이는 2이다.)

  그 다음, 3번 과정은 그냥 채워주는 것이므로 $O(1)$의 시간이 걸리고, 4번 과정은 만약 땜빵 노드가 리프노드면 그냥 삭제하니까 $O(1)$, 하나의 서브트리를 갖고 있으면 자기 부모노드랑 자식노드 그냥 이어주면 되니까 $O(1)$이다. 따라서 총 소요되는 시간은 $O(d + h - d + 1 + 1)$이고 상수는 무시하므로 삭제 알고리즘의 시간복잡도는 $O(h)$이다.

따라서 Best, Average-Case의 시간복잡도는 $O(h)$인 것을 알 수 있다.

하지만 Worst-Case의 경우 이야기가 달라진다. 지금까지 예를 든 Tree는 모두 노드가 두개의 자식트리를 그나마 균형적으로 갖는 것들이었다. 하지만 한쪽으로만 자식노드가 가져진다면 어떻게 될까?

이것이 그 예이다. 트리가 균형을 이루지 않고 한쪽으로만 쏠리는 것을 알 수 있다. 심지어 이것은 그나마 양호한 것이고, 만약 노드의 값이 2, 5, 7, 9, 13, …과 같이 한쪽으로만 커진다면 $n$개의 노드가 한쪽으로만 늘어지는 트리가 되어 높이가 $n$이 되버린다. 따라서 이 경우 Sequential Search와 같이 시간복잡도가 $O(n)$이 된다.

cf) Sequential Search(순차탐색) : 리스트 내에서 데이터를 탐색값과 순차적으로 비교해가며 탐색값을 찾는 것

Binary Search와 연결리스트의 장점을 모두 갖다붙였음에도 불구하고 BST에는 위와 같은 단점이 있다. 따라서 이 Worst-Case를 해결하기 위해서는 트리가 한 쪽으로만 자라지 않도록 Balance를 맞춰주어야 한다. 이를 위해 나온 것이 AVL Tree와 B-Tree이다. 이들은 이어서 공부할 것이다.