[자료구조] BST(binary search tree , 이진탐색트리) 구현

소개글

BST 의 기본적인 search , insert , delete 가 class로 구현되어 있다.

목차

Binary Search Tree (BST,이진탐색트리)

정의

검색

삽입

삭제

본문내용

Binary Search Tree (BST,이진탐색트리)

정의1) : 이진탐색트리는 이진트리이다. 트리는 빈 트리 일 수 있으며, 비어있지 않을경우, 아래의 4
가지 속성을 만족한다.
(1) 원소의 키 값을 유일하다. (다른 원소의 키 값과 다르다.)
(2) 비어있지 않은 왼쪽 서브트리의 키 값은 서브트리의 루트(부모)의 키 값보다 더 작아야한다.
(3) 비어있지 않은 오른쪽 서브트리의 키 값은 서브트리의 루트(부모)의 키 값보다 더 커야한다.
(4) 왼쪽과 오른쪽 서브트리는 또한 이진트리이어야 한다.

검색(Search)
(1) 키 값이 같은 경우, 성공
(2) 키 값이 부모보다 더 작은 경우, 왼쪽 서브트리
(3) 키 값이 부모보다 더 큰 경우, 오른쪽 서브트리
(4) 노드 값이 널일경우 실패, 아닐경우 반복.

삽입(Insert)
(1) 빈 트리일 경우, 루트에 삽입
(2) 아닐 경우 아래의 규칙을 따른다.
(가) 키 값이 부모보다 더 작은 경우, 왼쪽 서브트리
(나) 키 값이 부모보다 더 큰 경우, 오른쪽 서브트리
(다) 노드가 NULL일 경우 삽입, 아닐 경우 반복.

참고 자료

Fundamentals of Data Structure In C , Freeman and Company , 1993 , Ellis Horowitz etc

압축파일 내 파일목록

Binary Search Tree.docx
BST.sln
BST/BST.cpp
BST/BST.h
BST/BST.vcproj
BST/sample.cpp