자료구조 - Chapter 11

탐색의 이해

탐색(Search)

탐색은 알고리즘보다 자료구조에 더 가깝게 연관되어 있다.

어떻게 탐색해야할지 생각하기 보다 효율적인 탐색을 위한 저장 방법을 고려해야한다.

또한 효율적인 탐색이 가능한 대표적인 저장 방법은 트리이다.

 

보간 탐색(Interpolation Search)

보간 탐색은 이진 탐색의 비효율 성을 개선한 알고리즘이다. 

이진 탐색은 무조건 탐색 위치의 중간을 찾아 간다면, 보간 탐색은 비율을 통하여 그 값을 찾아간다.

 

Index = target - arr[left] / (arr[right] - arr[left]) * (right - left) + left

#여기서 left는 가장 왼쪽 인덱스 right는 가장 오른쪽 인덱스를 지칭한다.

 

탐색 Item에 대한 구조체 정의

• 탐색 키 (Search Key)
• 탐색 데이터(Search data)

탐색을 적용할 때, 탐색 키와 탐색 데이터를 묶는 형태의 구조체를 정의하고, 정렬이나 탐색이나 그 탐색

대상을 탐색 키에 맞춘다. 탐색의 키는 그 값이 고유해야한다.

 

예제 : 보간 탐색 구현하기

기존 이진 탐색 방법에 대해서 mid 부분을 수정하고 탈출 조건을 수정하면 완성된다.

 

보간 탐색 구현하기

ex11-1 Interpolation Search.c

0.00MB

이진 탐색 트리

이진 트리의 구조를 보면, 트리는 탐색에 효율적이다.

이진 탐색 트리는 이진트리에 데이터의 저장 규칙을 더해 놓은 것이다.

 

데이터 저장 규칙

• 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다
• 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떤 노드의 키보다 크다.
• 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떤 노드의 키보다 작다
• 왼쪽과 오른쪽 서브 트리도 이진 탐색트리이다.

예제 : 간단한 이진 탐색트리 구현하기

이진트리에 대한 소스는 전 포스팅의 자료를 끌고 왔다.

 

이진 탐색트리 구현하기

BinarySearchTree.c

0.00MB

BinarySearchTree.h

0.00MB

ex11-2 BinaryTree Search.c

0.00MB

예제 : 이진트리 삭제 구현하기

이진탐색트리에서 임의의 노드를 삭제하는 경우, 삭제 후에도 여전히 이진 탐색 트리가 유지되도록

빈 자리를 채워야한다.

• 경우 1 : 삭제할 노드가 단말 노드인 경우
• 경우2 : 삭제할 노드가 하나의 자식 노드를(하나의 서브 트리를) 갖는 경우
• 경우3 : 삭제할 노드가 두 개의 자식 노드를(두 개의 서브 트리를) 갖는 경우

이진 탐색트리 노드 삭제 구현하기

BinaryTree3.c

0.00MB

BinaryTree3.h

0.00MB

ex11-3 BinarySearchTree delete.c

0.00MB

BinarySearchTree2.c

0.00MB

BinarySearchTree2.h

0.00MB