이진 탐색 트리

3.1 이진 탐색 트리 (BST)의 정의

이진 탐색 트리 (BST)는 다음과 같은 속성을 가진 이진 트리야:

• 어떤 노드에 대해서든 그 노드의 왼쪽 서브트리에는 그 노드의 키보다 작은 키만 포함되어 있어.
• 어떤 노드에 대해서든 그 노드의 오른쪽 서브트리에는 그 노드의 키보다 큰 키만 포함되어 있어.
• 각 노드의 양쪽 서브트리도 이진 탐색 트리야.

BST 예시:

BST는 Binary Search Tree의 줄임말이야. 기본적으로 데이터가 "트리" 구조로 조직되어서 굉장히 빠르게 검색할 수 있어. 트리 구조는 사실상 요소의 숨겨진/교활한 정렬이야.

중위 순회 (in-order traversal)

순회의 목표는 노드(또는 노드의 데이터, 용어의 문제야)를 특정 방식으로 리스트로 만드는 거야. 중위 순회는 트리의 루트가 왼쪽과 오른쪽 서브트리의 순회 결과 사이에 위치하게 해.

이진 탐색 트리의 속성(불평등에 관한 것, 이론 참고)과 함께 중위 순회는 이진 탐색 트리의 노드를 정렬된 리스트로 만들어줘 — 멋지지! 그렇게 순회된다고 정의된 트리는:

3.2 BST의 동작 원리와 속성

동작 원리:

• 데이터 조직화: BST는 데이터를 검색, 삽입, 삭제를 효율적으로 할 수 있도록 조직화해.
• 재귀적 구조: BST의 각 노드는 트리의 루트와 같은 규칙을 따르므로 구조가 재귀적이야.
• 균형: 최적의 성능을 보장하려면 BST가 균형을 이루어야 해, 즉 왼쪽과 오른쪽 서브트리의 높이가 대략 비슷해야 해.

BST의 속성:

• 정렬: 언제든 트리를 "in-order" 순서로 순회할 수 있어 (왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리) 모든 요소를 정렬된 순서로 얻기 위해서.
• 연산 시간:
  • 평균적으로 검색, 삽입, 삭제 연산 시간은 O(log n)이야, 여기서 n은 노드의 수야.
  • 최악의 경우 (트리가 균형을 이루지 못하면) 연산 시간은 O(n)에 도달할 수 있어.
• 고유 키: BST의 모든 키는 유일해야 정렬을 유지할 수 있어.

3.3 기본 연산

1. 삽입 (Insertion):

동작 원리:

• 루트 노드부터 시작해.
• 새 노드의 키를 현재 노드의 키와 비교해.
• 새로운 키가 더 작으면 왼쪽 서브트리로 가고, 크면 오른쪽으로 가.
• 새 노드를 삽입할 적절한 위치를 찾을 때까지 반복해 (왼쪽 또는 오른쪽 자식이 없을 때까지).

알고리즘:

1. 트리가 비어 있으면 새 노드를 루트 노드로 만들어.
2. 그렇지 않으면 적절한 위치를 찾아 새 노드를 재귀적으로 추가해.

2. 삭제 (Deletion):

동작 원리:

• 삭제할 노드를 찾아.
• 세 가지 경우를 고려해:
• 노드가 리프(자식이 없음)인 경우: 그냥 그 노드를 삭제해.
• 노드가 자식이 하나 있는 경우: 노드를 그 자식으로 교체해.
• 노드가 두 자식이 있는 경우: 오른쪽 서브트리에서 가장 작은 노드를 찾아 그것의 값을 삭제할 노드에 복사하고, 가장 작은 노드를 재귀적으로 오른쪽 서브트리에서 삭제해.

알고리즘:

1. 주어진 키를 가진 노드를 찾아.
2. 경우에 따라 적절한 삭제 및 노드 재분배를 수행해.

3. 검색 (Search):

동작 원리:

• 루트 노드부터 시작해.
• 찾고자 하는 노드의 키를 현재 노드의 키와 비교해.
• 키가 일치하면 노드를 반환해.
• 키가 더 작으면 왼쪽 서브트리로 가고, 크면 오른쪽으로 가.
• 찾고자 하는 키가 있는 노드를 찾거나 트리 끝에 도달할 때까지 반복해 (이 경우 노드를 찾지 못한거야).

알고리즘:

1. 트리가 비어 있거나 노드의 키가 찾고자 하는 키와 일치하면 노드를 반환해.
2. 찾고자 하는 노드의 키가 더 작다면 왼쪽 서브트리를 재귀적으로 검색해.
3. 찾고자 하는 노드의 키가 더 크다면 오른쪽 서브트리를 재귀적으로 검색해.

3.4 BST를 사용한 문제 해결 예제

1. 동적 집합에서 요소 검색

여러 숫자를 포함할 수 있는 집합을 유지하고, 새로운 요소를 추가하고 기존 요소를 삭제하며, 주어진 숫자가 집합에 있는지를 빠르게 검색할 수 있어야 해.

BST를 사용한 해결방안:

• 새로운 요소를 트리에 삽입해.
• 기존 요소를 삭제해.
• 트리에서 요소를 검색해.

사용 예제:

시스템에 등록된 사용자 목록을 유지하면서 사용자를 추가하거나 삭제하고, 시스템이 사용자가 등록되어 있는지를 빠르게 확인할 수 있어야 해.

2. 최소 및 최대 요소 찾기

데이터 집합에서 최소 및 최대 값을 빠르게 찾을 수 있어야 해.

BST를 사용한 해결방안:

• 최소 요소는 트리의 가장 왼쪽 노드에 있어.
• 최대 요소는 트리의 가장 오른쪽 노드에 있어.

사용 예제:

주식 가격을 추적하는 시스템에서 현재 시점의 최소 및 최대 가격을 빠르게 찾아야 해.

3. 표현식의 균형 검사

수학적 표현식이 주어졌을 때, 여는 괄호와 닫는 괄호의 개수를 균형있게 확인해야 해.

BST를 사용한 해결방안:

BST를 사용해 괄호 균형 검사 중간 상태를 저장해.

사용 예제:

코드를 구문 분석하고 컴파일할 때, 표현식에서 괄호가 올바르게 배치되었는지 확인해야 해.

4. 사전 구축

단어가 추가, 삭제되고 빠르게 찾을 수 있는 데이터를 저장할 수 있는 구조를 만들어야 해.

BST를 사용한 해결방안:

• 단어를 알파벳 순서대로 트리에 추가해.
• 단어를 키로 검색해.

사용 예제:

텍스트 자동 수정 시스템에서 단어를 빠르게 찾아 수정해야 해.