[자료구조] #17 Binary Search Tree(2)

BST(1)에서 슈도코드로 다뤘던 것들을 이제 C++ 코드로 살펴보자.

 

• BinaryNode Class

class BinaryNode {
    // BinarySearchTree 클래스가 BinaryNode의 private 멤버에 접근할 수 있도록 설정
    friend class BinarySearchTree;
private:
    int key;  // 노드의 키 값
    int value;  // 노드의 데이터 값
    BinaryNode* left;  // 왼쪽 자식 노드에 대한 포인터
    BinaryNode* right;  // 오른쪽 자식 노드에 대한 포인터

public:
    // 생성자: 키, 값, 왼쪽 자식 포인터, 오른쪽 자식 포인터를 초기화
    BinaryNode(int key = 0, int value = 0, BinaryNode* left = nullptr, BinaryNode* right = nullptr) {
        this->key = key;  // 키 값 설정
        this->value = value;  // 데이터 값 설정
        this->left = left;  // 왼쪽 자식 포인터 설정
        this->right = right;  // 오른쪽 자식 포인터 설정
    }
    // 키, 값, 왼쪽 자식, 오른쪽 자식에 대한 getter와 setter 메소드

    // 현재 노드가 리프 노드인지 확인 (자식이 없는 경우)
    bool isLeaf() {
        return this->left == nullptr && this->right == nullptr;
    }

    // 현재 노드가 두 개의 자식을 가지고 있는지 확인
    bool hasTwoChildren() {
        return this->left != nullptr && this->right != nullptr;
    }

    // 현재 노드가 한 개의 자식만 가지고 있는지 확인
    bool hasOneChild() {
        bool hasOnlyLeft = this->left != nullptr && this->right == nullptr;
        bool hasOnlyRight = this->left == nullptr && this->right != nullptr;
        return hasOnlyLeft || hasOnlyRight;
    }
};

 

• BinaryTree Class

class BinaryTree {
protected:
    BinaryNode* root;  // 트리의 루트 노드를 가리키는 포인터

public:
    // 기본 생성자: 트리를 비어 있는 상태로 초기화
    BinaryTree() { this->root = nullptr; }

    // 소멸자: 트리의 모든 노드를 제거
    ~BinaryTree() {
        removeNodes(this->root);
    }

    // 트리가 비어 있는지 확인
    bool empty() { return this->root == nullptr; }

    // 다음과 같은 기능은 구현되어 있다고 가정:
    // - 전위 순회 (preorder), 중위 순회 (inorder), 후위 순회 (postorder), 레벨 순회 (levelorder)
    // - 노드 수 세기 (getCount), 리프 노드 수 세기 (getLeafCount), 트리 높이 계산 (getHeight)
    // - 노드 제거 (removeNodes)
};

class BinarySearchTree : public BinaryTree {
public:
    // 키를 검색하여 성공하면 노드의 값을 반환
    int search(int key) {
        // 검색 기능 구현
    }

    // 주어진 키와 값을 트리에 삽입
    void insert(int key, int value) {
        // 삽입 기능 구현
    }

    // 주어진 키를 가진 노드를 트리에서 제거
    void remove(int key) {
        // 제거 기능 구현
    }
};

 

• Search

// API
public:
int search(int key) {
    BinaryNode* node = search(this->root, key);  // 루트 노드에서 검색 시작
    if (node == nullptr) throw "error: out-of-key";  // 키를 찾지 못하면 예외 발생
    return node->value;  // 키를 찾으면 해당 노드의 값을 반환
}

// Worker fuction
private:
BinaryNode* search(BinaryNode* node, int key) {
    if (node == nullptr || key == node->key)  // 노드가 NULL이거나 키를 찾으면
        return node;  // 해당 노드를 반환
    else if (key < node->key)  // 찾는 키가 현재 노드의 키보다 작으면
        return search(node->left, key);  // 왼쪽 자식에서 검색
    else  // 찾는 키가 현재 노드의 키보다 크면
        return search(node->right, key);  // 오른쪽 자식에서 검색
}

 

