자료구조 & 알고리즘 (이진 탐색)

이진 탐색

정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘

0(log n) 만큼 시간복잡도가 걸린다.

이진 탐색의 특징

▶ 반드기 정렬이 되어있어야 사용할 수 있다.

▶ 배열 혹은 이진 트리를 이용하여 구현할 수 있다.

▶ 0(log n) 시간복잡도인 만큼 상당히 빠르다.

이진 탐색 트리를 이용한 구현 방법

이진 탐색 트리

이진 탐색을 위한 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값이 모여 있고

오른쪽 서브 트리는 루트보다 큰 값이 모여있다.

이진 탐색 트리의 문제점

▶ 최악의 경우 한쪽으로 편향된 트리가 될 수 있다.

▶ 그런경우 순차 탐색과 동일한 시간복잡도를 가진다.

▶ 이를 해결하기 위해 다음과 같은 자료구조를 이용할 수 있다.

    ▶ AVL 트리

    ▶ 레드-블랙 트리 

JavaScript에서 사용법

Array

Binary Search Tree