BST   Binary Search Tree   이진 탐색 트리

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

  ㅇ 이진 트리의 구조를 갖으나, 자료의 검색,삭제,삽입,정렬 등에 효율적이게 한 트리 자료구조


2. 이진 탐색 트리의 특징

  ㅇ 이진 탐색을, 보다 쉽게 효과적으로 구현할 수 있게 함
  ㅇ 최대값과 최소값을 쉽게 찾을 수 있음

  ㅇ 삽입,삭제시에, 올바른 위치를 찾아 곧바로(빠르게) 넣거나 뺄 수 있음
     - 한편, 배열의 경우에는, 삽입,삭제시에 매번 다시 정렬을 해야 만 이진 탐색이 가능해 짐
  ㅇ 검색시에, 루트 노드부터 시작함
     - 이곳부터 시작하여 원하는 키 값을 갖는 원소를 찾아나가는 방식임

  ㅇ 시간복잡도는, 
     - 평균적으로, Θ(log n)에 저장,검색 가능
     - 최악의 경우에, O(n)이 걸림


3. 이진 탐색 트리의 구조

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


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

  ㅇ AVL 트리 (AVL Tree, Adelson-Velskii and Landis's Tree)
     - 한 노드를 중심으로 좌우 부분의 트리 높이(height)의 차가 1 이하가 되도록 함

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

  ㅇ B 트리 (B-Tree, Balanced Tree)
     - 균형 잡힌 이진 탐색 트리를 보다 일반화시킨 트리 자료구조를 말함

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