이진 탐색 트리1 Binary Search Tree(이진 탐색 트리) Binary Search Tree는 특정한 규칙을 따르는 이진 트리이다.이진 트리는 부모 노드가 자식 노드를 최대 2개까지 갖는 트리이다.특정한 규칙이란왼쪽 자식 노드는 부모 노드보다 작거나 같다.오른쪽 자식 노드는 부모 노드보다 크다.이진 탐색은 주어진 목표를 향해 전체 크기의 반씩 나누고 비교하여 접근하는 탐색 방법이다.원래는 정렬된 배열에서만 가능했다. 하지만 이진 탐색 트리는 위의 규칙 덕분에 root 노드로부터 찾고자 하는 값을 비교해감으로써 원하는 값에 접근이 쉽다. ✅ 장점1. 탐색, 삽입, 삭제의 연산이 평균적으로 빠르다.트리의 노드 개수가 n 일때, 탐색, 삽입, 삭제의 평균적인 시간 복잡도는 O(log n) 이다.트리의 높이가 h 일때, 연산을 최대 h번 한다.균형이 잘 갖춰진 트리일.. 2025. 2. 20. 이전 1 다음