이진 탐색 트리 | 자료구조실습 3주차 과제

* 성신여대 22-2학기 자료구조실습 수업시간에 배운 내용을 토대로 요약 정리한 글입니다

 

 

1. 스케줄링 문제에 접근하는 이진 탐색 트리 소개

 

1) 이진 탐색 트리란?

• 이진 트리 기반의 탐색 자료구조
• key (왼쪽 서브 트리) <= key (루트 노드) <= (오른쪽 서브 트리)
• 중위 순회(inorder traversal)를 할 경우 오름차순으로 정렬된 값을 얻을 수 있다

 

2) 이진 탐색 트리 코드 구조

이진 탐색 트리의 코드는 다음과 같이 세 개의 class로 구조화해볼 수 있다.

 

 

 

 

 

---

① BinaryNode : 아래와 같이 본인의 int형 data와 left, right BinaryNode* 포인터를 가지고 있는 class를 만든다.

 

 

 

 

class BinaryNode {
private:
    int data;
    BinaryNode* left; // 포인터 변수로 작성
    BinaryNode* right;
public:
    BinaryNode(int d = 0, BinaryNode* l = NULL, BinaryNode* r = NULL) 
    : data(d), left(l), right(r) { } // 생성자를 이용해 변수 초기화

    int getData() { return data; }
    BinaryNode* getLeft() { return left; }
    BinaryNode* getRight() { return right; }

    void setData(int d) { data = d; }
    void setLeft(BinaryNode* l) { left = l; }
    void setRight(BinaryNode* r) { right = r; }

    bool isLeaf() { return (left == NULL) && (right == NULL); } // leaf 노드는 가장 말단에 있으므로 left와 right가 모두 NULL임
};

 

 

 

② BinaryTree : root라는 BinaryNode* 포인터를 멤버변수로 두고, root를 통해 left, right를 탐방하면서 이진 트리의 특징을 return 하는 함수들을 구현한 클래스이다.

 

 

 

몇몇 함수는 오버로딩을 통해 구현하여 편리하고 보기 좋게 작성되었다.

 

class BinaryTree {
protected: // 나중에 BinSrchTree가 상속받을 수 있게 멤버변수를 protected로 설정하였다.
    BinaryNode* root; 
public:
    BinaryTree(): root(NULL) { }
    void setRoot(BinaryNode* r) { root = r; }
    BinaryNode* getRoot() { return root; }
    bool isEmpty() { return ((root == NULL) ? true : false); } // root가 NULL일 경우 true.

	// 여기서부터는 각 함수들이 함수 오버로딩을 통해 구현되었다.

    int getCount() { return isEmpty() ? 0 : getCount(root); }
    int getCount(BinaryNode* node) {
        if (node == NULL) return 0;
        return 1 + getCount(node->getLeft()) + getCount(node->getRight()); // 재귀함수를 통해 +1을 반복적으로 하여 count
    }
    
    int getLeafCount() { return isEmpty() ? 0 : getLeafCount(root); }
    int getLeafCount(BinaryNode* node) {
        if (node == NULL) return 0;
        if (node->isLeaf()) return 1; // 1을 return 하는 부분이 총 leaf노드의 개수만큼 반복되므로 이를 통해 count를 할 수 있음
        else return getLeafCount(node->getLeft()) + getLeafCount(node->getRight()); //left와 right를 검사
    }
    
    int getHeight() { return isEmpty() ? 0 : getHeight(root); }
    int getHeight(BinaryNode* node) {
        if (node == NULL) return 0;
        int hLeft = getHeight(node->getLeft());
        int hRight = getHeight(node->getRight());
        return (hLeft > hRight) ? (1 + hLeft) : (1 + hRight); // Height값은 hLeft와 hRight 중 더 큰 값을 return해주어야 함
    }
    
    bool isFull() { return isEmpty() ? true : isFull(root); }
    int isFull(BinaryNode* node) {
        if (node == NULL) return true;
        if ((node->getLeft() == NULL) && (node->getRight() == NULL)) return true;
        
        if ((node->getLeft() != NULL) && (node->getRight() != NULL))
            return isFull(node->getLeft()) && isFull(node->getRight());
        else return false; // 만약 left와 right가 둘다 NULL이 아니거나 둘다 NULL이 아니지 않을 경우 Full인 tree라고 할 수 없으므로 false를 return
    }
    
    int calcLevel(int n) { return isEmpty() ? 0 : calcLevel(root, n, 1); } // n이 있는 위치의 레벨을 return 
    int calcLevel(BinaryNode* node, int n, int level) {
        if (node == NULL) return 0;
        if (node->getData() == n) return level;
        int ll = calcLevel(node->getLeft(), n, level + 1); // left로 내려가면서 level에 + 1
        if (ll != 0) return ll;
        ll = calcLevel(node->getRight(), n, level + 1); // right로 내려가면서 level에 + 1
        return ll;
    }
};

 

 

 

 

③ BinSrchTree : 이진 탐색 트리의 search, insert, remove 함수를 구현

 

class BinSrchTree : public BinaryTree {
public:
    BinSrchTree(void) { }
    ~BinSrchTree(void) { }

    BinaryNode* search(int key) {
        BinaryNode* node = search(root, key);
        if (node != NULL) return node; // 만약 key값을 가진 노드가 있을 경우 (==NULL이 아닐 경우)
        else return NULL;
    }

    BinaryNode* search(BinaryNode* n, int key) {
        if (n == NULL) return NULL;
        if (key == n->getData()) return n; // 노드 n에 있는 data값과 key값이 같을 경우 노드 n을 return
        else if (key < n->getData()) return search(n->getLeft(), key); // key값이 data값보다 작을 경우 left로 내려가기
        else return search(n->getRight(), key); // key값이 data값보다 작을 경우 right로 내려가기
    }

