[자료구조] BST

BST란?

Binary Search Tree(우리말로 '이진탐색트리')이다.
노드별로 자식을 최대 2개까지 가질 수 있는 트리형 자료구조인데, 탐색에 효율적이라서 "탐색"이란 단어가 붙지 않았나 싶다.

BST의 중요한 특징은 다음과 같다.

• 임의의 노드를 기준으로, 왼쪽 노드(+서브 트리)는 이하의 값을 오른쪽 노드(+서브 트리)는 이상의 값을 가진다.
• 중복되는 노드가 없다!

---

BST를 C++로 구현해 보자!

👏 더 효율적인 코드를 고민해 보자, 수정해 나가자..!

1. Node 구조체

struct Node {
    int data;
    Node* leftchild = NULL;
    Node* rightchild = NULL;
};

하나의 노드는 고유한 data를 담는 int와, 왼쪽/오른쪽 자식 노드를 연결하는 Node* 두 개로 구성된다.

2. BST 클래스

class BST {
public:
    Node* root = NULL;
    int cnt = 0;

    void insert(int data);
    Node* find(int data, Node* parPos);
    void deleteNode(int data);

    void travelBST();
    void travelBSTNode(Node* temp);
};

BST 트리는 클래스로 만들었는데, root 노드를 가리키는 Node*와 생성되는 노드의 갯수를 담을 cnt를 멤버 변수로 갖는다.

BST 트리의 멤버함수는 삽입/조회/삭제 그리고 전체 출력 등 4가지의 기능으로 구현하였다.

2-1. 삽입 - insert()

void BST::insert(int data){
    // 1. 동일한 data 값을 가진 노드가 있는지 탐색한다. -> 있으면 실패 반환
    Node* parPos = root;
    Node* temp = this->find(data, parPos);
    if(temp != NULL){
        cout << data + "값을 가진 노드가 이미 있습니다.\n";
        return;
    }

    // 2. (없다는 전제 하에) 새로운 노드를 만들어서 data를 담는다.
    Node* newNode = new Node();
    newNode->data = data;
    
    // case 1) 빈 트리인 경우 -> 새 노드를 루트와 연결한다.
    if(parPos == NULL){
        this->root = newNode;
        cout << "삽입 성공!" << endl;
        return;
    }
    
    // case 2) 빈 트리가 아닌 경우 -> parPos의 노드보다 작은지 큰지 판단해서 연결될 위치를 찾고, 넣는다.
    // ※ 삽입은 항상 리프노드로 들어간다!
    if(data < parPos->data){
        parPos->leftchild = newNode;
    }
    else { // data > parPos->data
        parPos->rightchild = newNode;
    }
    cout << "삽입 성공!" << endl;

    (this->cnt)++;
};

2-2. 조회 - find()

// find 함수2 (부모의 위치도 함께 반환)
// input : data, parPos(부모의 위치를 받아올 포인터 변수) / output : Node*(동일한 데이터를 가진 노드의 위치)
Node* BST::find(int data, Node* parPos){
    // 1. 루트 노드를 받아와서 준비를 마친다.
    Node* temp = root;
    
    // 2. 루트부터 아래로 내려가면서, 해당 데이터가 있는지 찾는다. + temp가 옮겨가기 전, parPos에 temp를 담는다.
    do{
        if(data == temp->data){  // 3. 있다면, 그 위치를 반환한다.
            cout << data + "를 가진 노드를 찾았습니다!\n";
            return temp;
        } 
        else if(data < temp->data){
            parPos = temp;
            temp = temp->leftchild;
        }
        else { // data > temp->data
            parPos = temp;
            temp = temp->rightchild;
        }
    } while(temp != NULL);

    // temp == NULL
    // 노드를 못 찾은 경우 + 루트 노드가 없는 경우(즉, 빈 트리인 경우) -> NULL을 반환한다.
    cout << data + "를 가진 노드가 없습니다!\n";
    return NULL;
};

2-3. 삭제 - delete()

void BST::deleteNode(int data){
    // 1. 해당 data를 가진 노드가 BST에 있는지 찾는다.
    // 없으면 -> 에러메시지 출력
    Node* parPos = NULL;
    Node* temp = this->find(data, parPos);
    if(temp == NULL){
        cout << data + "를 가진 노드가 없습니다.\n";
        return;
    }
    
    // 2. (있다는 전제 하에)
    // case 1) 루트노드 or 리프노드인 경우
    // 그냥 삭제한다.
    if(temp->leftchild == NULL && temp->rightchild == NULL){
        delete temp;
        cout << "삭제 완료!" << endl;
        return;
    }

    // 왼쪽(오른쪽 NULL) / 오른쪽(왼쪽 NULL) / 둘 다(둘 다 != NULL)
    // case 2) 인터널노드인 경우 - 자식이 1개일 때
    // 해당 노드를 삭제하고
    // 그 노드의 부모와 그 노드의 자식을 연결한다.
    if(temp->rightchild == NULL){ // 왼쪽에 연결
        if(parPos->leftchild == temp) parPos->leftchild = temp->leftchild;
        else parPos->rightchild = temp->leftchild;
        delete temp;
    }
    else if(temp->leftchild == NULL) { // 오른쪽에 연결
        if(parPos->leftchild == temp) parPos->leftchild = temp->rightchild;
        else parPos->rightchild = temp->rightchild;
        delete temp;
    }

    // case 3) 인터널노드인 경우 - 자식이 2개일 때
    // 해당 노드를 삭제하고
    // 오른쪽 서브트리에서 가장 작은 노드를 붙인다.
    else{
        Node* min = temp;
        while(min->leftchild != NULL){
            min = temp->leftchild;
        }
        temp->data = min->data;
        delete min;
    }

    cout << "삭제 완료!" << endl;

    (this->cnt)--;
};

2-4. 전체 출력 - travelBST()/travelBSTNode()

void visit(TreeNode<T>* current) {
        cout << current->data << " ";
    }
 
    // 전위 순회 Current - Left - Right
    void preorder(TreeNode<T>* current) {
        if (current != null) {
            visit(current);
            preorder(current->left);
            preorder(current->right);
        }
    }

🤥 내가 한 게 아니다!

하핳...전위 순회 하는 방법이 이론적으로는 이해가 되는데, 오른쪽 노드로 넘어가는 부분이 잘 해결되지 않는다.

막히는 부분

• 1) 루트 출력 2) 왼쪽 이동 → 왼쪽 NULL이 나올 때까지 반복!
  그리고 😢3) 오른쪽 이동😢
  • 이동하는 temp 외에도 부모 노드를 따로 또 만들어야 하는가?
  • 그러면, 오른쪽 찍고 또 그 위로는 어떻게 올라갈 건데?
  • cnt를 활용해서 해당 노드의 인덱스를 알아내어 이동하는 방향으로?
  • 근데 트리의 노드들이 인덱스로 관리되지 않는데? 그래도 접근할 수 있으려나?