이진탐색 (꼭 트리구조에서만 사용가능한 것이 아님)
=> 데이터가 "정렬로" 나열있을때 찾는 데이터를 찾기위해 데이터를 반반씩 쪼개며 찾는 방식을말함.
ex) 1에서 100 사이에 데이터 40을 찾기위해 1과 100 사이의 50을 기준으로 데이터를 찾아나감.
속도가 logN 이므로 찾는 데이터의 크기가 클 수록 효율이 매우 높아짐.
- 오로지 정렬되어있는 데이터에만 적용이 가능
이진탐색트리
- 이진탐색을 사용 할 수 있게 고안된 이진트리 즉 이진탐색을 쓸 수있는 트리구조
- 데이터 입력시 logN 속도. (vector, list 는 N 속도)
=> 속도 비교표 O(1) => O(logN) => O(N)
- 탐색 효율도 logN 속도. (vector, list 는 1 속도)
- 트리의 모양 밸런스가 유지되지 않으면 탐색 효율이 N 속도에 수렴함.( 즉 의미가 없음)
=> 이를 보안한 것이 자가균형 기능을 탑재한 AVL, Red/Black 트리임.
(AVL, Red/Black 트리 체험 => https://www.cs.usfca.edu/~galles/visualization/RedBlack.html)
C++ STL에서
std::set, set::map 이 있다.