[자료구조] 이진탐색트리

정의 1. 모든 노드는 서로 다른 하나의 값을 저장 2.

왼쪽 부분 트리의 모든 값들은 루트 노드의 값보다 더 작음 3. 오른쪽 부분 트리의 모든 값들은 루트 노드의 값보다 더 큼 4.

왼쪽 부분 트리와 오른쪽 부분 트리 모두 이진 탐색 트리 예시 루트 노드인 8을 기준 → 왼쪽은 비교적 작고, 오른쪽은 비교적 더 크다. 연산 - 생성 (초기화) - 검색 - 추가 - 제거 4개의 연산들의 시간 복잡도(n개의 노드)는 같은 결과를 가진다.

Balanced → O(log n) Skewed(Non-Balanced) → O(n) 참고자료 K-mooc 자료구조 http://www.kmooc.kr/courses/course-v1:SMUk+SMU2018_01+2021_1_T1/about Binary search tree https://en.wikipedia.org/wiki/Binary_search_tree Balanced vs Non-Balanced https://appliedgo.net/bal...