Algorithm Guidecomplexity: 평균 O(log n)

이진 탐색 트리 (BST)

왼쪽 자식 < 부모 < 오른쪽 자식 규칙을 지키는 이진 트리입니다. 정렬된 구조 덕분에 탐색·삽입·삭제를 평균 O(log n)에 처리하지만, 한쪽으로 치우치면 O(n)까지 퇴화합니다.

01이진 탐색 트리 (BST)

알고리즘 작동 원리 탐색

이진 탐색 트리(BST). 왼쪽엔 작은 값, 오른쪽엔 큰 값을 두는 규칙으로 값을 삽입합니다.

30 삽입 · 30 < 50이므로 루트의 왼쪽으로 내려가 자리를 잡습니다.

70 삽입 · 70 > 50이므로 오른쪽으로 내려가 자리를 잡습니다.

20 삽입 · 20 < 50(왼쪽), 20 < 30(왼쪽). 두 번 내려가 자리를 잡습니다.

40 삽입 · 40 < 50(왼쪽), 40 > 30(오른쪽)으로 내려가 자리를 잡습니다.

60 삽입 · 60 > 50(오른쪽), 60 < 70(왼쪽)으로 내려가 자리를 잡습니다.

search(40) · 50에서 왼쪽, 30에서 오른쪽으로 두 번 만에 40을 찾습니다.

정렬 규칙 덕분에 매 비교마다 한쪽 가지를 통째로 건너뜁니다 — 평균 O(log n)으로 빠릅니다.

Live Python

1class Node:

2 def __init__(self, key):

3 self.key = key

4 self.left = None

5 self.right = None

7def insert(root, key):

8 if root is None:

# root = 50

9 return Node(key)

10 if key < root.key:

11 root.left = insert(root.left, key)

12 elif key > root.key:

13 root.right = insert(root.right, key)

14 return root

16def search(root, key):

17 while root and root.key != key:

18 root = root.left if key < root.key else root.right

19 return root

1 / 8

02 쉽게 이해하기

For Everyone

🔑핵심 동작

왼쪽에는 작은 값, 오른쪽에는 큰 값만 둡니다. 한 번 비교할 때마다 볼 범위가 절반으로 줄어듭니다.

💡쉽게 말하면

왼쪽엔 작은 값, 오른쪽엔 큰 값을 두는 나뭇가지 구조예요.

이 규칙 덕에 찾을 때 절반씩 건너뛰어 빠릅니다(평균 O(log n)).

📍어디에 쓰나

–정렬된 데이터의 빠른 검색·삽입
–범위 조회
–자동완성 사전

03 파이썬 구현 코드

이진 탐색 트리 (BST)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root

def search(root, key):
    while root and root.key != key:
        root = root.left if key < root.key else root.right
    return root