이진탐색트리(BST)
이진탐색트리(Binary Search Tree, BST)는 이제까지 배운 자료구조 중에 단연 효과적이라고 느꼈다. 이 친구는 정말 단순하게 얘기하면, 저장할 값들을 순서를 정해서 저장한 이진트리이다. 좀 더 정확히 얘기하면 들어온 값을 부모 노드의 값과 비교하여 크면 오른쪽 노드, 작으면 왼쪽 노드에 저장하는 자료구조이다. 때문에 자료구조를 구성하는 과정에서 적지 않은 계산이 들어가야한다. 그럼에도 숱한 자료구조의 정글에서 BST가 월드스타로 우뚝 선 이유을 알아보자.
이진탐색트리의 장점은 무엇일까. 바로 특정값을 찾기 위해 탐색해야하는 정점의 수가 트리의 높이 값과 같다는 점이다. 트리의 높이 값h는 log2(N+1)-1을 소수점 첫째자리에서 올림한 값이다. 때문에 탐색의 시간복잡도가 O(log n)인 셈이다.
이진탐색트리의 균형
이진탐색트리는 트리의 루트의 값이 어느 것으로 정해지는지에 따라, 노드의 양 쪽에 저장되는 값의 개수가 다르다. 정말 치우친 값을 루트로하면, 한쪽에만 모든 값이 저장되며, 이 현상이 모든 자식노드에 적용된다면 사실상 연결리스트의 형태를 띈다. 이 때는 특유의 낮은 탐색 시간복잡도가 O(n)으로 돌아오기 때문에, 매우 치명적이다. 때문에 적절한 루트를 선정하는 것이 중요하며, 이를 보완하기 위하여 자가균형이진탐색트리(Self-Balancing Binary Search Tree)를 활용하기도 한다.
이진탐색트리 구현
이진탐색트리를 파이썬으로 구현해보자.
# 트리노드 선언
class TreeNode:
def __self__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
# 함수선언
def sorted_array_to_bst(lst):
# lst값이 없으면, 반환 없이 함수종료
if not lst:
return None
# 정렬된 리스트의 중심 값을 루트로 지정하기 위해 인덱스 값 저장
mid = len(lst)//2
# 노드 생성 및 저장
node = TreeNode(lst[mid])
# 현재 노드를 기준으로 배열의 앞 쪽을 잘라서, 해당 배열을 인자로 받는 함수를 재귀호출
# 동시에 현재 노드의 left에 저장
node.left = sorted_array_to_bst(lst[:mid])
# 현재 노드를 기준으로 배열의 뒤 쪽을 잘라서, 해당 배열을 인자로 받는 함수를 재귀호출
# 동시에 현재 노드의 right에 저장
node.right = sorted_array_to_bst(lst[mid+1:])
# 루트 값 반환
return node재귀함수를 통한, 이진탐색트리의 구현코드다. 배열을 정렬한 뒤 가운데 값을 루트 값으로 정하며 매 자식노드들 역시 자른 배열의 중심값을 가져오기 때문에, 균형이 보장되는 구현코드이기도 하다.
BST가 월드스타인 이유
BST는 사실 구현함수와 탐색함수를 한 세트로 생각한다면, 그다지 효율을 체감할 수 없다. 하지만 한번 구축한 자료구조를 지속적으로 사용하면 사용할 수록 특유의 효율을 만들어 낼 수 있다. 탐색을 여러번 해야한다면, 이진탐색트리 형태가 매우 효과적이라는 것이다.
게다가 이 작업은 연속적으로 이루어질 필요가 없다는 장점도 가지고 있다. 시간복잡도는 사실 결국 작업의 시작부터 끝까지의 단위 시간에 적용되기 때문에, 분할해서 작업할 수 있는 것은 큰 장점이다. 마치, 남는 전기가 많은 밤에 충전을 하는 전기차가 휘발유 차량을 밀어내는 것처럼, 연산할 여유가 있을 때 트리를 만들어 놓는다면 사실상 탐색에 대한 시간복잡도가 O(log n)으로 줄어든다고 볼 수 있다.
마무리
BTS 노래처럼 자주 듣다보면 익숙해지겠지
