이진 탐색 트리

탐색이란?

컴퓨터 프로그램에서 탐색은 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업을 의미한다.

레코드는 하나 이상의 필드(field)로 구성된다. 예컨대 학생의 레코드는 이름, 주소, 주민등록번호 등의 필드들로 이루어진다. 일반적으로 레코드들의 집합을 테이블(table)이라고 한다.

레코드들은 보통 키(key)라고 불리는 하나의 필드에 의해 식별할 수 있다. 키는 서로 중복되지 않는 고유한 값을 가지는데, 키를 사용하면 각각의 레코드들을 구별할 수 있다. 이러한 키를 주요키(primary key)라고 한다.

Untitled

이진 탐색 트리란?

이진 탐색 트리는 이진트리 기반의 탐색을 위한 자료구조로 효율적인 탐색 작업을 위한 자료구조이다. 이진 탐색 트리는 특별한 성질을 만족하는 이진트리를 말하는데, 다음과 같이 순환적으로 정의된다.

Untitled

Untitled

이진 탐색 트리의 추상 자료형

이진 탐색 트리의 연산

탐색 연산

이진 탐색 트리에서 어떤 탐색키를 가진 노드를 찾기 위해서는 먼저 주어진 탐색키와 현재의 루트 노드의 키 값을 비교해야 한다.