알고리즘이론 - 검색트리 (Search Tree) - 미완

1. 기본 용어 정의
레코드 :
 - 개체에 대해 수집된 모든 정보를 포함하고 있는 저장단위
 - ex) 사람의 레코드 (주민번호,이름, 집주소, 집 전화번호, 직장 전화번호, 휴대폰번호, 최종 학력, 연소득, 가종상황 등 의 정보)
필드 :
 - 레코드에서 각각의 정보를 나타내는 부분
 - ex) 위 사람의 레코드에서 각각의 정보를 나타내는 부분
검색키(Search key) 또는 키(key)
 - 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드
 - 키는 하나의 필드로 이루어 질 수도 있고, 두 개 이상의 필드로 이루어질 수도 있다.
검색트리
 - 각 노드가 규칙에 맞도록 하나씩의 키를 갖고있다.
 - 이를 통해 해당 레콛가 저장된 위치를 알수 있다.

2. 이진 검색 트리(BST : Binary Search Tree)

3.1
- 각 노드는 하나씩의 키 값을 갖는다. 각 노드의 키값은 다르다(중복된 키가 있을수 없다)
- 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두개의 자식을 갖는다.
- 임의의 노드의 키값은 자신의 왼쪽 자식 노드의 키값보다 크고, 오른쪽 자식의 키값보다 작다
 ( Left Node < key < Right Node)

3.1.1 삽입
treeInsert(t, x) //t : 트리의 루트노드, x : 삽입하고자 하는 키
{
    if(t = NIL) then {
        key[r] ← x;        // r: 새노드
        return r;
    }
    if(x < key (t))
        then {left[t] ← treeInsert(left[t],x); return t};
        else {right[t] ← treeInsert(right[t],x); return t};
}

3.1.2 삭제
treeDelete(t, r, p)
{
    if( r = t ) then root ← deleteNode(t);    // r이 루트 노드인 경우
    else if( r = left[p])                            // r 이 루트 노드가 아닌경우
        then left[p] ← deleteNode(r);    //r이 p의 왼쪽 자식
        else right[p] ← deleteNode(r);    //r이 p의 오른쪽 자식
}

deleteNode(r)


/. Red-Black 트리 (RB Tree)

3. B - 트리

- 디스크의 접근 단위는 블록(페이지)
- 디스크에 한 번 접근하는 시간은 수십만 명령어의 처리 시간과 맞먹는다.
- 검색트리가 디스크에 저장되어 있다면 트리의 높이를 최소화 하는 것이 유리하다. (벨런스 트리)
- B-트리는 다진검색트리가 균형을 유지하도록 하여 최악의 경우 디스크 접근 횟수를 줄인 것이다.

성질
- 루트를 제외한 모든 노드는 k/2 ~ k 개의 키를 갖는다.
- 모든 리프 노드는 같은 깊이를 가진다.

3.2 B* - 트리
3.3 B+ - 트리

4. KD - 트리

- 한 Level에서는 하나의 필드만 사용한다.
- 총 k 개의 필드를 사용하는 검색이라면, k개의 level을 내려가면 검색에 사용하는 필드가 일치한다.

5. KDB - 트리
- KD-트리의 (다차원 key) 특성과 B-트리(디스크의 한 페이지가 한 노드와 일치 Balanced tree)의 특성을 결합
- 각 레코드는 k 차원 공간에서 하나의 점에 해당 ( 자신이 속한공간을 담당하는 색인 node들을 따라감)

영역노드 :
 - 루트 노드는 k차원 공간 전체를 커버
 - 이하 노드들은 k차원 공간 부분 영역을 담당
 - (영역, 페이지 번호) 을 가짐
 - 같은 level에 있는 모든 노드들은 서로 겹치는 영역이 없다.
 - 같은 elvel에 있는 모든 노드들의 담당 영역을 합치면 k차원 공간 전체가 된다.
 - 리프 노드를 제외한 노드들은 영역노드

키 노드 : 
 - 데이터 레코드를 저장한다.
 - (키, 페이지번호)를 가짐
 - 리프 노드 = 키노드

6. R - 트리

- B트리의 다차원 확장
- 균형잡힌 검색트리 (B트리의 특성을 이어받음)
- 모든 레코드는 리프노드에서만 가리킴
- 다차원 도형의 저장 가능 ( 점, 선 , 면, 폐공간, 각종 도형 ) 
- KDB-트리에선 노드들이 전체 공간을 나누어 커버하는대 반해 키들을 포함하는 최소영역만 노드에 있다.
- 영역 개수의 상한과 하한이 있다.
. 루트를 제외한 모든 내부 노드는 k/2 ~ k개의 영역을 갖는다.
 . 모든 리프노드는 같은 깊이를 가진다.
 . 모든 레코드는 리프노드에서만 가리킨다. 

  영역 노드 : 복수 개의 (영역,페이지 번호)쌍으로 구성, 모든 내부 노드는 영역노드.
  키 노드 : 복수 개의 (키, 페이지 번호)쌍으로 구성, 모든 리프노드는 점(키) 노드다.

기타. 그리드 파일

7. (Point) Quad - 트리( Quadtree )

루트에 대한 하위 노드를 항상 4개로 구성
노드를 배치하는 방법은  NS , WE(동서, 남북) 으로 분류해 NW,NE,SW,SE순으로 배치

8. Oct - 트리 ( Oct Tree)