[알고리즘] 이진탐색트리

이진검색트리 ( binary search tree)

기본적으로 레코드는 데이터를 저장하는 필드를 가지고 있다.
그리고 다른 레코드와의 구분을 위해 한개 그이상의 필드 조합으로 이루어진 필드를 검색키 또는 키 라고한다.

이진검색트리를 탐색에 사용하기 위한 몇가지 특성(조건)을 가지고있다.

1.이진트리의 각 노드는 키값을 하나씩 갖는다. 각노드의 키값은 중복되지 않는다.
2.최상위 레벨에 루트노드가 있고, 각 노드는 최대 두개의 자식노드를 갖는다.
3.임의의 노드의 키값은 자신의 왼쪽 자식노드의 키값보다 크고, 오른쪽 자식 노드의 키값 보다 작다.

탐색방법
    입력 : 루트노드와 찾고자하는 키값
    1.루트노드 = 키값 => 루트 반환
    2.키값이 루트보다 작으면 왼쪽탐색, 키값이 루트보다 크면 오른쪽 탐색
    3.반복

    탐색시간
    최악의 경우 (ㅇ-ㅇ-ㅇ-ㅇ 과 같이 일자형 구조로 이루어진경우) Θ(n)의 시간이 걸린다.
    최적의 경우 (힙의 모양) Θ(log n)의 시간이 걸린다. (트리의 높이만큼의 시간)
     ex) 4~7개의 노드로 이루어진 힙의 구조를 가진 BST에서는 높이가 트리의 높이가 3임으로 총 2의
       탐색시간이 걸린다.

삽입
    입력 : 루트노드와 삽입하고자 하는 노드의 키값
    1. 루트노드 키값이 작으면 왼쪽, 크면 오른쪽 탐색
    2. 반복 후 리프노드 도달시 리프노드보다 크면 왼쪽, 크면 오른쪽에 삽입
     (힙의 구조가 아니기 때문에 별다른 트리의 수정이 필요하지 않다.)

삭제
   입력 : 루트노드와 삭제하고자 하는 노드의 키값
   1. 삭제하고자 하는 키값을 탐색
   2. 삭제
     2-1 삭제하고자 하는 키값이 리프노드일 경우 : 바로 삭제
     2-2 삭제하고자 하는 키값이 자식을 하나 가질 경우
         :해당 노드를 삭제한 후 그 자식을 삭제한 노드 위치에 배치한다.
     2-3 삭제하고자 하는 키값이 자식을 둘 가질 경우
         :해당 노드를 삭제하고
         1.왼쪽 자식 중 가장 큰값으로 대체하거나
         2. 오른쪽 자식중 가장 작은 값으로 대체한다.
         3. 대체한 값(가장 크거나 작은)이 역시 자식노드를 가지고 있다면 2-3의 과정을 반복한다.