[Java, 알고리즘, 탐색] - 탐색 알고리즘 개요
탐색
- 순차 탐색
- 이진 탐색
- 이진 탐색 트리
순차 탐색
배열에서 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법. 보통 정렬되지 않은 배열에서 데이터를
찾아야 할 때 사용한다.
시간 복잡도
하나씩 차례대로 확인하기 때문에 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로
순차 탐색의 시간 복잡도는 O(N)이다
이진 탐색
배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
동작 방식
탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점이 필요하다. 찾으려는 데이터와 중간점 위치에 있는
데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다.
시간 복잡도
한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가
O(logN)이다.
이진 탐색 트리
트리 자료구조
노드와 노드의 연결로 표현하며, 노드란 정보의 단위로서 어떠한 정보를 가지고 있는 개체로 이해할 수 있다.
트리 자료구조는 그래프 자료구조의 일종으로 데이터베이스 시스템이나 파일 시스템같은 곳에서 많은 양의
데이터를 관리하기 위한 목적으로 사용한다.
트리 구조를 이용한 이진 탐색 트리 동작 방식
이진 탐색 트리란 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조다.
이진 탐색 트리 특징 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
부모 노드 8에는 자식노드 3, 10이 있다.
3 < 8
특징 1. 부모 노드보다 왼쪽 자식 노드가 작다.
10 > 8
특징 2. 부모 노드보다 오른쪽 자식 노드가 크다.
3 < 8 < 10
왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드가 성립해야지 이진 탐색 트리라 할 수 있다.
현재 노드와 찾고자 하는 원소 값을 비교한다.
찾고자 하는 원소 값이 현재 노드 값보다 작으면 왼쪽 자식 노드로 이동
찾고자 하는 원소 값이 현재 노드 값보다 크면 오른쪽 자식 노드로 이동
이 과정을 반복한다.
데이터의 개수가 1,000만개를 넘어가면 이진 탐색 알고리즘으로 접근을 고려해보자.