알고리즘 12강 :: 순차 탐색, 이진 탐색, 이진 탐색 트리

알고리즘 12강을 보며 배운내용

 

 

탐색

데이터 형태

리스트, 트리, 그래프 등에서 원하는 데이터 찾는것

 

내부 탐색 vs 외부 탐색

 

탐색 연산

탐색 + 초기화(정렬), 삽입, 삭제

 

이번 강의에서는

• 순차 탐색
• 이진 탐색
• 탐색 트리 -> 이진 탐색 트리

 

다음 강의에서는

• 균형 탐색 트리(흑적트리, B-트리)
• 해싱

 

 

순차 탐색

배열이나 연결리스트 형태로 주어진 원소들을

처음부터 차례대로 비교하면서 원하는 값 찾는 방법

 

⌛ 시간복잡도

• 탐색: O(n)
• 삽입: O(1)
• 삭제: O(n)

 

✨특징

• 모든 리스트에 적용 가능
• 원소가 순서 없이 저장된 경우 적합하다
• 데이터 큰 경우 부적합
• 알고리즘 간단
  반복문 돌려서 앞에서부터 비교해주면 된다.

 

삽입 연산(배열)

맨 뒤에 붙여주면 된다

 

🤖삭제 연산(배열)

맨 마지막 데이터를 해당 원소에 덮어쓴다

// 순차탐색 삭제연산
function 순차탐색_Delete(원배열, 찾을원소) {
  // 찾을 원소가 어딨는지 확인
  const index = 순차탐색(원배열, 찾을원소)
  
  // 없으면 원배열 반환
  if(index === -1) return 원배열
  
  // 있으면 찾은 자리에 마지막 원소로 덮어쓰기
  원배열[index] = 원배열[배열크기 - 1]
  원배열.pop()
  return 원배열
}

 

삽입 연산(연결 리스트)

맨 앞에 넣는다

 

삭제 연산(연결 리스트)

해당 양쪽 노드 이어주면 끝!

 

 

이진 탐색

정렬된 배열에 사용할 수 있다

절반씩 줄여가면서 원하는 값 찾는 방법

탐색값 7

 

⌛시간복잡도

• 탐색: O(logn)
• 초기화(정렬): O(nlogn)
• 삽입: O(n)
• 삭제: O(n)

 

✨특징

• 분할 정복 방법
• 연결 리스트는 이진 탐색 구현 불가능
• 삽입과 삭제가 빈번한 경우에는 부적합
  => 이진 탐색 트리의 배경

 

🤖알고리즘

function binarySearch(원배열, 왼쪽, 오른쪽, 탐색값){
  if(왼쪽 > 오른쪽) return -1
  let 가운데 = Math.floor((왼쪽 + 오른쪽) / 2)
  
  if(탐색값 == 원배열[가운데]) return 가운데
  else if(탐색값 < 원배열[가운데]){
    binarySearch(원배열, 왼쪽, 가운데 - 1, 탐색값)
  } else {
    binarySearch(원배열, 가운데 + 1, 오른쪽, 탐색값)
  }
}

 

삽인 연산(배열)

1. 삽입할 위치를 찾고
2. 삽입할 위치 뒤부터 한 칸씩 뒤로 이동시키고
3. 삽입한다

 

삭제 연산(배열)

1. 삭제할 인덱스를 찾고 삭제
2. 그 뒤의 원소부터 한 칸씩 앞으로 이동

 

 

이진 탐색 트리

루트 노드에서 시작해서

작으면 왼쪽, 크면 오른쪽으로 트리를 따라 내려가며 탐색

 

⌛시간복잡도

탐색

이진 트리의 높이에 비례

• 모든 차수가 2(최소 높이): O(logn)
• 모든 차수가 1(경사 이진 트리): O(n)

 

 

✨특징

• 이진 트리
  각 노드의 왼쪽 서브트리에 있는 키 값은 그 노드의 키값보다 작다
  각 노드의 오른쪽 서브트리에 있는 키 값은 그 노드의 키값보다 크다
• 연결 리스트 사용
• 삽입/삭제에 따라 경사 트리 형태가 될 수 있다
  => 최악의 수행 시간 O(n)
  => 경사 트리가 되지 않으면 O(logn) 보장
  => 그래서 나온 균형 탐색 트리(흑적 트리, B-트리)

 

🤖알고리즘

// 이진 탐색 트리
function BST_search(트리, 탐색값){
  현재노드 = 트리의 루트 노드
  
  // 현재 노드가 Null이면 종료
  while(현재노드 !== Null){
  
    // 현재노드 값이 탐색값과 같으면 현재노드 반환
    if(탐색값 === 현재노드.key) return 현재노드
    
    // 탐색값이 작으면 현재노드 왼쪽으로 따라 내려간다
    else if(탐색값 < 현재노드.key) {
      현재노드 = 현재노드.왼쪽
      
    // 크면 오른쪽으로 내려간다
    } else {
      현재노드 = 현재노드.오른쪽
    }
  }
  
  // 여기까지 오면 값이 없으니 Null 반환
  return Null
}

 

삽입 연산

탐색값을 찾아서 내려가다가

더 이상 내려갈 곳(탐색할 곳)이 없으면 삽입

 

삭제 연산

복잡하네, 반복 필요

 

 

Search by Marten Newhall @unsplash