이진탐색

이진탐색

• 비선형 자료구조이다
  

• 데이터의 탐색 속도 증진을 위해 사용하는 구조

• 포인터를 이용해 특정한 루트에서 자식으로 접근하는게 휠씬 간단

• 한번 내려갈때마다 1/2씩 줄어든다. 높이가 logn이 된다

• 힙정렬 구현 할 때는 완전 이진트리 사용되기에 배열로 표현 가능

• 포인터로 왼 자식 오른 자식 구별하는 이뉴는 완전 이진트리가 아닌 것은 배열로 표형하기 어렵기 때문

• 포인터는 데이터의 낭비를 막아준다. 이진트리가 아니면 많은 양의 배열을 만들어야 될 수 도 있다.

이진탐색 순회 방법

• 전위 순회

  • 하나의 노드에 방문했을 때 다음의 순서를 따름
  1. 먼저 자기 자신을 처리
  2. 왼쪽 자식 방문
  3. 오른쪽 자식 방문

• 중위 순회

  • 하나의 노드에 방문했을 때 다음의 순서를 따름
  1. 왼쪽 자식 방문
  2. 자기 자신 처리
  3. 오른쪽 자식 방문

• 후위 순회

  1. 왼쪽
  2. 오른쪽
  3. 자신

  

  1. 전위 순회
     1-2-4-8-9-5-10-11-3-5-6-7-12-13-7-14-15

  2. 중위 순회
     8-4-9-2-10-5-11-1-2-12-6-13-3-14-7-15

  3. 후위 순회
     8-9-4-10-11-5-2-12-13-6-14-15-7-3-1

마스터 정리

• 재귀를 활용한 점화식을 푸는 방법을 알려준다.
• 단순 for문 중첩으로는 알 수 없는 것들을 계산해야 하는 경우
• 재귀를 사용한 알고리즘은 시간 복잡도 구하는 것이 어려운데 이를 활용하면 쉽게 구할 수 있다.

• 마스터 정리를 위한 세가지 제약 조건
  • f(n)은 다항식
  • a>=1와 b>1인 양의 실수여야 함.

마스터 정리를 이용한 이진 탐색