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

이진 트리의 구조를 갖고 있으면서 자료의 검색,삭제,삽입,정렬 등을 효율성을 갖는 트리 자료구조

이진 탐색 트리의 특징

1. 이진 탐색을 보다 쉽게 효과적으로 구현할 수 있게 함

2. 최대값과 최소값을 쉽게 찾을 수 있음

3. 삽입,삭제시에, 올바른 위치를 찾아 곧바로(빠르게) 넣거나 뺄 수 있음

   • 배열의 경우에는, 삽입,삭제시에 매번 다시 정렬을 해야 만 이진 탐색이 가능

4. 검색시 루트 노드부터 시작함

   • 루트 노드부터 시작하여 원하는 키 값을 갖는 원소를 검색

5. 시간복잡도는,

   • 평균적으로, Θ(log n)에 저장,검색 가능
   • 최악의 경우에, O(n)이 걸림

이진 탐색 트리의 구조

1. 최상위 레벨에 루트 노드가 있음
2. 각 노드는, 1개의 키 값 만을 갖음
   • 즉, 키 값이 모두 서로 달라야 함
3. 각 노드는, 최대 2개의 자식 노드를 갖음
   • 이들 각각을 가리키는 최대 2개의 포인터를 갖음
4. 각 노드의 키 값은 크기 순서가 있게 됨
   • (순서 앞섬) 왼쪽 자식 노드 => 부 노드 => 오른쪽 자식 노드 (순서 뒤짐)
     • 즉, 왼쪽 자식 노드 값 < 부모 노드 값 < 오른쪽 자식 노드 값

이진 탐색 트리의 개선 : 균형 잡힌 이진 탐색 트리

1. AVL 트리 (AVL Tree, Adelson-Velskii and Landis's Tree)

   • 한 노드를 중심으로 좌우 부분의 트리 높이(height)의 차가 1 이하가 되도록 함

   • 가장 초기에 나온 균형 잡힌(Balanced) 이진 탐색 트리 임

2. B 트리 (B-Tree, Balanced Tree)

   • 균형 잡힌 이진 탐색 트리를 보다 일반화시킨 트리 자료구조를 말함

   • 데이터베이스 및 파일시스템에 널리 쓰이는 자료구조