<aside> 💡 2진 트리를 사용하려면 반드시 데이터 값이 정렬되어 있어야 한다.

</aside>

2진 트리(2진 검색) 이란

0, 1, 2, 3, 4, 5라는 값이 저장되어 있는 데이터가 있다 찾고 자 하는 값이 1일 경우

절반으로 나눈 값 3을 먼저 찾고, 이후 다시 절반으로 나눈 값 2를 찾고 다시 절반으로 나눠서

값 1을 찾게됨

즉, 값을 찾을 수 있을 때 까지 계속해서 데이터의 크기를 절반으로 나눔

이 때, 찾고자 하는 값이 데이터의 절반 부분에 있는 값보다 크다면 오른쪽으로 작다면 왼쪽으로 이동 (오름차순 정리 하여두면 가능)

데이터 크기가 256 개면 8번의 검색이 필요함

이를 시간복잡도 라고 한다.

2^8 256

2^10 1024

2^16 65536

2^32 42억 9천

데이터의 수가 많으면 많을 수록 2진 트리가 유리하나, 만약 하나가 아니라 여러 가지의 데이터를 찾아야 하는 경우에는 2진 트리보다 풀스캔이 유리해 질 수도 있다.

데이터 21개의 경우 5개의 데이터를 찾는다면 시간 복잡도가 25번으로 늘어남

이런 경우는 풀스캔이 유리해짐(풀스캔은 21번 찾으면 되니)