Python 알고리즘

Python으로 배우는 이진 탐색 트리

이진 탐색 트리는 작은 값을 왼쪽 서브트리에, 큰 값을 오른쪽 서브트리에 둡니다. 그래서 비교할 때마다 남은 트리의 절반을 제외할 수 있습니다.

Python으로 배우는 이진 탐색 트리이란?

이진 탐색 트리는 작은 값을 왼쪽 서브트리에, 큰 값을 오른쪽 서브트리에 둡니다. 그래서 비교할 때마다 남은 트리의 절반을 제외할 수 있습니다.

Python으로 이진 탐색 트리를 만들고 값을 삽입하고, 검색하고, 정렬된 순서로 나열합니다.

언제 사용하나요?

알고리즘과 자료 구조를 이해합니다.
각 단계와 경계 조건을 확인합니다.
실행 시간과 메모리 사용량을 비교합니다.

동작 원리 보기

값을 삽입해 어디에 놓이는지 보고, 값을 검색해 경로를 따라가고, 순회를 실행해 방문 순서를 확인하세요.

예제 코드

코드 실행 →

main.py

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None   # smaller values go left
        self.right = None  # larger values go right


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


def contains(node, value):
    # Each comparison discards one whole subtree.
    while node is not None:
        if value == node.value:
            return True
        node = node.left if value < node.value else node.right
    return False


def inorder(node):
    # Left subtree, node, right subtree: visits values in sorted order.
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)


def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))


root = None
for value in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, value)

print("inorder:", inorder(root))
print("contains 60:", contains(root, 60))
print("contains 65:", contains(root, 65))
print("height:", height(root))

예상 출력

inorder: [20, 30, 40, 50, 60, 70, 80]
contains 60: True
contains 65: False
height: 3

작동 원리

insert()는 루트에서 아래로 내려가 값을 알맞은 자리에 붙입니다. contains()는 하나의 경로만 따라가므로 균형 잡힌 트리에서는 O(log n) 단계면 됩니다. 중위 순회(inorder)는 왼쪽, 노드, 오른쪽 순으로 방문하므로 값이 정렬된 순서로 나옵니다.

값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.

연습 문제

입력값과 경계 조건을 바꾸고 더 큰 데이터에서도 동작을 확인하세요.

빈 입력, 한 요소, 중복값을 시험하세요.
각 단계의 상태를 출력하세요.
다른 풀이와 성능을 비교하세요.

Python IDE에서 실행 →

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지