C++で親ポインタを使った二分探索木（BST）へのノード挿入方法

二分探索木（BST）に新しいノードを挿入する場合、一般的には再帰的な方法が用いられ、その際に各部分木の根のアドレスを返します。本記事では、もうひとつのアプローチとして、親ポインタを維持しながら挿入を行う方法を紹介します。親ポインタを保持しておくと、特定のノードの祖先をたどったり、中順後続ノード（inorder successor）を求めたりする処理などで非常に役立ちます。

基本的な考え方は、再帰呼び出しによって左部分木・右部分木のアドレスを受け取り、その戻り値のノードに対して親ポインタを設定するというものです。これにより、挿入処理の中ですべての親ポインタが正しく設定されることが保証されます。なお、木の根（ルート）の親ポインタはNULLに設定されます。

アルゴリズム

insert(node, key) −

begin
    if node が NULL なら、key を持つ新しいノードを作成して返す
    if key が node のデータより小さい場合
        left_child := insert(node の左部分木, key)
        node の左ポインタ := left_child
        left_child の親ポインタ := node
    else if key が node のデータより大きい場合
        right_child := insert(node の右部分木, key)
        node の右ポインタ := right_child
        right_child の親ポインタ := 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

出力の各行は「ノードの値　親の値」のペアを表しています。例えば「40 60」という行は、値40を持つノードの親が60であることを意味します。木の根である100には親が存在しないため、「NULL」と表示されています。このように中順走査（inorder traversal）の結果を確認することで、すべてのノードの親ポインタが正しく設定されていることが分かります。

計算量と注意点

この挿入操作の時間計算量は、木のバランスが取れている場合は平均O(log n)ですが、ソート済みデータを挿入するなどして木が偏った場合は最悪O(n)になります。また、この実装では既に同じ値が木に存在する場合（key が node のデータと等しい場合）、そのキーは挿入されずに無視される点にも注意してください。