이진 탐색 트리 (Binary Search Tree, BST)의 주요 성질 정리

1. 기본 정의

• BST는 왼쪽 자식 노드 < 현재 노드 < 오른쪽 자식 노드의 조건을 만족하는 이진 트리이다.
• 모든 서브트리도 BST이어야 한다.

---

2. 중위 순회의 특징

• BST를 중위 순회(in-order) 하면 오름차순으로 정렬된 노드 값을 얻을 수 있다.

# 중위 순회 코드
def inorder(node):
    if not node:
        return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

---

3. 역중위 순회 (Reverse In-order)

• 오른쪽 → 루트 → 왼쪽 순으로 탐색
• 내림차순 순서로 노드를 방문함
• 예시: Greater Tree 변환에서 사용됨

# Greater Tree 변환 예시
acc = 0

def reverse_inorder(node):
    nonlocal acc
    if not node:
        return
    reverse_inorder(node.right)
    node.val += acc
    acc = node.val
    reverse_inorder(node.left)

---

4. 탐색 시간 복잡도

• 평균: O(log n)
• 최악 (한쪽으로 치우친 경우): O(n)
• 균형 잡힌 BST (예: AVL, Red-Black Tree) 는 항상 O(log n) 보장

---

5. 기타 성질 및 활용

삽입/삭제 시 주의사항

• 항상 BST 성질(왼 < 루트 < 오)을 유지해야 함

최소/최대값 찾기

• 최소값: 가장 왼쪽 노드
• 최대값: 가장 오른쪽 노드

LCA (최저 공통 조상)

• 두 노드의 값과 현재 노드의 값을 비교하며 탐색하면 효율적으로 찾을 수 있음

# BST에서의 LCA
if p.val < root.val and q.val < root.val:
    return lowestCommonAncestor(root.left, p, q)
elif p.val > root.val and q.val > root.val:
    return lowestCommonAncestor(root.right, p, q)
else:
    return root

---

6. BST 관련 문제 유형

• 탐색 (search, contains)
• 삽입/삭제
• 정렬 (중위 순회)
• 범위 내 합 구하기 (range sum)
• K번째 작은/큰 원소 찾기
• 트리 변형 (예: Greater Tree)

---

7. 정리

• BST는 정렬된 데이터를 트리 형태로 표현한 구조
• 순회 방식과 트리 구조를 이해하면 다양한 문제를 효율적으로 해결 가능함