1. 이진 검색 트리 정의

이진 검색 트리 (BST) 정의:

  • BST (Binary Search Tree): 내부 노드의 키가 해당 노드의 왼쪽 서브트리의 모든 키보다 크고 오른쪽 서브트리의 모든 키보다 작은 이진 트리.
  • 시간 복잡도: BST에서의 연산 시간 복잡도는 트리의 높이에 비례.

특징:

  • 빠른 탐색, 추가 및 삭제를 위한 이진 검색 트리.
  • 각 비교에서 남은 트리의 약 절반을 건너뛰기 때문에 검색 성능은 이진 로그와 비례.

2. 이진 검색 트리 연산

연산:

  • IsEmpty(): 트리가 비어있는지 확인.
  • Search(key): 주어진 키로 노드를 검색.
  • Insert(key, value): 주어진 키와 값을 삽입.
  • Delete(key): 주어진 키를 삭제.

복잡도:

  • 검색, 삽입, 삭제 연산의 최악의 경우 시간 복잡도는 O(n), 기대 시간 복잡도는 O(log n) (n은 요소의 수).

3. 요소 검색

요소 검색 알고리즘:

tree_pointer search(tree_pointer t, int x) {
    if (t == NULL)
        return NULL; // 요소를 찾지 못함
    else if (x == t->key)
        return t; // 요소를 찾음
    else if (x < t->key)
        return search(t->leftchild, x); // 왼쪽 서브트리 검색
    else
        return search(t->rightchild, x); // 오른쪽 서브트리 검색
}

반복적 요소 검색 알고리즘:

tree_pointer search(tree_pointer t, int x) {
    while (t) {
        if (x == t->key)
            return t;
        if (x < t->key)
            t = t->leftchild;
        else
            t = t->rightchild;
    }
    return NULL;
}


4. 요소 삽입

요소 삽입 알고리즘:

void insert_node(tree_pointer *node, int num) {
    tree_pointer ptr, temp = modified_search(*node, num);
    if (temp || !(*node)) {
        ptr = (tree_pointer)malloc(sizeof(tree_pointer));
        if (!ptr) {
            fprintf(stderr, "Memory allocation failed\n");
            exit(1);
        }
        ptr->data = num;
        ptr->leftchild = ptr->rightchild = NULL;
        if (*node) {
            if (num < temp->data)
                temp->leftchild = ptr;
            else
                temp->rightchild = ptr;
        } else {
            *node = ptr;
        }
    }
}


5. 요소 삭제

삭제 연산:

  • 네 가지 경우:
    1. 삭제할 키가 없는 경우.
    2. 삭제할 요소가 리프인 경우.
    3. 삭제할 요소가 차수가 1인 노드인 경우.
    4. 삭제할 요소가 차수가 2인 노드인 경우.

리프에서 삭제:

  • 예제: key = 7을 삭제

--추가하기

차수가 1인 노드에서 삭제:

  • 예제: key = 40을 삭제

차수가 2인 노드에서 삭제:

  • 예제: key = 10을 삭제
    • 왼쪽 서브트리의 가장 큰 키 또는 오른쪽 서브트리의 가장 작은 키로 교체.


6. 인덱스된 이진 검색 트리 (Indexed Binary Search Tree)

정의:

  • 각 노드에 추가 필드가 있는 이진 검색 트리.
    • leftSize: 왼쪽 서브트리에 있는 노드의 수.

leftSize와 순위 (Rank):

  • 요소의 순위는 중위 순회 순서에서의 위치.
  • 예제:
    • rank(2) = 0
    • rank(15) = 5
    • rank(20) = 7

검색 및 삭제 연산:

  • index = x.leftSize일 때 원하는 요소는 x.element.
  • index < x.leftSize일 때 원하는 요소는 x의 왼쪽 서브트리에서 index 번째 요소.
  • index > x.leftSize일 때 원하는 요소는 x의 오른쪽 서브트리에서 (index - x.leftSize - 1) 번째 요소.

7. 승자 트리 (Winner Trees)

정의:

  • n개의 외부 노드와 n-1개의 내부 노드로 구성된 완전 이진 트리.
  • 외부 노드는 토너먼트 선수들을 나타냄.
  • 각 내부 노드는 두 자식 사이의 경기를 나타내며, 승자가 저장됨.

승자 트리 초기화:

  • 각 매치 노드에서 경기 수행: O(1)
  • n-1개의 매치 노드: O(n)

응용:

  • 정렬: 요소들을 승자 트리에 삽입 후, 승자를 반복적으로 추출하고 큰 값으로 대체.

복잡도:

  • 초기화: O(n)
  • 승자 얻기: O(1)
  • 승자 제거/대체 후 재경기: O(log n)

8. 패자 트리 (Loser Trees)

정의:

  • 각 매치 노드에 경기의 패자가 저장되는 트리.

패자 트리 초기화:

  • 각 매치 노드에서 경기 수행: O(n)

복잡도:

  • 재경기: O(log n)