이진탐색,이진탐색트리,BinarySearch,BinarySearchTree

이진 탐색

특징

- 데이터가 정렬되어 있을때 가능하다.

- 데이터를 배열 형태 정렬된 데이터를 들고 있으면 중간 데이터 접근이 빠르나, 데이터를 중간 삽입/삭제이 느리다.

- 데이터를 리스트 형태로 정렬된 데이터를 들고 있으면 임의접근이 빈번이 일어나는 이진탐색에서 비효율적이다

 

 

이진탐색트리

특징

- 데이터를 이진트리에 정렬된 데이터를 갖고 있으면 탐색 속도와 중간 데이터 삽입/삭제, 배열과 리스트의 이점을 모두 만족하는 이진탐색이 가능하다.

- 이진탐색트리를 이용할 경우, 이진 균형 트리 형태일 때 이진탐색이 시간복잡도lon2N으로 동작한다. 한쪽에 데이터가 치우져 있으면 일반 연결리스트와 다를바 없다.

- 이진 균형 트리의 종류에는 avl, red-black tree 등이 있다.