이진 탐색 트리 (BST, Binary Search Tree)

이진 탐색 트리 (BST, Binary Search Tree)

모든 노드가 왼쪽 서브트리의 모든 값 < 노드 값 < 오른쪽 서브트리의 모든 값 속성을 만족하는 이진 트리로, 효율적인 검색·삽입·삭제를 지원

목적: 빠른 검색·삽입·삭제, 정렬된 순서 유지, 동적 집합 관리

특징: 정렬 속성, 중위 순회 = 정렬 순서, 재귀적 구조, 동적

속성: 왼쪽 서브트리 < 노드 < 오른쪽 서브트리 (모든 노드)

연산

• •검색(Search): 재귀 또는 반복, O(h)
• •삽입(Insert): 리프 위치 찾아 삽입, O(h)
• •삭제(Delete): 3가지 케이스, O(h)
• •최소/최대: 가장 왼쪽/오른쪽, O(h)
• •중위 순회: 정렬 순서 출력, O(n)

시간 복잡도

• •평균: O(log n) - 균형 트리
• •최악: O(n) - 편향 트리(한쪽으로 치우침)

공간 복잡도: O(n)

장점: 빠른 검색·삽입·삭제(평균 O(log n)), 정렬 순서, 범위 쿼리, 동적

단점: 편향 시 O(n), 균형 유지 필요, 포인터 메모리

적용사례: 동적 집합, 우선순위 큐, 심볼 테이블, 데이터베이스 인덱스

비교: BST(정렬속성/평균 O(log n)) vs 해시(정렬없음/O(1)) vs AVL(균형보장/O(log n))

연관: 이진 트리, AVL 트리, Red-Black 트리, 균형 트리