Algorithm Guidecomplexity: 평균 O(log n)

이진 탐색 트리 (BST)

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

01 Explore How It Works

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 Understand It Simply

For Everyone

🔑Analogy

숫자 맞히기 스무고개 — '그보다 큰가요?'로 매번 절반씩 좁혀갑니다.

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 이진 탐색 트리 (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