이번에는 재귀 알고리즘으로 구현하는 이진 탐색 트리를 알아봅시다. 이진 탐색 트리는 검색 효율을 높이기 위해 만들어진 트리입니다.
이진 탐색 트리를 살펴보기 전에 먼저 트리가 무엇인지 살펴보기로 해요.
트리는 대표적인 비선형 자료구조입니다. 비선형 자료구조는 자료를 보관하는 구조를 하나의 선의 형태로 표시할 수 없는 자료구조를 말하며 트리와 그래프 등이 있습니다.
그 중에 트리는 뿌리에서부터 계층적으로 자료를 보관하는 자료구조입니다. 트리는 방향성 있는 그래프로 표현하며 사이클이 존재하지 않고(ACycle) 고립 상태가 없는(No Island) 자료구조입니다.
트리는 다음처럼 루트와 서브 트리의 집합으로 정의할 수 있습니다.
Tree = {root , sub trees} sub tree is tree
그리고 트리는 다음처럼 정의할 수도 있습니다.
Tree 는 방향성 있는 그래프이며 사이클이 존재하지 않고 고립 상태가 없는 자료구조
