알고리즘
이진탐색트리 Binary Search Tree!
bogus919
2013. 8. 3. 00:11
탐색을 위한 트리인데 이진트리이다
부모 노드를 기준으로, 왼쪽 자식은 부모보다 작은값, 오른쪽 자식은 부모보다 큰값을 갖는다
배열에서의 바이너리서치와 마찬가지로 한번씩 비교하면서 탐색 범위를 반씩 줄일 수 있다
배열과 비교해서, 동적으로 데이터의 삽입, 삭제가 이뤄질 수 있다
크게 탐색, 삽입, 삭제 기능이 있는데 삭제가 좀 까다롭다
1. 자식노드가 없는 경우
2. 자식노드가 한개만 있는 경우
3. 자식노드가 두개 있는 경우
1번의 경우, 그냥 삭제하면 된다
2번의 경우, 삭제하려는 노드의 부모와 자식노드를 이어 주기만 하면된다
3번의 경우, 일단 삭제하려는 노드의 오른쪽 하위트리에서 최소값을 갖는 노드를 찾는다
(계속 왼쪽으로 내려갔을때 끝에 있는 노드가 최소노드 이다.)
그 최소노드를 삭제하려는 노드와 바꾼다
(그 최소노드가 삭제하려는거보다 큰 것들 중에서 제일 작으니까 왼쪽하위트리보단 크고, 오른쪽 하위트리보단 작게된다 올ㅋ)
나머지는 아래 소스를 보면 되겠다
각 함수들은 자신의 하위트리에 대해서 자신을 다시 recursive로 호출하는 형태이다
아 한가지 아쉬운점은, 트리가 한쪽으로만 엄청나게 쏠리게 되면 이진탐색이고 뭐고
그냥 리스트랑 다를게 없다. 검색효율이 걍 떨어지게 된다. 그래서 레드블랙트리란게 또 있다
#include "BinarySearchTree.h"
BSTNode* BST_CreateNode(ElementType NewData){
BSTNode* NewNode = (BSTNode*)malloc(sizeof(BSTNode));
NewNode->Left = NULL;
NewNode->Right = NULL;
NewNode->Data = NewData;
return NewNode;
}
void BST_DestroyNode(BSTNode* Node){
free(Node);
}
void BST_DestroyTree(BSTNode* Tree){
if( Tree->Right != NULL ) //오른쪽 자식있으면 똑같이 제거함수 호출해줌
BST_DestroyTree(Tree->Right);
if( Tree->Left != NULL ) //왼쪽자식도 마찬가지
BST_DestroyTree(Tree->Left);
Tree->Left = NULL; //다 없앴으면 NULL로 설정해줌
Tree->Right = NULL;
BST_DestroyNode(Tree); //마지막에 루트노드를 없애줌
}
BSTNode* BST_SearchNode(BSTNode* Tree, ElementType Target){
if( Tree == NULL ) //끝까지 갔는데도없으면 NULL
return NULL;
if( Tree->Data == Target ) //찾는 데이터와 일치하는 값을 갖는 노드를 리턴
return Tree;
else if( Tree->Data > Target ) //찾는값이 현재노드보다 작으면 왼쪽으로
return BST_SearchNode(Tree->Left, Target);
else
return BST_SearchNode(Tree->Right, Target);
}
BSTNode* BST_SearchMinNode(BSTNode* Tree){
if(Tree == NULL)
return NULL;
if( Tree->Left == NULL ) //더이상 왼쪽자식이 없으면 지가 최소값
return Tree;
else
return BST_SearchMinNode( Tree->Left ); //왼쪽새끼 계속 따라가면 최소값나옴
}
void BST_InsertNode(BSTNode* Tree, BSTNode* Child){
if( Tree->Data < Child->Data ){ //현재 노드보다 값이 크면 오른쪽으로
if( Tree->Right == NULL ) //오른쪽자식 없으면 거기다 삽입
Tree->Right = Child;
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 );
}
}
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);
//최소값 노드는 현재노드의 오른쪽 하위트리에서의 최소값노드
//최소값 노드를 먼저 찾은 후 그 노드의 데이터를 갖는 노드를 지운다
//지우면서 트리는 재구성되고, 지운노드(최소값노드)는 다시 MinNode에 저장된다
MinNode = 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;
}
}
}
return Removed;
}
void BST_InorderPrintTree( BSTNode* Node){
if( Node == NULL )
return;
//왼쪽 하위트리 출력
BST_InorderPrintTree( Node->Left );
//루트노드 출력
printf("%d ", Node->Data);
BST_InorderPrintTree( Node->Right);
}