[자료구조] BS, Splay, AVL, BB

BS(Binary Search, 이진 탐색 트리)

• 특정 데이터의 효과적인 검색을 위해 제한점을 가지는 이진 트리
• 특정 데이터의 검색과 노드의 삽입, 삭제 처리에 효과적인 이진 트리
• 트리를 구성할 때, 데이터의 탐색을 고려하여 구성하므로 탐색에 최적화된 이진 트리
• 키: 탐색, 삽입, 삭제 연산에서 비교의 대상이 되며, 이진 트리 노드에서 데이터를 대표하는 혹은 노드를 특정할 수 있는 값
• 노드 v_i의 키를 k_i라 할 때, 각 노드 v_i가 다음을 만족하는 이진 트리
  • v_i의 왼쪽 서브 트리에 있는 모든 노드의 키 값은 v_i의 키 값보다 작다
  • v_i의 오른쪽 서브 트리에 있는 모든 노드의 키 값은 v_i의 키 값보다 크다
• 중위순회를 통해 같은 순서 데이터를 만들어 낼 수 있는 다양한 BS 트리

BS 트리의 노드 정의

typedef struct BSTnode {
    struct BSTnode* left; // 왼쪽 자식을 위한 포인터
    char key; // 키 값을 위한 문자 배열
    char content[10]; // 데이터 필드
    struct BSTnode* right; // 오른쪽 자식을 위한 포인터
} BSTnode;

BS 트리의 중위 순회

정렬된 순서로 데이터를 출력할 수 있음

void inorderBST(BSTnode* root) {
    if(root != NULL) {
        inorderBST(root -> left);
        printf("%c", root -> key);
        inorderBST(root -> right);
    }
}

BS 트리의 노드 탐색

BSTnode* searchBST(BSTnode* root, char key) {
    if(root == NULL) {
        printf("Error: 값을 찾을 수 없습니다₩n");
        return root;
    }
    if(key == root -> key) return root;
    else if(key < root -> key) SearchBST(root -> left, key);
    else if(key > root -> key) searchBST(root -> right, key);
}

• 트리가 비어 있다면 탐색 실패, 아니면 k와 현재 루트 노드의 키 값 k_i를 비교한다.
• k = k_i 이면 탐색 성공, 이 때 찾은 정점은 v_i이다.
• k < k_i 이면 v_i의 왼쪽 서브 트리를 탐색한다.
  즉, v_i = v_i,left 로 바꾸고 재탐색한다.
• k > k_i 이면 v_i의 오른쪽 서브 트리를 탐색한다.
  즉, v_i = v_i,right 로 바꾸고 재탐색한다.

BS 트리의 노드 삽입 연산

BSTnode* insertBST(BSTnode* root, char key) {
    BSTnode* ptr;
    BSTnode* newNode = (BSTnode*)malloc(sizeof(BSTnode));
    newNode -> key = key;
    newNode -> left = newNode -> right = NULL;

    if(root == NULL) {
        root = newNode;
        return root;
    }

    ptr = root;
    while(ptr) {
        if(key == ptr -> key) {
            printf("Error: 중복값은 허용되지 않습니다!₩n");
            return root;
        } else if(key < ptr -> key) {
            if(ptr -> left == NULL) {
                ptr -> left = newNode;
                return root;
            }
            else ptr = ptr -> left;
        } else {
            if(ptr -> right == NULL) {
                ptr -> right = newNode;
                return root;
            }
            else ptr = ptr -> right;
        }
    }
}

• k = k_i 이면 멈춘다.
• k < k_i 이면 v_i 의 왼쪽 서브 트리에 삽입해야 하므로 v_i = v_i → left로 하고 네번째 과정으로 넘어간다.
• k > k_i 이면 v_i 의 오른쪽 서브 트리에 삽입해야 하므로 v_i = v_i → right로 하고 네번째 과정으로 넘어간다.
• 트리가 비어 있으면 키 k를 가지는 노드를 삽입한다. 그렇지 않으면 다시 k와 현재 루트 노드의 키 k_i를 비교하여 탐색을 반복한다.

BS 트리의 노드 삭제

