Algorithm Guidecomplexity: 평균 O(log n)

이진 탐색 트리 (BST)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Binary Search Tree

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

Logic Node1 / 8

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

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