컴공 일기197

Question

순차탐색은 일단, 시간복잡도가 O(N)인 반면... 이진 탐색은 시간복잡도가 O(Log₂N)이기 때문에 훨씬 성능이 좋은 알고리즘이라 할 만합니다. 다만 문제는, 배열로 데이터가 주어진 경우에는 인덱스를 통해서 중앙 요소의 데이터를 구할 수 있고 이를 토대로 간단히 구현 가능하지만, 만약 구조가 링크드 리스트라면, "중앙 요소"를 쉽게 찾아낼 수 없게 된다는 것입니다. 그래서, 링크드리스트 속에서도 이 중앙요소를 판별하기 위해 사용하는 자료구조가 있으니, 그것이 바로 이진 탐색 트리(Binary Search Tree)가 되겠습니다. 이 구조에는 중앙요소를 쉽게 판별하기 위해서 정한 규칙이 몇 가지 있는데, 그건 넘어가도록 하겠습니다. 궁금하시면, 찾아보셔요! 간단하게 말하면, 순열처럼 자료의 크기에 따라 위치시켜야 하는 장소가 정해져 있습니다. 그래야, 중앙에 위치하게 되는 데이터가 무엇인지 알아낼 수 있겠지요? 다음 그림이 바로 그 규칙을 토대로 생성한 이진 탐색 트리의 구조입니다.

여하튼 다시 본론으로 돌아가서, 이진 탐색 트리는 링크드리스트에서 중앙요소를 찾아내기에 굉장히 용이한 자료구조라고 보면 됩니다. 이것을 이용하면, 링크드리스트에서도 얼마든지 이진 탐색이라는 고성능의 알고리즘을 사용할 수 있다는 것입니다. 결국 이진 탐색은 중앙 요소를 경계로 하여 빠르게 원소들을 분별하는 것이 핵심이니까요.

다음은 그냥 예제 코드입니다.

헤더파일 : "Binary.h"

#pragma once

#ifndef BINARY_SEARCH_TREE_H

#define BINARY_SEARCH_TREE_H

#include <stdio.h>

#include <stdlib.h>

typedef struct tagBSTNode

{

struct tagBSTNode* Left;

struct tagBSTNode* Right;

int Data;

}BSTNode;

BSTNode* BST_CreateNode(int Newdata);

void BST_DestroyNode(BSTNode* Node);

void BST_DestroyTree(BSTNode* Tree);

BSTNode* BST_SearchNode(BSTNode* Tree, int Target);

BSTNode* BST_SearchMinNode(BSTNode* Tree);

void BST_InsertNode(BSTNode* Tree, BSTNode* Child);

BSTNode* BST_RemoveNode(BSTNode* Tree, BSTNode* Parent, int Target);

void BST_InorderPrintTree(BSTNode* Node);

#endif

BinarySearchTree.c

#include "Binary.h"

BSTNode* BST_CreateNode(int 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;

Tree->Right = NULL;

BST_DestroyNode(Tree);

}

BSTNode* BST_SearchNode(BSTNode* Tree, int Target)

{

if (Tree == 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, int 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 = 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);

}

main.c

#include "Binary.h"

int main(void)

{

BSTNode* Tree = BST_CreateNode(123);

BSTNode* Node = NULL;

//이진 탐색 트리 규율에 맞게 노드 생성

BST_InsertNode(Tree, BST_CreateNode(22));

BST_InsertNode(Tree, BST_CreateNode(9918));

BST_InsertNode(Tree, BST_CreateNode(424));

BST_InsertNode(Tree, BST_CreateNode(17));

BST_InsertNode(Tree, BST_CreateNode(3));

BST_InsertNode(Tree, BST_CreateNode(98));

BST_InsertNode(Tree, BST_CreateNode(34));

BST_InsertNode(Tree, BST_CreateNode(760));

BST_InsertNode(Tree, BST_CreateNode(317));

BST_InsertNode(Tree, BST_CreateNode(1));

BST_InorderPrintTree(Tree);

printf("\n");

printf("Removing 98....\n");

Node = BST_RemoveNode(Tree, NULL, 98);

BST_DestroyNode(Node);

BST_InorderPrintTree(Tree);

printf("\n");

printf("Inserting 111...\n");

BST_InsertNode(Tree, BST_CreateNode(111));

BST_InorderPrintTree(Tree);

printf("\n");

BST_DestroyTree(Tree);

return 0;

}

코드 실행 결과 :

1 3 17 22 34 98 123 317 424 760 9918

Removing 98....

1 3 17 22 34 123 317 424 760 9918

Inserting 111...

1 3 17 22 34 111 123 317 424 760 9918

루트Root · Accepted Answer

하지만 node의 삽입/삭제가 빈번해서 skewed 이슈가 발생하거나 그걸 해결하기 위한 balancing 연산량이 일정량 이상 필요할경우 순차탐색이 나을수도

컴공 일기197

최근 게시글 · 더보기

오르비 캐스트