11강 / 20강

이진 탐색 트리 — 반씩 접어 가며 찾는 나무

규칙 하나를 더했을 뿐인데 검색이 폭발적으로 빨라진다

10강의 이진 트리에 규칙 하나를 더해 봅시다.

이진 탐색 트리의 규칙

모든 노드에 대해 — 왼쪽 가지의 모든 값 < 나 < 오른쪽 가지의 모든 값

이 규칙 덕분에 값을 찾을 때 비교 한 번에 절반을 버릴 수 있습니다. 찾는 값이 나보다 작으면? 오른쪽은 볼 필요조차 없어요.

1000개 중에서 찾는다면 리스트는 최악의 경우 1000번 비교하지만, 잘 만든 이진 탐색 트리는 약 10번이면 끝납니다. (1000 → 500 → 250 → … → 1, 즉 2를 열 번 곱하면 1024니까요.)

고등학생규칙 하나를 더했을 뿐인데

10강의 이진 트리에 규칙 하나를 더합니다.

왼쪽은 나보다 작고, 오른쪽은 나보다 크다

이 규칙이 무엇을 만드나

찾을 때 한쪽을 통째로 버릴 수 있습니다.

비교	버리는 것
찾는 값 < 현재	오른쪽 전부
찾는 값 > 현재	왼쪽 전부

한 번 비교할 때마다 절반이 사라진다

숫자로

개수	리스트에서	BST 에서
1,000	1,000번	10번
1,000,000	100만번	20번

100만 개에서 20번 — 이게 "폭발적" 이라는 말의 뜻

비유 — 스무고개

1부터 100만 중 하나를 스무 번 안에 맞힐 수 있습니다.

질문	남는 후보
50만보다 큰가?	50만
25만보다 큰가?	25만
…20번 뒤	1개

"예/아니오" 하나가 후보를 반으로 줄인다

규칙이 있으면 질문 하나로 절반을 지울 수 있어요. 규칙이 없으면 하나씩 확인해야 하고요.

정렬(규칙)의 가치는 찾을 때 드러난다

이진 탐색 트리를 중위 순회하면 저절로 오름차순이 됩니다.

Python 브라우저에서 실행

class 노드:
    def __init__(self, 값):
        self.값, self.왼, self.오 = 값, None, None

def 넣기(뿌리, 값):
    if 뿌리 is None:
        return 노드(값)
    if 값 < 뿌리.값:
        뿌리.왼 = 넣기(뿌리.왼, 값)     # 작으면 왼쪽으로
    elif 값 > 뿌리.값:
        뿌리.오 = 넣기(뿌리.오, 값)     # 크면 오른쪽으로
    return 뿌리                          # 같으면 무시 (중복 없음)

뿌리 = None
for ㅇ in [50, 30, 70, 20, 40, 60, 80]:
    뿌리 = 넣기(뿌리, ㅇ)

def 중위(ㄴ):
    if ㄴ: 중위(ㄴ.왼); print(ㄴ.값, end=" "); 중위(ㄴ.오)

print("중위 순회:", end=" "); 중위(뿌리); print()
print("↑ 넣은 순서는 뒤죽박죽인데 나올 때는 '정렬'되어 있습니다!")

고등학생중위 순회 = 정렬

note 가 말하는 이 성질이 놀랍습니다.

BST 를 중위 순회하면 값이 정렬된 순서로 나온다

왜 그런가

중위 순회는 왼쪽 → 나 → 오른쪽 순서입니다. 그리고 BST 규칙은 왼쪽 < 나 < 오른쪽 이죠.

순회 순서와 크기 순서가 정확히 일치한다

각 노드에서 이 관계가 성립합니다

방문 순서	크기
왼쪽 가지 전부	가장 작다
나	중간
오른쪽 가지 전부	가장 크다

모든 노드에서 성립하니 전체가 정렬된다

비유 — 도서관 서가

