순차탐색
*순차탐색은 정렬되지 않은 데이터 집합 속에서 원하는 데이터를 찾거나, 구현이 간단해서 데이터의 크기가 적은 곳에서 자주 쓰인다.
*자기구성순차탐색이란 자주 사용되는 항목을 데이터의 앞 쪽에 배치하여 탐색 효율을 높인다.
-전진 이동법: 탐색이 되면 가장 앞에(헤드에) 위치시킨다.
-전위법:탐색된 항목을 바로 이전 항목과 교환한다. ->점진적으로 자주 탐색되는 항목은 앞쪽으로 모이게 된다.
-계수법:원소별 탐색 횟수를 저장해놓고, 탐색 횟수별로 원소의 위치를 재구성하는 방식이다.
이진탐색
*탐색 범위를 1/2씩 줄여나가는 방식이다.
*단, 미리 정렬되어 있어야한다.
탐색과정
1.데이터 집합의 중앙에 있는 요소를 고른다.
2.중앙 요소의 값과 찾고자 하는 값을 비교한다.
3.목표값이 더 크면 오른편에 대해서 이진탐색을, 작다면 왼편에 대해서 이진탐색을 수행한다.
4.찾을때까지 위 과정을 반복한다.
*이진탐색의 성능은 O(logn)이다.
-한번 탐색을 할 때 마다 1/2 , 1/4 , 1/16.. 씩 줄어들게 된다.
-따라서 일반화 식은 1 = n * (1/2)^x 가 되고, 정리하면 1=n/2^x -> x = log2의n 이 된다. 이 뜻은 데이터 수가 아무리 커져도 탐색 소요 시간은 정말 미미하게 증가한다는 의미이다.
int BinarySearch(int list[] , int size , int target ) {
int left;
int right;
int middle;
left=0;
rifht = size-1;
while( left <= right ) { //탐색범위의 크기가 0이 될 때 까지 반복한다.
middle = (left + right) / 2;
if(target == list[middle])
return dataset[middle];
else if (target > list[middle])
left = middle + 1;
else if (target < list[middle])
right = middle -1;
}
return -1;
}
이진탐색트리(Binary Search Tree)
정의
이진탐색을 위한 트리이다.
*이진탐색트리의 각 노드는 왼쪽자식보다 크고, 오른쪽자식보다는 작다.
*따라서 각 노드는 '중앙요소'이다. 중앙요소를 찾아 좌/우의 대소를 비교하여 탐색 범위를 정하고, 또 다시 중앙 요소를 찾아 좌/우의 대소를 비교하는 과정을 반복하는 과정은 이진탐색과 다를 바 없다.
이진탐색트리의 탐색
BSTNode* BST_SearchNode(BSTNode * Tree , ElementType target){
if(Tree == NULL)
return NULL;
if( Tree->Data == Target)
retrun Tree;
else if (Tree->Data > Target)
return BST_SearchNode(Tree->Left , Target);
else if (Tree->Data < Target )
return BST_SearchNode(Tree->Right , Target);
}
이진탐색트리의 삽입
*새 노드가 어느 위치에 삽입 될지가 핵심이다.
void BST_InsertNode ( BSTNode ** Tree , BSTNode * child ) {
if ((*Tree)->Data < Child->Data){
if((*Tree)->Right == NULL)
(*Tree)->Right = Chile;
else
BST_InsertNode(&(*Tree)->Right , Child);
}
else if ((*Tree)->Data > Child -> Data){
if( (*Tree)->Left == NULL)
(*Tree)->Left = child;
else
BST_InsertNode(&(*Tree)->Left, Child);
}
}
이진탐색트리의 삭제
*삭제한 노드의 자식노드의 왼쪽 자식중 가장 큰 노드 or 오른쪽 자식 중 가장 작은 노드를 삭제할 노드의 자리에 대신한다.
BSTNode* BST_RemoveNode (BSTNode * Tree, BSTNode * Parent , ElementType Target){
BSTNode* Removed = NULL;
if(Tree == NULL ) {
return NULL;
}
if( Tree->Data > Target )
Removed = BST_RemoveNode(Tree->Left , Tree, Target);
else if (Tree->Data < Target )
Removed = BST_RemoveNode(Tree->Right , Tree , Target);
else{ /* 목표 값을 찾은 경우 */
Removed = Tree;
/* 단말노드라면 바로 삭제 */
if(Tree->Left == NULL && Tree->Right == NULL){
if(Parent->Left == Tree)
Parent->Left = NULL;
else
Parent->Right = NULL;
}
else{ /* 자식이 양쪽 다 있는 경우 */
if( Tree->Left != NULL && Tree->Right != NULL){
/* 최소값 노드를 찾아 제거한 뒤 현재의 노드에 위치시킨다. */
BSTNode* MinNode = BST_SearchMinNode(Tree->Right);
Removed = BST_RemoveNode(Tree , NuLL , MinNode->Data); /* 대체할 노드의 뒤처리 */
Tree->Data = MinNode->Data;
} else{ /* 자식이 하나만 있는 경우 */
BSTNode* Temp = NULL;
if(Tree->Left != NULL)
Temp = Tree->Left;
else
Temp = Tree->Right;
if(Parent->Left == Tree)
Parent->Left = Temp;
else
Parent->Right = Temp;
}
}
}
}
(코드의 출저는 뇌를 자극하는 알고리즘에서 가져왔지만, 아쉬움이 있는 코드다. 자식이 하나만 있는 경우에 단순히 연결만 해주고 노드 자체를 제거하지는 않는다.)
레드블래트리
*순수(?) 이진탐색트리는 자칫 트리의 모양이 한쪽으로 쏠릴 위험이 있다(정렬된 데이터로 만든다라던가...)
*그럴때 이진탐색트리의 본래 기능을 발휘하기 위해 균형을 맞추는 작업을 해주는데, 이때 레드블랙트리가 등장하게 된다.
구조체부터 알아보자.
typdef struct tagRBTNode {
struct tagRBTNode* Parent;
struct tagRBTNode* left;
struct tagRBTNode* right;
enum { RED , BLACK } Color;
ElementType Data;
} RBTNode;
*레드블랙트리는 다음 규칙을 지킴으로서 균형을 유지한다.
-모든 노드는 빨간색 아니면 검은색이다.
-루트 노드는 검은색이다.
-잎 노드는 검은색이다.(NIL노드, 단말노드에 붙어서 왼,오른 자식을 완성한다.)
-빨간 노드의 자식들은 모두 검은색이다. 하지만 검은색 노드의 자식이 빨간색일 필요는 없다.
-루트 노드에서 모든 잎 노드 사이에 있는 검은 노드의 수는 모두 도일하다.
*레드블랙트리도 이진탐색트리이다. 그렇기에 탐색은 물론 같고, 삽입과 삭제도 연산까지는 모두 같지만 '뒤처리'과정이 추가로 행해진다.
우회전:왼쪽 자식이 부모 노드의 위치로 올라오는것
이때 왼쪽 자식의 오른쪽 자식을 부모의 왼쪽 자식으로 연결한다.
좌회전:오른쪽 자식이 부모 노드의 위치로 올라오는 것
오른쪽 자식의 왼쪽 노드를 부모 노드의 오늘쪽 자식으로 연결한다.
void RBT_RotateRight( RBTNode** Root , RBTNode* Parent){
RBTNode* Leftchild = Parent->Left;
Parent->Left = LeftChile->Right;
if(LeftChild->Right != Nil )
LeftChile->Right->Parent = Parent;
LeftChild->Parent = Parent -> Parent;
if(Parent->Parent == NULL)
(*Root) = LeftChile;
else{
if(Parent == Parent->Parent->Left)
Parent->Parent->Left = LeftChile;
else
Parent->Parent->Right = LeftChile;
}
LeftChild->Right = Parent;
Parent->Parent = LeftChild;
}