이진 검색 트리(Binary Search Tree, BST)

이진 검색 트리(Binary Search Tree, BST)는 이진 트리의 한 종류로, 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값들을, 오른쪽 서브트리에는 해당 노드의 값보다 큰 값들을 저장하는 특징을 가진다.

다음은 이진 검색 트리의 특징이다:

1. 각 노드는 하나의 키(데이터)를 가지며, 이 키는 고유한 값을 가진다.
2. 왼쪽 서브트리 (하위 트리)의 모든 키는 루트의 키보다 작다.
3. 오른쪽 서브트리의 모든 키는 루트의 키보다 크다.
4. 왼쪽과 오른쪽 서브트리 각각이 이진 검색 트리여야 한다.

이러한 속성 덕분에 이진 검색 트리에서는 데이터 검색, 삽입, 삭제 등의 연산을 효율적으로 처리할 수 있다. 이진 검색 트리에서의 검색 연산은 트리의 높이에 비례하는 시간 복잡도를 가지므로, 균형 잡힌 트리에서는 로그 시간 복잡도를 가지게 된다. 하지만 트리가 한쪽으로 치우쳐져 있는 경우(즉, 균형이 잘 잡혀있지 않은 경우) 검색 성능이 저하될 수 있다. 이런 문제를 해결하기 위해 AVL 트리, 레드-블랙 트리 등의 자가 균형 이진 검색 트리가 개발되었다.

예를 들어, 아래의 숫자들을 이진 검색 트리에 넣으면, 8, 3, 10, 1, 6, 14, 4, 7, 13

이것을 이진 검색 트리로 구성하면 다음과 같다.

        8
       / \\
      3  10
     / \\   \\
    1   6   14
       / \\  /
      4   7 13

이 트리는 다음의 성질을 만족한다:

• 모든 노드는 유일한 값이다.
• 왼쪽 서브트리의 모든 노드의 값은 루트의 값보다 작다.
• 오른쪽 서브트리의 모든 노드의 값은 루트의 값보다 크다.
• 모든 서브트리도 이진 검색 트리이다.

이 이진 검색 트리에서 어떤 노드를 찾으려면 어떻게 해야 할까? 예를 들어 7을 찾는다고 가정해 보면.

• 먼저 루트에서 시작한다. 현재 노드가 8이고, 7은 8보다 작으므로 왼쪽 자식으로 이동한다.
• 현재 노드는 3이다. 7은 3보다 크므로 오른쪽 자식으로 이동한다.
• 현재 노드는 6이다. 7은 6보다 크므로 다시 오른쪽 자식으로 이동한다.
• 이제 현재 노드는 7입니다. 원하는 값을 찾았으므로 검색을 종료한다.

이진 검색 트리는 데이터를 효율적으로 관리하고 검색하는 데 매우 유용하다. 그러나 트리가 균형을 잃어버릴 경우 검색 성능이 떨어질 수 있으므로 이를 보완하기 위한 다양한 이진 검색 트리(예: AVL 트리, 레드-블랙 트리)가 존재한다.