여기서 잠깐! API와 Worker이란?

 

API (search(int key))

클래스 외부에서 호출할 수 있는 공용 메소드로 사용자가 키를 검색할 수 있는 기능을 제공한다.

키가 없을 경우 예외를 발생시킨다.

 

Worker function (search(BinaryNode* node, int key))

내부에서 호출되는 비공용 메소드이다.

재귀적으로 트리를 탐색하여 키를 찾는 작업을 수행한다.

 

요약하면, API는 사용자와 시스템 간의 인터페이스를 제공하고, 워커 함수는 시스템 내에서 실제 작업을 수행한다고 할 수 있다.

 

• Insert

// API
public:
void insert(int key, int value) {
    // 트리가 비어 있는지 확인
    if (empty()) {
        // 트리가 비어 있으면 새로운 루트 노드를 생성
        this->root = new BinaryNode(key, value);
    } else {
        // 트리가 비어 있지 않으면 재귀적으로 삽입
        insert(this->root, key, value);
    }
}

// Worker
private:
void insert(BinaryNode* node, int key, int value) {
    // 삽입하려는 키가 현재 노드의 키와 같으면 값을 업데이트
    if (key == node->key) {
        node->value = value;
    } 
    // 삽입하려는 키가 현재 노드의 키보다 작으면 왼쪽 자식으로 이동
    else if (key < node->key) {
        if (node->left == nullptr) {
            // 왼쪽 자식이 없으면 새로운 노드를 생성하여 삽입
            node->left = new BinaryNode(key, value);
        } else {
            // 왼쪽 자식이 있으면 재귀적으로 삽입
            insert(node->left, key, value);
        }
    } 
    // 삽입하려는 키가 현재 노드의 키보다 크면 오른쪽 자식으로 이동
    else {
        if (node->right == nullptr) {
            // 오른쪽 자식이 없으면 새로운 노드를 생성하여 삽입
            node->right = new BinaryNode(key, value);
        } else {
            // 오른쪽 자식이 있으면 재귀적으로 삽입
            insert(node->right, key, value);
        }
    }
}

 

• Remove

// API
public:
void remove(int key) {
    // 주어진 키를 가진 노드를 제거하고, 제거된 노드를 반환받음
    BinaryNode* node = remove(this->root, nullptr, key);
    if (node == nullptr) {
        // 키를 찾지 못하면 예외 발생
        throw "error: out-of-key";
    }
    // 제거된 노드를 삭제
    delete node;
}

// Worker
private:
BinaryNode* remove(BinaryNode* node, BinaryNode* parent, int key) {
    if (node == nullptr) {
        // 노드를 찾지 못한 경우
        return nullptr;
    }
    if (key < node->key) {
        // 키가 현재 노드의 키보다 작으면 왼쪽 자식에서 제거
        return remove(node->left, node, key);
    } else if (key > node->key) {
        // 키가 현재 노드의 키보다 크면 오른쪽 자식에서 제거
        return remove(node->right, node, key);
    } else {
        // 키가 현재 노드의 키와 같은 경우
        if (node->hasTwoChildren()) {
            // 두 자식이 있는 경우 (case 3)
            // 두 자식이 있을 때의 처리 (예: 후속자 찾기)
        } else if (node->hasOneChild()) {
            // 한 자식만 있는 경우 (case 2)
            // 한 자식만 있을 때의 처리
        } else if (node->isLeaf()) {
            // 자식이 없는 경우 (case 1)
            // 리프 노드일 때의 처리
        }
        return node; // 제거된 노드를 반환
    }
}

 

Remove - Case 1

// case 1: node to be removed is a leaf (삭제할 노드가 리프 노드인 경우)
else if (node->isLeaf()) {
    if (node == this->root) {
        // 삭제할 노드가 루트 노드인 경우, 루트 노드를 nullptr로 설정
        this->root = nullptr;
    } else {
        // 삭제할 노드가 루트 노드가 아닌 경우
        if (parent->left == node) {
            // 삭제할 노드가 부모 노드의 왼쪽 자식인 경우
            parent->left = nullptr;
        } else {
            // 삭제할 노드가 부모 노드의 오른쪽 자식인 경우
            parent->right = nullptr;
        }
    }
    // 삭제된 노드를 반환
    return node;
}

 

