[자료구조&알고리즘] 이진 탐색 트리(1)

※ 이진 탐색 트리(Binary Search Trees)

- 이진 트리의 일종. 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고

오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진 트리임

 

 

정렬된 배열을 이용한 이진 탐색과 비교했을때,

장점으로는 데이터 원소의 추가와 삭제가 비교적 용이

단점으로는 공간 소요가 크다는 점이 있음

 

데이터 표현 - 각 노드는 (key, value) 한 쌍으로 구성되어 있음

이로 인한 특징은 키를 이용해서 검색이 가능하고 보다 복잡한 데이터 레코드로 확장이 가능함

연산의 정의 - insert(key, data) : 트리에 주어진 데이터 원소 추가

remove(key) : 특정 원소를 트리로부터 삭제

lookup(key) : 특정 원소를 검색

inorder() : 키의 순서대로 데이터 원소를 나열

min(), max() : 최소 키, 최대 키를 가지는 원소를 각각 탐색