정렬되지 않은 데이터의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾는 방법
탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법
크기가 적은 리스트에서는 효유류적이지만 크기가 큰 리스트에서는 매우 비효율적
장점
하나씩 비교하기 때문에 탐색에 용이
탐색 알고리즘이 간단함
단점
탐색 시간이 느리며 수행 시간 오래 걸림
순차 탐색 실행 예
이진 탐색 (Binary Search)
전체 데이터 집합을 두 부분으로 나누어 검색하고자 하는 값이 어느 부분에 속하는 가를 결정하여 그 부분에 대하여 순환적으로 탐색을 수행하는 방법
즉, 정렬된 리스트에서 중간에 위치한 키 값과 찾으려는 값이 같으면 탐색 성공
서로 다르면 중간 항목을 기준으로 두 부분 중 한쪽 리스트를 선택하여 키를 정한 후 다시 이진 탐색해서 찾으면 성공
그래도 없으면 나머지 다른 한쪽에서 이진 탐색
특징
분할 및 정복에 의한 탐색 방법의 하나로 리스트가 정렬되어 있는 경우에 적합한 탐색 방법
따라서, 이진 탐색 방법을 적용할 경우, 먼저 리스트의 항목들을 정렬시켜야 하는데, 레코드의 삽입, 삭제가 빈번하게 실행되는 경우, 리스트를 재구성에 의한 항목들의 이동이 요구되기 때문에 데이터의 삽입, 삭제가 거의 없는 리스트에 적합함
이진 탐색 실행 예
보간 탐색 (Interpolation Search)
탐색하고자 하는 키 값의 위치를 예측하여 탐색하는 방법
사전이나 전화번호부를 탐색하는 방법과 동일
사전을 찾을 때 'ㅎ'로 시작하는 단어는 사전의 뒷부분에서 찾고
'ㄱ'으로 시작하는 단어는 앞부분에서 찾는 것과 같은 원리
보간 탐색은 이진 탐색과 유사하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 검색
이진 탐색처럼 리스트가 정렬되어 있는 경우에 적합한 탐색
많은 데이터가 비교적 균등하게 분포되어 있는 경우 보간 탐색이 이진 탐색보다 우수
이진트리 탐색 (Binary Tree Search)
탐색 속도와 항목을 효율적으로 수정할 수 있도록 주어진 리스트를 이진트리로 구성하여 탐색하는 방법
근 노드를 중심으로 좌측 트리는 근 노드보다 작은 값, 우측 트리는 큰 값이 존재하도록 구성
이진 탐색과 이진 트리 탐색 방법의 차이점
이진 탐색과 이진 트리 탐색 방법은 근본적으로 같은 원리에 의한 탐색 구조
이진 탐색은 자료를 삽입하고 삭제할 때마다 앞뒤의 원소들을 이동시켜야 함
이진 트리 탐색 방법은 비교적 빠른 시간 안에 삽입과 삭제를 수행할 수 있음
삽입, 삭제가 빈번히 이루어진다면 반드시 이진 트리 탐색 방법 사용
이진 탐색 트리에서의 탐색 (순환적 기술)
키 값이 x인 원소를 탐색
시작: root
이진 탐색 트리가 공백이면 실패로 끝남
root의 키값 = x 이면 탐색은 성공하며 종료
키값 x < root 이면, root의 왼쪽 서브 트리만 탐색
키값 x > root 이면, root의 오른쪽 서브 트리만 탐색
이진 탐색 트리에서의 삽입
키 값이 x인 새로운 원소를 삽입
x를 키값으로 가진 원소가 있는지 탐색
탐색이 실패하면 탐색이 종료된 위치에 원소 삽입
ex) 키값 13, 50 삽입 과정
이진 탐색 트리에서의 삭제
삭제하려는 원소의 키 값이 주어졌을 때
이 키 값을 가진 원소를 탐색
원소를 찾으면 삭제 연산 ㅅ행
해당 노드의 자식 수에 따른 세 가지 삭제 연산
자식이 없는 단말 노드의 삭제
자식이 하나인 노드의 삭제
자식이 둘인 노드의 삭제
1. 자식이 없는 단말 노드의 삭제
제거할 노드가 단말 노드면 그대로 삭제
2. 자식이 하나인 노드의 삭제
삭제되는 노드 자리에 그 자식 노드 트리 위치
3. 자식이 둘인 노드의 삭제
삭제되는 노드의 좌측 트리 중 제일 오른쪽 단말 노드로 대체
이진트리 탐색 예
노드 생성
노드 삽입
트리 순회(전위 / 중위 / 후위)
이진 검색
Node.java
package tree;
public class Node {
int value;
Node leftChild;
Node rightChild;
// 생성자: 멤버 변수 초기화
public Node(int value) {
this.value = value;
leftChild = null; // 객체이므로 null로 초기화
rightChild = null;
}
}
BinaryTree.java
package tree;
public class BinaryTree {
Node rootNode = null;
// 새로운 노드 삽입
public void insertNode(int element) {
// 루트가 빈 경우. 즉, 아무 노드도 없는 경우 -> 노드 생성
if(rootNode == null){
rootNode = new Node(element);
}else {
Node head = rootNode;
Node currentNode;
while(true) {
currentNode = head;
// 현재 루트보다 작은 경우, 왼쪽으로 탐색
if(head.value > element){
head = head.leftChild;
// 왼쪽 자식 노드가 비어 있는 경우 -> 해당 위치에 추가할 노드 삽입
// 현재 currentNode는 head를 가리키고 있음
if(head == null) {
currentNode.leftChild = new Node(element);
break;
}
// 현재 루트보다 큰 경우, 오른쪽으로 탐색
else{
head = head.rightChild;
// 오른쪽 자식 노드가 비어있는 경우 -> 해당 위치에 추가할 노드 삽입
if(head == null) {
currentNode.rightChild = new Node(element);
break;
}
}
}
}
System.out.println();
}
}
// 전위 운행(순회)
public void preorderTree(Node root, int depth) {
if(root != null) {
for(int i = 0; i<depth; i++){
System.out.println("ㄴ");
}
System.out.println(root.value); // root
preorderTree(root.leftChild, depth+1); // left
preorderTree(root.rightChild, depth+1); // right
}
}
// 중위 순회 : left - root - right
public void inorderTree(Node root, int depth){
if(root != null){
inorderTree(root.leftChild, depth+1); // left
for(int i = 0; i<depth; i++){
System.out.println("ㄴ");
}
System.out.println(root.value); // root
inorderTree(root.rightChild, depth+1); // right
}
}
// 후위 순회 : left - right - root
public void postorderTree(Node root, int depth){
if(root != null){
postorderTree(root.leftChild, depth+1); // left
postorderTree(root.rightChild, depth+1); // right
for(int i = 0; i<depth; i++){
System.out.println("ㄴ");
}
System.out.println(root.value); // root
}
}
}
BinaryTreeMain.java
package tree;
public class BinaryTreeMain {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.insertNode(5);
tree.insertNode(2);
tree.insertNode(8);
tree.insertNode(1);
tree.insertNode(4);
tree.insertNode(6);
tree.insertNode(10);
tree.insertNode(3);
tree.insertNode(7);
// 트리 순회
tree.preorderTree(tree.rootNode, 0);
System.out.println();
tree.inorderTree(tree.rootNode, 0);
System.out.println();
tree.postorderTree(tree.rootNode, 0);
System.out.println();
// 트리 검색
tree.searchBTree(tree.rootNode, 10);
}
}
