BST   Binary Search Tree   이진 탐색 트리

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

  ㅇ 검색 트리, 탐색 트리 이란?
     - 데이터를 정렬된 형태로 저장하여, 효율적인 검색,삽입,삭제가 가능하도록 설계된 트리 자료구조

  ㅇ 이진 트리의 구조를 갖음
     - 각 노드가 최대 2개의 자식 노드를 가지며, 규칙적으로 정렬된 노드들을 가짐
        . 각 노드의 왼쪽 서브트리는 작은 값, 오른쪽 서브트리는 큰 값을 가짐
     - 탐색 시간 :  평균  O(log n), 최악 O(n) (불균형할 경우)


2. 이진 탐색 트리의 특징

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

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

  ㅇ 삽입,삭제시에, 올바른 위치를 찾아 곧바로(빠르게) 넣거나 뺄 수 있음
     - 한편, 배열의 경우에는, 삽입,삭제시에 매번 다시 정렬을 해야 만 이진 탐색이 가능해 짐

  ㅇ 검색시에, 루트 노드부터 시작함
     - 이곳부터 시작하여 원하는 키 값을 갖는 원소를 찾아나가는 방식임

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

  ㅇ 이진 탐색 트리는, 가장 기본적인 검색 트리 임
     - 한편, 검색 키가 포함하는 필드 수에 따라, 1차원, 다차원 검색 트리로 구분
        . 1차원 검색 트리 : 이진 검색 트리, 다진 검색 트리, B 트리, AVL 트리, 레드블랙 트리 등
        . 다차원 검색  트리 : KD 트리, KDB 트리, R 트리 등


3. 이진 탐색 트리의 구조

  ㅇ 최상위 레벨에 루트 노드가 있음

  ㅇ 각 노드는, 1개의 키 값 만을 갖음 
     - 또한, 키 값이 모두 서로 달라야 함

  ㅇ 각 노드는, 최대 2개의 자식 노드를 갖음
     - 따라서, 이들 각각을 가리키는 최대 2개의 포인터를 갖음

  ㅇ 각 노드의 키 값은, 크기 순서가 있게 됨
     - (순서 앞섬) 왼쪽 자식 노드 => 부 노드 => 오른쪽 자식 노드 (순서 뒤짐)
        . 즉, 왼쪽 자식 노드 값 < 부모 노드 값 < 오른쪽 자식 노드 값
     - 例) 부모 왼쪽의 자식 노드들은, 부모 보다 앞서는(작은값) 노드들을 포함
     - 例) 부모 오른쪽 자식 노드들은, 부모 보다 뒤지는(큰값) 노드들을 포함
        


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

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

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

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

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

  ㅇ 레드 블랙 트리 (Red-Black Tree)
     - 균형 유지를 위해 추가적인 규칙을 적용한, 자기 균형 이진 탐색 트리 (Self-Balancing BST)
     - 특징 (5가지 규칙)
        . 각 노드는, 빨간색(Red) 또는 검은색(Black)
        . 루트 노드는, 항상 검은색
        . 모든 리프 노드는, 검은색
        . 빨간색 노드는, 연속해서 등장할 수 없음
           .. 즉, 빨간색 노드의 부모와 자식은 반드시 검은색
        . 어떤 노드에서든, 모든 리프 노드까지의 검은색 노드 개수(Black Height)는 동일