이진 탐색 트리 (binary search tree)

이진 탐색 트리

이진 탐색 트리(Binary Search Tree) 라는 것도 있다. 이진 탐색이란 미리 큰 순으로 정렬된 자료구조에서 무작위의 데이터를 뽑아 검색 데이터와 비교해, 작다면 왼쪽 영역의 가운데 값, 크다면 오른쪽 영역의 가운데 값과 비교해나가며 검색하는 방식이다. 두 영역으로 나눈다고 해서 이진 검색이라고 하는 것 같다 :).

 

이진탐색트리는 이진 탐색을 위한 트리다. 루트노드를 포함해서, 부모 노드가 왼쪽에 작은 값의 자식을, 오른쪽에는 큰 값의 자식을 가지는 구조다. 검색할 때 부모 노드를 보고 부모보다 작은 값을 찾고 있다면 왼쪽 서브트리를 탐색하고 큰 값을 찾고 있다면 오른쪽 서브트리를 탐색하면 된다. 각 단계마다 해야되는 작업이 반절로 줄어드니 O(log n) 의 시간복잡도를 가진다.

 

이진 트리는 왼쪽 서브트리와 오른쪽 서브트리의 균형이 맞아야 성능이 보장된다. 한쪽으로 너무 치우쳐져 있으면 O(n) 의 성능을 보인다... 이런 이슈로 이진트리를 균형잡히게 하도록 만든 트리가 있는데, 바로 👉 AVL tree 와 Red-Black tree 이다.