Remove - Case 2

 

// case 2: node has only one child (삭제할 노드가 하나의 자식만 가진 경우)
else if (node->hasOneChild()) {
    // 삭제할 노드의 자식 노드를 찾습니다.
    BinaryNode* child = (node->left != nullptr) ? node->left : node->right;
    if (node == this->root) {
        // 삭제할 노드가 루트 노드인 경우, 자식 노드를 새로운 루트로 설정합니다.
        this->root = child;
    } else {
        // 삭제할 노드가 루트 노드가 아닌 경우
        if (parent->left == node) {
            // 삭제할 노드가 부모 노드의 왼쪽 자식인 경우, 자식 노드를 왼쪽 자식으로 설정합니다.
            parent->left = child;
        } else {
            // 삭제할 노드가 부모 노드의 오른쪽 자식인 경우, 자식 노드를 오른쪽 자식으로 설정합니다.
            parent->right = child;
        }
    }
    // 삭제된 노드를 반환합니다.
    return node;
}

 

Remove - Case 3

// case 3: node has two children (삭제할 노드가 두 개의 자식을 가진 경우)
if (node->hasTwoChildren()) {
    // 후속자(successor)를 찾습니다. 
    BinaryNode* succ = leftmost(node->right);
    // 삭제할 노드의 키와 값을 후속자의 키와 값으로 대체합니다.
    node->key = succ->key;
    node->value = succ->value;
    // 후속자를 제거합니다.
    succ = this->remove(node->right, node, succ->key);
    // 삭제된 후속자를 반환합니다.
    return succ;
}

// 주어진 노드의 서브트리에서 가장 왼쪽에 있는 노드를 찾는 함수
BinaryNode* leftmost(BinaryNode* node) {
    // 주어진 노드의 왼쪽 자식이 nullptr이 될 때까지 반복하여 실행
    while (node->left != nullptr) {
        // 현재 노드를 왼쪽 자식으로 이동하여 왼쪽 자식 노드로 이동
        node = node->left;
    }
    // 가장 왼쪽에 있는 노드를 반환
    return node;
}

 

• BST의 시간복잡도 분석

 

search 연산의 시간복잡도

최선의 경우 : 루트에 탐색키가 있는 경우 → O(1)

최악의 경우 : 탐색키가 트리의 가장 깊은 리프토드에 있는 경우 → O(h) (h는 트리의 높이)

 

Insert/remove 연산의 시간복잡도

탐색 후 노드를 삽입하는 과정 : O(1)

탐색 후 노드를 삭제하는 과정 : Case 1, 2는 O(1)이 걸리고 Case은 후계자 관련 작업을로 O(h)가 걸린다.

 

BST가 n개의 노드를 가지고 있다고 가정하자.

 

최선의 경우 각 연산은 O(1)이다.

 

최악의 경우 각 연산은 O(n)이다.

이때 트리의 모양은 degenerate tree로 높이는 h = n-1이 되므로 search/insert/remove는 O(n)의 시간을 가지게 된다.

이것은 배열을 사용해 탐색한 것과 동일한 시간이 소요되는 것이다.

 

이제 평균적인 경우의 시간복잡도에 대해 알아보자.

 

비어있는 BST에 랜덤한 n개의 key가 임의의 순서로 insert 된다고 했을때, 최종적인 BST 는 균형잡힌 트리가 된다.

이때, 균형잡힌 트리는 O(log n)의 높이를 가지고, 따라서 주요 연산들의 시간복잡도는 O(log n)이 된다.

 

• Self-Balancing BST

 

BST는 평균적인 경우에는 O(log n)이지만 입력에 따라 O(n)의 시간복잡도를 가질 수 있다.

(입력의 구성이 degenerate tree가 되면 발생)

 

Self -Balancing BST는 항상 트리의 높이를 짧게 유지하기 때문에 최악의 경우에도 O(log n)을 보장한다.