Binary Search Tree : Insertion

BST에 노드를 삽입하는 과정은 다음과 같습니다:

루트 노드부터 시작합니다.
현재 노드의 값과 삽입하려는 데이터 값을 비교합니다.
삽입하려는 데이터 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로 이동하고, 값이 크면 오른쪽 서브트리로 이동합니다.
만약 해당 서브트리가 비어있으면 새로운 노드를 생성하고 그 위치에 삽입합니다.
만약 해당 서브트리가 비어있지 않다면 서브트리의 루트로 이동하여 2단계부터 반복합니다.
모든 작업이 완료되면 변경된 BST의 루트 노드를 반환합니다.
BST에 노드를 삽입하는 이 과정을 재귀적으로 구현하거나 반복문을 사용하여 구현할 수 있습니다. 주어진 문제에서는 이 과정을 잘 구현하여 새로운 노드를 BST에 삽입하고 변경된 BST의 루트 노드를 반환하는 함수를 작성해야 합니다.

 

   Node * insert(Node * root, int data) {
         if (root == nullptr) {
            return new Node(data);
        }
        queue<Node*> q;
        q.push(root);
        
        while(!q.empty()){
            Node* current = q.front();
            q.pop();
            
            if(current->data < data){
                if(current->right) q.push(current->right);
                else {
                    current->right = new Node(data);
                    break;
                }
                
            }
            else if(current->data > data){
                 if(current->left) q.push(current->left);
                 else {
                     current->left = new Node(data);
                     break;
                 }
                
            }
        }

        return root;
    }

 

이진 탐색 트리(Binary Search Tree, BST)에 새로운 노드를 삽입하는 알고리즘을 구현하는 문제입니다. BST는 다음과 같은 규칙을 따릅니다:

모든 노드는 하나의 값과 왼쪽 서브트리와 오른쪽 서브트리로 구성됩니다.
왼쪽 서브트리의 모든 노드의 값은 현재 노드의 값보다 작습니다.
오른쪽 서브트리의 모든 노드의 값은 현재 노드의 값보다 큽니다.
중복된 값은 허용되지 않습니다.