이진탐색트리 시각화
BST 삽입·탐색·삭제를 단계별 애니메이션으로 배우는 인터랙티브 자료구조 학습 도구
자료구조★★☆
속도
1 / 1노드 수: 0트리 높이: 0
연산 선택
현재 노드방문함삽입됨삭제됨
BST 속성을 유지하면서 각 연산이 어떻게 동작하는지 단계별로 관찰하세요.
비교
← 왼쪽으로
오른쪽으로 →
삽입
발견!
없음
값을 입력하고 실행을 눌러 시작하세요.
이진탐색트리(BST)란?
이진탐색트리(Binary Search Tree)는 각 노드가 최대 두 개의 자식을 가지는 트리 자료구조입니다. 핵심 속성: 왼쪽 서브트리의 모든 값 < 부모 값 < 오른쪽 서브트리의 모든 값. 이 속성 덕분에 삽입·탐색·삭제 연산이 평균 O(log n)으로 매우 빠릅니다.
사용 방법
- 1값을 입력하고 삽입/탐색/삭제 연산을 선택한 후 실행하세요
- 2재생 버튼으로 단계별 애니메이션을 관찰하세요
- 3랜덤 버튼으로 무작위 트리를, 정렬 버튼으로 최악 케이스를 생성하세요
- 4균형 버튼으로 높이가 최소화된 균형 트리를 만들어 비교하세요
- 5오른쪽 패널에서 단계별 과정과 실제 코드를 동시에 확인하세요
동작 원리
- 1삽입 — 루트부터 시작하여 값이 작으면 왼쪽, 크면 오른쪽으로 이동. 빈 자리를 찾으면 새 노드 생성
- 2탐색 — 루트부터 값 비교하며 좌/우 이동. 찾으면 반환, 리프까지 도달하면 실패
- 3삭제 — 3가지 경우: ①리프 노드 제거, ②자식 1개면 자식을 올림, ③자식 2개면 중위 후속자(오른쪽 서브트리 최솟값)로 교체 후 제거
- 4평균 O(log n), 최악(편향 트리) O(n)
실무 활용
- •데이터베이스 인덱스(B-Tree, B+Tree)의 기반 자료구조
- •파일 시스템의 디렉토리 구조 관리
- •컴파일러의 심볼 테이블(변수/함수 이름 검색)
- •자동 완성 기능(Trie의 기반 개념)
- •게임의 리더보드 — 점수 기반 순위 조회/갱신
비슷한 알고리즘
- •AVL 트리 — BST에 높이 균형 조건 추가(좌우 높이 차 ≤ 1). 항상 O(log n) 보장하나 삽입/삭제 시 회전 오버헤드
- •레드-블랙 트리 — AVL보다 느슨한 균형 조건. 삽입/삭제가 빈번한 경우 AVL보다 빠름. Java TreeMap, C++ std::map이 사용
- •B-Tree — 디스크 기반 탐색에 최적화. 노드가 여러 키를 저장하여 디스크 I/O 최소화. 데이터베이스의 표준 인덱스
학습 팁
- •정렬된 순서로 삽입하면 트리가 한쪽으로 치우쳐 O(n)으로 성능이 저하됩니다
- •균형 트리는 높이가 log n에 가까워 모든 연산이 O(log n)을 유지합니다
- •삭제 연산 중 자식이 2개인 경우 후계자(우측 최솟값)로 교체하는 과정을 관찰하세요
- •트리 높이와 비교 횟수의 관계를 다양한 입력으로 확인해보세요
자주 묻는 질문
Q. BST와 이진 힙의 차이점은?
A. BST는 왼쪽<부모<오른쪽 속성으로 탐색에 최적화됩니다. 이진 힙은 부모≥자식 속성으로 최댓값(최솟값) 추출에 최적화됩니다. 힙은 임의 값 탐색이 O(n)입니다.
Q. 삭제 연산에서 후계자란?
A. 두 자식이 있는 노드를 삭제할 때, 해당 노드 다음으로 큰 값(오른쪽 서브트리의 최솟값)이 후계자입니다. 후계자 값으로 교체 후 후계자 노드를 삭제하면 BST 속성이 유지됩니다.
Q. 균형 BST는 어떻게 유지하나요?
A. AVL 트리나 Red-Black 트리 같은 자가 균형 BST는 삽입·삭제 후 회전 연산으로 트리 높이를 O(log n)으로 유지합니다. Java의 TreeMap, C++의 map이 이를 사용합니다.