이진탐색(이분탐색)알고리즘

BinarySearchTree와 이진탐색 모두 조회에 있어 O(logN)의 성능을 보인다.

그러나 삽입&삭제 연산의 성능이 다르다.

 

BST vs 이진탐색 알고리즘 성능비교

 

이름	조회	삽입	삭제
BST	O(logN)	O(logN)	O(logN)
이분탐색	O(logN)	N	N

 

이진탐색 알고리즘(선형 자료구조)의 한계

이진탐색 알고리즘의 전제조건은 "데이터가 정렬되어 있어야한다" 라는 것이다.

 

이진탐색을 하기 위해서는 인덱스 접근을 빠르게 해야하므로 배열리스트를 이용할 수 밖에 없다.

배열 리스트에서의 데이터 삽입은 데이터들을 뒤로 밀어야하므로O(N)이다.

 

따라서 이진탐색 알고리즘(선형자료구조)에서의 삽입&삭제는 모두O(N)이다.