DATA STRUCTURE
이진 탐색 트리 (BST)
모든 노드가 "왼쪽 자식은 나보다 작다, 오른쪽 자식은 나보다 크다"는 규칙을 지키는 트리를 확인하세요. 같은 값을 넣어도 삽입 순서에 따라 균형 잡힌 트리가 되기도, 한쪽으로 치우친 편향 트리가 되기도 합니다 — 이 모양 차이가 탐색 속도에 얼마나 큰 영향을 주는지 직접 비교해 보세요.
재생 버튼을 누르거나 다음 단계 버튼으로 트리 연산을 시작하세요.
삽입 0회 · 검색 0회
1 / 1
PSEUDOCODE
insert(value): 트리가 비어있으면 루트로 삽입 그렇지 않으면 현재 노드와 비교해 왼쪽/오른쪽으로 이동 반복 빈 자리를 찾으면 그 자리에 새 노드 삽입search(value): 루트부터 비교하며 왼쪽/오른쪽으로 이동 값이 일치하면 발견 null에 도달하면 "찾을 수 없음"어떻게 동작하나요
이진 탐색 트리는 모든 노드가 "왼쪽 서브트리의 모든 값 < 나 < 오른쪽 서브트리의 모든 값"을 지키는 트리입니다. 삽입할 때도, 검색할 때도 루트부터 시작해 값을 비교하며 왼쪽 또는 오른쪽으로 한 걸음씩 내려갑니다 — 매 걸음마다 살펴봐야 할 범위가 절반으로 줄어드는 것이 이진 탐색과 같은 원리입니다. 다만 이 절반씩 줄어드는 효율은 트리가 균형 잡혀 있을 때만 성립합니다 — 값을 정렬된 순서로 그대로 넣으면 트리가 한쪽으로만 길어져 사실상 연결 리스트가 되어버립니다(편향 트리). 이 페이지는 삽입/검색만 다루며, 삭제는 세 가지 경우(자식 없음/하나/둘)를 나누어 처리해야 하는 더 복잡한 규칙이 필요해 범위에서 제외했습니다.
시간·공간 복잡도
- 삽입 (균형 트리)
- O(log n)
- 검색 (균형 트리)
- O(log n)
- 삽입·검색 (편향 트리, 최악)
- O(n)
- 공간 복잡도
- O(n)
"정렬된 순서 삽입"과 "균형 잡힌 삽입" 두 시나리오를 번갈아 보면, 완전히 같은 값 5개로도 트리 높이가 5(편향)와 3(균형)으로 얼마나 달라지는지 확인할 수 있습니다.
Algorithm 코스 자료구조 파일럿(스택·큐·연결 리스트·해시 테이블·힙·이진 탐색 트리) 6종이 모두 완료되었습니다 — Algorithm 코스로 돌아가기