이진탐색트리의 특성이 적혀 있다.
1. adelson velskil landis 이사람이 만든거다...
2. set 중복이 없다...
3. table 테이블 구조다
4. avl 1번의 약자다...
G.M. Adelson-Velskii와 E.M. Landis 가 그들의 논문 "An algorithm for the organization of information" 1, 4번..
1. 검색..
탐색 기법에 대한 시간탐색도를 설명하기 전에 한가지 설명을 한다면..
root 노드를 기준으로 왼쪽과 오른쪽이 있다.
왼쪽은 작은 값이 들어가고 오른쪽은 큰 값이 들어간다.
1. 15를 기준으로 7이란 값은 작으므로 왼쪽으로 이동
2. 6이란 숫자보다 7이란 값은 크므로 오른쪽으로 이동
3. 7를 찾았다.
그렇다면 시간탐색도는 어떻게 될까?...
16개로 구성된 배열로 설명을 해보겠다.
중간요소를 일단 피벗으로 선택한다.
13은 피벗보다 작으므로 나머지 절반을 삭제한다.
총 1/2를 4번 곱했다.
우리가 구하는 수는 n 의 수를 (1/2)^승을 구하는구것이다 몇승인지...
그러므로 시간복잡도는 O(logN)이 된다.