책이 왼쪽부터 오른쪽으로 번호순으로 꽂혀 있습니다.

왼쪽 끝부터 읽어 나가면? 번호순으로 읽히죠. 따로 정렬한 게 아니라 꽂을 때 규칙을 지킨 결과입니다.

넣을 때 규칙을 지키면 꺼낼 때 저절로 정렬된다

그래서 BST 가 유용합니다

동작	BST	정렬된 리스트
찾기	O(log n)	O(log n)
넣기	O(log n) ✔	O(n) — 밀린다
정렬해 보기	O(n)	O(n)

정렬을 유지하면서 넣고 뺄 수 있다 — 그게 BST 의 값어치

🎮 이진 탐색 트리 실험실

값을 넣어 트리를 키우고, 찾기를 눌러 어느 길로 내려가는지 보세요. 그리고 1, 2, 3, 4, 5를 순서대로 넣어 보세요. 무슨 일이 벌어지나요?

비교할 때마다 나머지 절반이 통째로 사라집니다.

Python 브라우저에서 실행

class 노드:
    def __init__(self, 값):
        self.값, self.왼, self.오 = 값, None, None

def 넣기(뿌리, 값):
    if 뿌리 is None: return 노드(값)
    if 값 < 뿌리.값: 뿌리.왼 = 넣기(뿌리.왼, 값)
    elif 값 > 뿌리.값: 뿌리.오 = 넣기(뿌리.오, 값)
    return 뿌리

def 찾기(뿌리, 값):
    걸음 = 0
    현재 = 뿌리
    while 현재:
        걸음 += 1
        print(f"  {걸음}번째 비교: {현재.값}", end="")
        if 값 == 현재.값:
            print("  ✅ 찾았다!"); return 걸음
        elif 값 < 현재.값:
            print("  → 더 작다, 왼쪽으로 (오른쪽 전부 버림)")
            현재 = 현재.왼
        else:
            print("  → 더 크다, 오른쪽으로 (왼쪽 전부 버림)")
            현재 = 현재.오
    print("  ❌ 없습니다"); return 걸음

뿌리 = None
for ㅇ in [50, 30, 70, 20, 40, 60, 80, 35, 45]:
    뿌리 = 넣기(뿌리, ㅇ)

print("45 찾기:")
찾기(뿌리, 45)
print()
print("99 찾기:")
찾기(뿌리, 99)

고등학생치명적인 약점 — 한쪽으로 쏠린 트리

note 의 경고가 BST 의 아킬레스건입니다.

이미 정렬된 자료를 넣으면 줄이 된다

1, 2, 3, 4, 5 를 순서대로 넣으면

	기대	실제
깊이	log n	n ⚠
검색	O(log n)	O(n)

트리인데 연결 리스트가 되었다 — 장점이 전부 사라진다

왜 이게 심각한가

정렬된 자료는 아주 흔하거든요.

흔한 자료	정렬돼 있나
날짜순 기록	그렇다
id 순서	그렇다
DB 에서 꺼낸 것	대개 그렇다

가장 흔한 입력에서 최악의 성능이 난다

비유 — 팀 나누기

공정하게 나누려면 절반씩 갈라야 합니다. 그런데 키 순서대로 세워 놓고 나누면?

기준	결과
가운데를 기준으로	반반 ✔
가장 작은 사람 기준	1명 대 나머지 ⚠

기준이 가운데가 아니면 나누는 의미가 없다

해결 — 균형 트리

이름	방법
AVL 트리	기울면 회전해서 편다
레드-블랙 트리	색 규칙으로 균형 유지
B-트리	DB 인덱스가 쓰는 것

넣을 때마다 스스로 모양을 고친다 — 대가는 삽입 비용

실무에서 BST 를 직접 만들 일은 드뭅니다. 이미 만들어진 균형 트리를 쓰거나 딕셔너리(13강)를 쓰죠.

그래도 왜 균형이 필요한지 는 알아야 한다

