이진 탐색 트리 (Binary Search Tree)

I. 평균 탐색 속도 보장, 이진 탐색 트리의 개요

이진 탐색 트리의 개념

중복된 노드가 없고, 왼쪽 서브 트리에는 작은 값, 오른쪽 서브 트리에는 큰 값으로 구성되는 이진 트리

이진 탐색 트리의 특징

  • O(log N)의 평균 탐색 속도 보장
  • 삽입/삭제 시 트리 재구성 필요

II. 이진 탐색 트리의 데이터 삽입 과정

이진 탐색 트리 데이터 삽입 알고리즘

단계설명
1단계– 전체 트리에서 삽입하고자 하는 값 존재 탐색
2단계– 탐색 성공 시, 해당 값이 존재하므로 삽입 종료
3단계– 탐색 실패 시 부모 노드가 NULL이면 해당 노드에 값 삽입
4단계– 부모 노드 값과 비교하여 작으면 왼쪽, 크면 오른쪽 서브 노드로 삽입
  • 전위/중위/후위 등 일정한 규칙 기반 트리 탐색 후 삽입 수행

이진 탐색 트리 데이터 삽입 과정 상세 설명

단계삽입 과정설명
1단계– 삽입하고자 하는 키 값이 루트 노드의 키 값보다 작으므로 왼쪽 서브 트리 탐색
2단계– Level2의 왼쪽 서브 노드 키 값과 비교

– 삽입하려는 키 값이 크므로 오른쪽 서브 트리 탐색

3단계– Level3의 오른쪽 서브 노드의 키 값과 비교

– 삽입하려는 값이 크므로 오른쪽 서브 트리 탐색

– 탐색 시도한 서브 트리가 NULL이므로 삽입

III. 이진 탐색 트리의 구현 사례(C언어)

Node 자료 구조삽입코드
typedef struct Node {

struct Node* Left;

struct Node* Right;

int Data;

} Node;

void insertNode(Node** Tree, Node* newNode)

{

Node* tmpNode = *Tree;

if (tmpNode == NULL) tmpNode = newNode;

else if (tmpNode->Data > newNode->Data)

insertNode(&tmpNode->Left, newNode);

else if (tmpNode->Data < newNode->Data)

insertNode(&tmpNode->Right, newNode);

*Tree = tmpNode;

}

 

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^