C++ 부모 포인터를 활용한 이진 탐색 트리(BST) 삽입 구현하기

이진 탐색 트리(BST)에 새 노드를 삽입할 때는 일반적으로 재귀 방식을 사용하며, 각 서브트리의 루트 주소를 반환하는 형태로 구현합니다. 이번 글에서는 또 다른 접근 방식을 소개합니다. 바로 부모(parent) 포인터를 함께 유지하는 방법입니다. 부모 포인터는 특정 노드의 조상(ancestor)을 찾는 등 다양한 트리 연산에서 매우 유용하게 활용됩니다.

핵심 아이디어는 왼쪽과 오른쪽 서브트리의 주소를 저장해 두었다가, 재귀 호출이 반환된 후 해당 포인터들의 부모 포인터를 설정하는 것입니다. 이렇게 하면 삽입 과정에서 모든 부모 포인터가 반드시 올바르게 설정됨을 보장할 수 있습니다. 루트 노드의 부모는 NULL로 설정합니다.

알고리즘

insert(node, key) −

begin
    if node is null, then create a new node and return
        if the key is less than the key of node, then
            create a new node with key
            add the new node with the left pointer or node
        else if key is greater or equal to the key of node, then
                create a new node with key
            add the new node at the right pointer of the node
        end if
    return node
end

C++ 예제 코드

#include<iostream>
using namespace std;
class Node {
    public:
        int data;
        Node *left, *right, *parent;
};
struct Node *getNode(int item) {
    Node *temp = new Node;
    temp->data = item;
    temp->left = temp->right = temp->parent = NULL;
    return temp;
}
void inorderTraverse(struct Node *root) {
    if (root != NULL) {
        inorderTraverse(root->left);
        cout << root->data << " ";
        if (root->parent == NULL)
            cout << "NULL" << endl;
        else
            cout << root->parent->data << endl;
        inorderTraverse(root->right);
    }
}
struct Node* insert(struct Node* node, int key) {
    if (node == NULL) return getNode(key);
    if (key < node->data) { //왼쪽 서브트리로 삽입
        Node *left_child = insert(node->left, key);
        node->left = left_child;
        left_child->parent = node;
    }
    else if (key > node->data) { //오른쪽 서브트리로 삽입
        Node *right_child = insert(node->right, key);
        node->right = right_child;
        right_child->parent = node;
    }
    return node;
}
int main() {
    struct Node *root = NULL;
    root = insert(root, 100);
    insert(root, 60);
    insert(root, 40);
    insert(root, 80);
    insert(root, 140);
    insert(root, 120);
    insert(root, 160);
    inorderTraverse(root);
}

실행 결과

40 60
60 100
80 60
100 NULL
120 140
140 100
160 140

출력 결과를 보면 각 줄은 [노드의 데이터] [부모 노드의 데이터] 순서로 표시됩니다. 중위 순회(inorder traversal) 결과인 40, 60, 80, 100, 120, 140, 160이 오름차순으로 출력되며, 각 노드 옆에는 그 노드의 부모 값이 함께 나타납니다.

예를 들어 첫 번째 줄의 40 60은 노드 40의 부모가 60임을 의미하고, 네 번째 줄의 100 NULL은 루트 노드 100의 부모가 없음(NULL)을 의미합니다. 이처럼 삽입 과정에서 모든 노드의 부모 포인터가 정확하게 설정되었음을 확인할 수 있습니다.