【C++】指定範囲内のBSTキーをO(1)空間で出力する方法 ― モリス走査の活用

問題の概要

この問題では、2つの値 k1 と k2（k1 < k2）、および二分探索木（BST）のルートが与えられます。目的は、指定された範囲内に存在するBSTのキーを出力するプログラムをC++で作成することです。

問題の説明： 木に含まれるすべてのキーのうち、k1 以上 k2 以下の値を持つものを昇順に出力します。

入出力例

入力： k1 = 4、k2 = 12

出力： 6, 7, 9

解決アプローチ

この種の問題は、一般的には中順走査（inorder traversal）を使えば簡単に解くことができます。しかし、再帰呼び出しやスタック・キューを利用する通常の実装では、空間計算量が O(n) かかってしまいます。今回は O(1) の空間計算量で解くことが求められているため、特殊な走査手法を採用します。

そこで使用するのがモリス走査（Morris Traversal）です。この手法はスレッド化二分木（threaded binary tree）の考え方に基づいており、スタックやキューを一切必要とせず、未使用の NULL ポインタを一時的なリンク情報の保存先として活用します。これにより、追加の記憶領域を O(1) に抑えることができます。

モリス走査の流れ

1. 現在ノードに左の子がない場合 → キーが範囲内であれば出力し、右の子へ移動します。
2. 左の子が存在する場合 → 左部分木の中で最も右にあるノード（中順における直前のノード）を探します。
   ・その右ポインタが NULL の場合：現在ノードへのスレッド（戻り用リンク）を張り、左へ移動します。
   ・すでに現在ノードを指している場合：スレッドを解除して木を元の構造に復元し、現在ノードのキーを出力して右へ移動します。

C++による実装例

以下は、モリス走査を用いて指定範囲内のキーを出力するプログラムです。

#include <iostream>
using namespace std;

struct node {
    int data;
    struct node *left, *right;
};

node* insertNode(int data) {
    node* temp = new node;
    temp->data = data;
    temp->right = temp->left = NULL;
    return temp;
}

void RangeTraversal(node* root, int k1, int k2) {
    if (!root)
        return;

    node* nodeTraversal = root;

    while (nodeTraversal) {
        if (nodeTraversal->left == NULL) {
            if (nodeTraversal->data <= k2 && nodeTraversal->data >= k1)
                cout << nodeTraversal->data << " ";
            nodeTraversal = nodeTraversal->right;
        }
        else {
            node* prevNode = nodeTraversal->left;
            while (prevNode->right != NULL && prevNode->right != nodeTraversal)
                prevNode = prevNode->right;

            if (prevNode->right == NULL) {
                prevNode->right = nodeTraversal;
                nodeTraversal = nodeTraversal->left;
            }
            else {
                prevNode->right = NULL;
                if (nodeTraversal->data <= k2 && nodeTraversal->data >= k1)
                    cout << nodeTraversal->data << " ";
                nodeTraversal = nodeTraversal->right;
            }
        }
    }
}

int main() {
    node* root = insertNode(6);
    root->left = insertNode(3);
    root->right = insertNode(2);
    root->left->left = insertNode(1);
    root->left->right = insertNode(7);
    root->right->right = insertNode(9);

    cout << "All BST keys in the given range are \t";
    RangeTraversal(root, 4, 10);

    return 0;
}

実行結果

All BST keys in the given range are 7 6 9

このように、モリス走査を利用すれば、スタックや再帰といった補助データ構造に頼ることなく、指定範囲内のBSTキーを効率的に出力できます。時間計算量は O(n)、追加の空間計算量は O(1) となるため、メモリ制約が厳しい場面で特に有効な手法です。