AVL 트리

벡터와 스택 테스터를 통과했다면 AVL의 차례이다

자료구조 전공수업을 들은 지 벌써 3년이 넘었기 때문에 ㅡ,,ㅡ; 사실 그때도 레드블랙만 한듯

암튼 공부해야한다

특징

이진 탐색

이진 탐색은 데이터 배열에서 특정 값을 찾기 위한 하나의 방법이다

배열 내에서의 중간값과 찾고자 하는 값을 비교하면서 범위를 절반씩 줄여나가면서 값을 탐색하는 방법이다

$> 1부터 99까지의 수가 있습니다.
$> 제가 생각하는 숫자를 맞춰보세요.

• 50보다 작습니까? : 예
  • 범위가 1 ~ 99 에서 1 ~ 49 로 줄어들었다 (50개)
• 24보다 큽니까? : 예
  • 범위가 1 ~ 49 에서 25 ~ 49 로 줄어들었다 (25개)
• 37보다 작습니까? : 아니오
  • 범위가 25 ~ 49 에서 37 ~ 49 로 줄어들었다 (13개)
• 43보다 큽니까? : 예
  • 범위가 37 ~ 49 에서 44 ~ 49 로 줄어들었다 (6개)
• 47보다 작습니까? : 아니오
  • 범위가 44 ~ 49 에서 47 ~ 49로 줄어들었다 (3개)
• 48보다 큽니까? : 예
  • 정답은 49 1개로 추려졌다

매번 범위가 약 반토막이 나기 때문에, n개 데이터에 대하여 시간 복잡도가 상당히 작다 (O(log n))

단점은 배열에 있는 값들이 정렬되어 있어야 이진 탐색이 적용된다는 점