TIL 8 | 알고리즘 - 이진 탐색

grighth12·2021년 8월 10일
1

TIL

목록 보기
8/15
post-thumbnail

이진 탐색

  • 요소들이 이미 정렬되어 있는 상태일 때, 정렬 되어 있는 요소들을 반씩 제외하며 찾느 알고리즘이다.
  • 선형 탐색보다 훨씬 빠르다.
  • O(nlog(n))

1. 배열을 이용한 구현

  • left(가장 첫 index), mid(중간 index), right(가장 마지막 index) 변수가 있다고 하자.
  1. mid 인덱스의 배열 값과 찾는 값을 비교한다.
    1-1. mid 인덱스의 배열 값이 찾는 값보다 크면, leftmid+1로 옮긴다. mid 값을 다시 계산하여 1을 반복한다.
    1-2. mid 인덱스의 배열 값이 찾는 값보다 작으면, rightmid-1로 옮긴다.mid 값을 다시 계산하여 1을 반복한다.
    1-3. mid 인덱스의 배열 값이 찾는 값과 같으면 탐색이 끝난다.
  • 배열이기 때문에, 삽입과 삭제 시 선형 시간이 걸린다는 단점이 있다.

2. 이진 탐색 트리를 이용한 구현

  • 배열의 단점을 해결한다.
  • 이진 탐색 트리는 이진 트리에 왼쪽 서브트리는 루트보다 작은 값이 모여있고, 오른쪽 서브트리는 루트보다 큰 값이 모여있다는 규칙이 추가된 것 이다.
  • 최악의 경우 한쪽으로 편향된 트리가 될 수 있고, 이럴 경우 순차 탐색과 같이 선형 시간이 걸린다는 문제점이 있다.
    • 이를 해결하기 위해 AVL 트리, 레드-블랙 트리와 같은 자료구조를 이용할 수 있다.

      AVL 트리
      트리가 편향될 경우 좌회전, 우회전하여 균형을 유지하는 이진 탐색 트리

이진 탐색 트리의 동작

  • 삽입

    • 가장 처음 삽입한 노드가 루트가 된다.
    • 루트를 기준으로 작으면 왼쪽, 크면 오른쪽으로 간다. 이미 해당 위치에 노드가 존재하면 존재하는 노드의 value와 삽입할 노드의 value를 비교하여 빈 위치로 갈 때까지 반복한다.
  • 삭제

    1. 단말 정점(리프 노드)을 삭제하는 경우

      • 부모 노드와의 연결을 끊는다.
      • 위 그림에서 3을 삭제하는 과정을 생각하면, 4와의 간선을 끊으면 3은 참조가 되지 않아 사라진다.
    2. 하나의 서브 트리를 가지는 경우

      • 제거되는 노드를 참조하고 있는 부모 노드의 간선이 자식 노드를 가리키게 바꾼다.
      • 위 그림에서 4를 삭제하는 과정을 생각하면, 5의 왼쪽 간선이 3을 가리키도록 하면 된다. 4는 참조가 되지 않으므로 삭제된다.
    3. 두 개의 서브트리를 가지는 경우

      • 왼쪽 서브 트리의 가장 큰 값을 가지는 노드 또는 오른쪽 서브 트리의 가장 작은 값을 가지는 노드 중 하나를 선택하여 삭제할 노드와 교체한다.
      • 위 그림에서 7을 삭제하는 과정을 생각하면, 78(오른쪽 서브트리의 가장 작은값)로 교체하거나 76(왼쪽 서브트리의 가장 작은 값)으로 교체하는 경우 둘 다 이진 탐색트리의 규칙을 만족하게 된다.

출처

프로그머스 데브코스 프론트엔드 Day4 [강의] 이진탐색
profile
데굴데굴 굴러가고 있습니다

0개의 댓글