[자료구조] Binary Search Tree

• 본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다.
• 따라서 완벽하지 않은 부분이 있을 수 있습니다.
• 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다.

Skip List

• 링크드 리스트에서 중간으로 향하는 포인터를 두고 이를 활용해 이진탐색처럼 활용할 수 있도록 구성한 리스트
• 하지만 insert, delete 등의 기능을 사용하면서도 이러한 조건을 유지하기란 쉽지 않다.
• 데이터가 바뀌지 않을 때만 한정적으로 사용하기에도 적절치 않다. 배열이 더 효율적이다.
• 더 좋은 자료구조가 없을까?

Binary Search Tree (BST)

class Node {
    int k; // key값
    Node *l, *r; // child 노드 정보

• 트리의 일종으로서, 각 노드가 모여서 하나를 이룬다.
• 노드는 key값(데이터)를 보유한다.
• root 노드가 존재한다.
• left, right chid를 보유한다.
• 각각의 child는 sub tree의 root 노드이다.
• 각각의 sub tree도 하나의 BST가 된다.
• 왼쪽은 root 노드보다 key값이 작고 오른쪽은 root 노드보다 key값이 크다.

BST Search

Node* Search (Node *N, int X) {
    if (N == NULL) return NULL;
    if (N->k == X) return N;
    if (N->k < X) return Search(N->r, X);
    else if (N->k > X) return Search(N->l, X);
}

• Node* N은 대상노드, X는 찾는 key값을 의미한다. 현 노드의 key값과 X를 비교하고, 동일하면 현재 노드를 리턴하고 X가 더 크면 Right child로, X가 더 작으면 Left child로 간다.
• 증명 : "만약 노드 안의 key값이 X와 일치하면 해당 노드의 주소를 리턴하고, 아니면 Fail을 리턴한다."에 대한 증명. 우선 key값이 X와 일치하면 if문이 있으므로 당연히 해당 노드의 주소가 리턴된다. X가 현재 key값보다 크다면 X는 무조건 right child의 tree에 존재하고 그 곳에 없다면 존재하지 않는 것이다. X가 현재 key값보다 작다면 X는 무조건 left child의 tree에 존재하고 그 곳에 없다면 존재하지 않는 것이다.
• 성능 : root에서 제일 멀리 갈 수 있는 거리를 height라고 한다. (root를 포함하기도 하고, 포함하지 않기도 하지만 교수님은 포함시켰음) 노드 갯수에 비해 height는 빨리 증가하지 않는다. 다만 같은 노드들로도 어떻게 표현하느냐에 따라 height를 많이 늘릴 수 있다. 잘 정돈된 형태라면 height는 O(log N)의 길이를 가지지만, 아니라면 O(N)의 길이를 가진다. N개의 노드가 한 방향으로만 나열되면 height가 N이 될 것이므로 이 부분은 직관적으로 납득된다. 하지만 O(log N)은 바로 이해가 가지 않을 수 있다. 트리가 잘 정돈되어 있다면, 한번 child를 이동할 때마다 절반이 잘리게 된다. 따라서 Binary Search를 할 때와 같이 logN이면 길이 탐색이 끝나게 되는 것이다.

BST Insert

Node* Insert (Node* N, int X) {
    Node *P;
    while (1) {
        if (N == NULL) {
            N = new Node; N->l = NULL; N->r = NULL; N->k = X; 
            return N;
        }
        if (N->k == X) return NULL;
        if (N->k < X) {
            if (N->r == NULL) {
                P = new Node; P->l = NULL; P->r = NULL; P->k = X;
                N->r = P;
                return P;
            } else {
                N = N->r;
            }
        }
        else if (N->k > X) {
            if (N->r == NULL) {
                P = new Node; P->l = NULL; P->r = NULL; P->k = X;
                N->l = P;
                return P;
            } else {
                N = N->l;
            }
        }
    }
}

• Search와는 다르게 반복문을 통해 구현했다. 이 역시 재귀로 구성할 수 있고, Search 역시 반복문으로도 구현할 수 있다. 처음부터 대상 노드 N을 NULL을 전달했을 경우 바로 넣어줄 수 있도록 처리한다. 그 외엔 자식노드 탐색 후 비어있으면 X를 key값으로 하는 P노드를 해당 위치에 넣어주는 방식으로 처리한다. 물론 X에 해당하는 key값을 가진 노드가 이미 존재한다면 Fail이다.
• 증명 : "서브트리로 내려갔을 때, 만약 X가 트리에 존재한다면 그 곳에 있다"를 증명. 있다면 바로 실패처리되고 반복문을 반복하다 NULL을 만나면 그곳에 insert를 해준다.
• 성능 : search만큼의 시간에 새 노드를 만들고 추가하는 상수시간이 소요된다.

BST Delete

int Delete(Node *N, Node *P) {
    if (N->l == NULL && N->r == NULL) {
        if (N == P->l) P->l = NULL;
        else P->r = NULL;
        delete N;
    }
    else if (N->l != NULL && N->r == NULL) {
        if (N == P->l) P->l = N->l;
        else P->r = N->l;
        delete N;
    }
    else if (N->l == NULL && N->r != NULL) {
        if (N == P->r) P->r = N->r;
        else P->l = N->r;
        delete N;
    }
    else {
        Node *NN, *PP;
        NN = N->r;
        PP = N;
        while (N->l != NULL) {
            PP = NN;
            NN = NN->l;
        }
        N->K = NN->K;
        Delete (NN, PP);
    }
}

• Delete도 마찬가지로 Search를 먼저 수행한다. 수행 결과가 fail이면 delete도 fail한다. 수행이 성공하면 해당 노드의 자식 갯수에 따라 케이스가 나뉜다. (위 코드에서는 Search 과정이 빠져있지만 이미 Search를 수행하고 대상 노드와 그 부모노드를 찾아왔다고 가정한다. N은 대상 노드이고 P는 그 부모노드이다.)
• delete와 Delete는 다른 함수임에 유의하자.
• 대상 노드가 자식이 없을 경우 : 그냥 삭제해주면 된다.
• 대상 노드가 자식이 하나 있을 경우 : 삭제 후 해당 자식을 이어붙이면 된다.
• 대상 노드가 자식이 둘 있을 경우 : 자신보다 큰 노드들 중 가장 작은 노드인 Successor노드를 찾아서 그를 활용한다. NN이 그 역할을 한다. (PP는 그의 부모노드이다.) Successor노드와 삭제 대상 노드의 데이터값만 바꾸고 Successor노드를 삭제해버리면 트리 자체에는 오류가 없어지고, 대상 key값은 삭제되므로 그를 활용하는 것이다.
• 증명 : Lemma(사실, 보조정리)로서 "BST의 모든 값에 대해 탐색이 성공한다 if and only if BST는 옳다"를 활용한다. 자식이 없을 경우엔 그냥 삭제이므로 BST값에 대한 탐색이 성공적일 것이고, 자식이 하나 있는 경우도 BST조건을 해치지 않으므로 성공한다. 마지막으로 자식이 둘 있을 경우도 결국 BST의 조건을 해치지 않아 성공한다.
• 성능 : 정렬된 트리의 경우 height에 비례하게 된다. 이는 O(logN)이다. 하지만 정렬된 트리를 가정하지 않고 모든 트리를 고려해 평균값을 따져도 height는 O(logN)이다. 평균이 그럴 뿐 아니라 높은 확률로 O(logN)이다.

Dummy Node

• cf. 트리에서 함수 처리를 좀 더 쉽게 하기 위해 맨 위에 Dummy Node를 만들어놓기도 한다.
• 무한대 혹은 마이너스 무한대를 넣어 활용한다. 물론 무한대라는 값을 코드로 표현할 수는 어려우므로, 해당 트리에서 사용하는 자료형의 최댓값 혹은 최솟값을 활용한다.
• 이는 root노드가 존재하지 않아 생기는 오류나 알고리즘적 복잡함을 해소할 수 있다.