같은 값 127개, 넣는 순서만 다릅니다. 높이를 비교해 보세요.

Python 브라우저에서 실행

import random

class 노드:
    def __init__(self, 값): self.값, self.왼, self.오 = 값, None, None

def 넣기(뿌리, 값):
    if 뿌리 is None: return 노드(값)
    if 값 < 뿌리.값: 뿌리.왼 = 넣기(뿌리.왼, 값)
    elif 값 > 뿌리.값: 뿌리.오 = 넣기(뿌리.오, 값)
    return 뿌리

def 높이(ㄴ):
    return 0 if ㄴ is None else 1 + max(높이(ㄴ.왼), 높이(ㄴ.오))

값들 = list(range(1, 128))

정렬넣기 = None
for ㅇ in 값들:
    정렬넣기 = 넣기(정렬넣기, ㅇ)

섞어서 = 값들[:]; random.shuffle(섞어서)
섞어넣기 = None
for ㅇ in 섞어서:
    섞어넣기 = 넣기(섞어넣기, ㅇ)

print("값 127개를 넣었습니다.")
print(f"  순서대로 넣으면 높이 = {높이(정렬넣기):3}   ← 사실상 연결 리스트 😱")
print(f"  섞어서   넣으면 높이 = {높이(섞어넣기):3}   ← 이상적인 높이는 7")

정리 — 자료구조 세 개의 검색 비교

자료구조	검색	삽입	정렬된 순서로 꺼내기
리스트 (정렬 안 됨)	🐢 하나씩 다 본다	⚡ 맨 뒤에 붙이기	🐢 매번 정렬해야
정렬된 리스트	⚡ 이진 탐색 (16강)	🐢 자리를 만들려면 밀어내기	⚡ 그냥 순서대로
이진 탐색 트리	⚡ 절반씩 버리기	⚡ 내려가서 붙이기	⚡ 중위 순회
해시 테이블 (13강)	⚡⚡ 즉시	⚡⚡ 즉시	❌ 순서 없음

완벽한 자료구조는 없습니다. 무엇을 자주 하느냐가 선택을 결정합니다 — 20강의 주제입니다.

고등학생BST 와 딕셔너리, 무엇을 쓸까

둘 다 빠른 검색을 줍니다. 뭐가 다를까요?

	BST (균형)	딕셔너리 (해시)
찾기	O(log n)	O(1) ✔
정렬 순서	유지된다 ✔	없다
범위 검색	가능 ✔	불가능
최소·최대	즉시	전부 훑어야

속도는 해시가 이기고, 순서는 트리가 이긴다

범위 검색이 결정적입니다

"3월 1일부터 3월 15일까지의 기록" 을 찾으려면?

구조	방법
트리	3월 1일을 찾고 순서대로 읽는다 ✔
해시	전부 확인해야 한다 ⚠

해시는 "이것 있나?" 만 답한다 — "이 사이" 는 못 한다

그래서 DB 인덱스는 트리입니다

/db 7강의 인덱스가 B-트리 인 이유예요.

SQL	필요한 것
`WHERE id = 5`	해시도 된다
`WHERE 날짜 BETWEEN …`	트리여야 한다
`ORDER BY 이름`	트리여야 한다

범위와 정렬이 필요하면 트리, 딱 하나 찾기면 해시

비유 — 사전과 색인 카드

	사전 (트리)	이름표 상자 (해시)
"apple" 찾기	빠르다	더 빠르다
"ap~" 로 시작하는 것 전부	이어서 읽는다 ✔	불가능

20강의 물음 — "무엇을 자주 하느냐" 가 답을 정한다

🤔 확인 문제

이진 탐색 트리의 규칙은?

🤔 확인 문제

이진 탐색 트리를 중위 순회하면 값이 어떤 순서로 나올까요?

🤔 확인 문제

1부터 1000까지를 순서대로 이진 탐색 트리에 넣으면?