    void insert(BinaryNode* n) {
        if (n == NULL) return;
        if (isEmpty()) root = n; // 만약 트리가 비어있을 경우 root가 n이 됨
        else insert(root, n); // 비어있지 않을 경우 아래 함수 호출
    }

    void insert(BinaryNode* r, BinaryNode* n) { // r: 루트노드, n: 삽입할 노드
        if (n->getData() == r->getData()) return; // 중복 허용 X
        else if (n->getData() < r->getData()) { // 삽입할 노드의 key 값이 n 노드의 key 값보다 더 작을 경우
            if (r->getLeft() == NULL) r->setLeft(n); // left가 비어있으면 left에 n을 삽입
            else insert(r->getLeft(), n); // 아닐 경우 함수 호출하면서 left로 내려가기
        }
        else { // 삽입할 노드의 key 값이 n 노드의 key 값보다 더 클 경우
            if (r->getRight() == NULL) r->setRight(n); // right가 비어있으면 right에 n을 삽입
            else insert(r->getRight(), n); // 아닐 경우 함수 호출하면서 right로 내려가기
        }
    }

    void remove(int data) {
        if (isEmpty()) return; // empty면 함수 종료시킴
        BinaryNode* parent = NULL;
        BinaryNode* node = root; // 일단 node를 root로 설정
        // 삭제하기 전에 먼저, data값을 가진 node를 찾아야함
        while ((node != NULL) && (node->getData() != data)) { // node가 NULL이 아니고 data를 가진 노드를 찾지 못 할 동안
            parent = node;
            node = ((data < node->getData()) ? node->getLeft() : node->getRight()); // 현재 node의 data값과 우리가 찾아야 할 data값의 대소비교를 통해 left 혹은 right로 이동
        }
        
        if (node == NULL) { // 만약 data를 가진 노드를 찾지 못 했을 경우
            cout << "error\n";
            return;
        }
        else remove(parent, node); data를 가진 노드를 찾았을 경우
    }

    void remove(BinaryNode* parent, BinaryNode* node) {
        // case 1 : 삭제할 노드가 단말노드일 경우
        if (node->isLeaf()) {
            if (parent == NULL) root = NULL;
            else {
                if (parent->getLeft() == node) // 단말노드가 left child
                    parent->setLeft(NULL);
                else // 단말노드가 right child
                    parent->setRight(NULL);
            }
        }
        
        // case 2 : 삭제할 노드가 자식이 하나인 노드일 경우
        else if ((node->getLeft() == NULL) || (node->getRight() == NULL)) {
            BinaryNode* child = ((node->getLeft() != NULL) ? node->getLeft() : node->getRight()); // 자식 노드 선언
            if (node == root) root = child;
            else {
                if (parent->getLeft() == node) 
                    parent->setLeft(child); // 부모 노드의 왼쪽 자식을 제거하고 child를 붙임
                else
                    parent->setRight(child); // 부모 노드의 오른쪽 자식을 제거하고 child를 붙임
            }
        }
        // case 3 : 삭제할 노드가 두 개의 자식을 가진 노드일 경우
        else {
            BinaryNode* succp = node;
            BinaryNode* succ = node->getRight(); // 한번 오른쪽으로 간 후
            // 거기에서 가장 왼쪽의 값 찾기
            while (succ->getLeft() != NULL) { // left most 값 찾기
                succp = succ;
                succ = succ->getLeft();
            }
			// 만약 succp의 왼쪽이 succ면 succp의 left랑 succ의 right랑 연결
            if (succp->getLeft() == succ) succp->setLeft(succ->getRight());
            // 만약 succp의 왼쪽이 succ가 아니라면 succcp가 가장 작은 값이므로 succp의 right를 succ의 right와 연결
            else succp->setRight(succ->getRight());

            node->setData(succ->getData());
            node = succ;
        }
        delete node;
    }
};

 

* 이해를 위해 교재 내용 첨부함

 

 

 

 

 

3) 스케줄링 문제

 

상황

빵집에 오븐이 있다고 하자. 오븐에는 4, 20, 32, 37, 45 분에 각각 빵 하나씩이 들어갈 예정이다. 모든 빵들은 오븐에서 5분간 구워진 후 나오게 된다. (오븐이 좁은 관계로 빵은 하나만 넣어서 구울 수 있다, 동시에 구울 수 없다)

 

근데, 당일에 손님이 찾아와 26분에 빵을 하나 구워달라고 요청을 한다. 

 

알고리즘을 사용해 빵집에서는 26분에 빵을 구워 손님의 요청을 들어줄 수 있을지 계산하려고 한다.

 

 

스케줄링을 위한 알고리즘 비교

 

결과

이진 탐색 트리의 root를 잘 설정하여 트리의 높이를 줄이는 것이 효과적이다!!!!!

 

 

 

 

2. Big-O 표기법 소개

 

1) 빅오 개념

 

2) 빅오 적용

 

 

 

3. 문제 풀이

 

3-1. LeetCode 문제 풀이

# 98

https://chaesoong2.tistory.com/6

98. Validate Binary Search Tree | LeetCode 문제 풀이

 

# 99

https://chaesoong2.tistory.com/7

 

99. Recover Binary Search Tree | LeetCode 문제 풀이

 

 

# 700

https://chaesoong2.tistory.com/8

700. Search in a Binary Search Tree | LeetCode 문제 풀이

 

# 701

https://chaesoong2.tistory.com/9

701. Insert into a Binary Search Tree | LeetCode 문제 풀이