자식을 하나만 갖는 노드를 삭제하는 경우, 삭제한 노드를 가리키던 포인터가 그 노드의 null이 아닌 서브트리의 루트를 가리키게 할당함

BSTnode* deleteBST(BSTnode* root, char key) {
    if(del -> left == NULL && del -> right == NULL) { // 자식 노드 0개
        if(parent != NULL) {
            if(parent -> left == del) parent -> left = NULL;
            else parent -> right = NULL;
        }
        else root = NULL;
    } else if(del -> left != NULL && del -> right != NULL) { // 자식 노드 2개
        predecessor = del;
        successor = del -> left;

        while(successor -> right != NULL) {
            predecessor = successor;
            successor = successor -> right;
        }
        if(predecessor -> left == successor) predecessor -> left = successor -> left;
        else predececcor -> right = successor -> left;

        del -> key = successor -> key;
        del = successor;
    }else { // 자식 노드 1개
        if(del -> left != NULL) child = del -> left;
        else child = del -> right;

        if(parent != NULL) {
            if(parent -> left == del) parent -> left = child;
            else parent -> right = child;
        }
        else root = child;
    }
}

Splay, AVL, BB(Balanced Tree)

• 이진 탐색 트리의 특징
  • 트리의 구조와 특정 노드에 접근할 확률은 BS 트리의 성능에 영향을 줌
  • 트리의 성능이 구조에 영향을 받음
  • 어떤 노드의 탐색/삽입/삭제를 위한 접근정보를 예측할 수 없는 상황에서는 최적의 BS 트리구조를 결정하기 어려움
• 경험으로 좋은 성능의 BS 트리를 구축하는 방법
  • 자주 탐색하는 키를 가진 노드를 트리의 루트에 가깝게 놓는다 → Splay
  • 트리가 균형이 되도록 유지한다. → BB트리
    즉, 각 노드에 대해 왼쪽과 오른쪽 서브트리가 가능한 한 같은 수의 노드를 같게 한다 → AVL 트리

Splay 트리

• 자주 탐색하는 키를 가진 노드를 루트에 가깝게 위치하도로 구성한 BS 트리
• 가장 최근에 사용한 노드 x가 트리의 루트에 올 때까지 Splay 연산을 반복하여 적용하여 생선된 이진 트리
• Splay 연산: 최근에 접근한 노드 x를 루트에 위치시켜 트리를 재구성하는 연산
  • 노드 x: 최근에 접한 노드
  • 노드 p: x의 부모 노드
  • 노드 g: x의 조부모(부모의 부모) 노드
  • Zig(단일 회전): p가 트리의 루트 노드이면 p와 x의 간선 연결(edge joining)을 회전시킨다.
  • Zig-Zig((두 개의 단일 회전): p가 루트가 아니고 x와 p가 동일하게 왼쪽 자식들 또는 오른쪽 자식들이면 p와 조부모 g와의 간선 연결을 회전시키고 그 다음에 x와 p의 간선 연결을 회전시킨다
  • Zig-Zag(이중 회전): 만약 p가 루트가 아니고 x가 왼쪽 자식, p가 오른쪽 자식(또는 그 반대)이면 x와 p의 간선 연결을 회전시키고 그 다음에 x와 x의 새로운 부모 g와의 간선 연결을 회전시킨다.

AVL 트리(변형 BS 트리)

노드의 삽입과 삭제가 일어날 때, 노드의 키 값과 서브트리의 키 값 사이의 관계를 유지하면서 균형을 유지시키는 것이 쉽지 않음

• AVL 트리의 개념
  • 제한 조건을 완화하여 트리가 완전한 균형이 아닌 것을 허용함
  • 무너진 균형의 정도는 작아야 하고, 평균 탐색 길이도 완전 균형 트리의 탐색 길이와 크게 차이가 나지 않아야 함
  • 거의 완전한 균형 트리의 한 형태로 높이가 균형 잡힌 높이 균형 트리
  • 직접 탐색 성능이 매우 좋음
• AVL 트리의 조건: 왼쪽 서브트리 높이와 오른쪽 서브트리 높이가 최대 1만큼 차이가 남

BB 트리 (bound-balanced)

거의 완전히 균형 잡힌 트리의 다른 종류로 무게가 균형 잡힌 트리