[자료구조] 이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리 (Binary Search Tree)

딕셔너리(Dictionary)는 페어(Pair)의 모음으로, 각 페어는 Key값과 관련된 다른 값들로 이루어져 있다. 일반적인 딕셔너리 구조는 실제로는 그렇지 않음에도 불구하고 중복된 키값이 없다 가정하지만, 이진 탐색 트리에서는 이러한 가정 없이 쉽게 중복 키값에 대해 확장할 수 있는 자료구조이다.

정의

이진 탐색 트리는 이진 트리의 한 종류로써, 다음 조건들을 만족하는 자료구조이다.

① 각 노드는 구분되는 하나의 키값을 갖는다.

② 왼쪽 서브트리의 모든 키값들은 root의 키값보다 작다.

③ 오른쪽 서브트리의 모든 키값들은 root의 키값보다 크다.

④ 왼쪽, 오른쪽 서브트리 각각 또한 이진 탐색 트리이다.

탐색 (Search)

삽입 (Insertion)

삭제 (Deletion)

 

※ 본 게시글은 『Fundamentals of Data Structures in C』 를 참고하여 작성되었습니다.