C++で実装する二分探索木（BST）イテレータの作り方

二分探索木（BST）に対するイテレータを実装することを考えてみましょう。このイテレータには、次の2つのメソッドが必要です。

• next()：次の要素（次に小さい値）を返すメソッド
• hasNext()：次の要素が存在するかどうかをブール値で返すメソッド

例えば、以下のような二分探索木があるとします。

この木に対して、関数呼び出しのシーケンスが [next(), next(), hasNext(), next(), hasNext(), next(), hasNext(), next(), hasNext()] である場合、出力は [3, 7, true, 9, true, 15, true, 20, false] となります。これは、木の中順走査（inorder traversal）の順序で値が取り出されることを意味します。

解決のためのアプローチ

この問題は、スタックを使って中順走査を効率的に管理することで解決できます。具体的な手順は以下の通りです。

next() メソッドの処理内容

• スタックの先頭要素を curr として取得し、その要素をスタックからポップする
• curr の右の子が存在する場合、右部分木の中順後継者（inorder successor）となるノード群をスタックにプッシュする
• 現在のノードの値を返す

hasNext() メソッドの処理内容

• スタックが空でなければ true を、空であれば false を返す

コンストラクタでは、ルートノードから左方向へ辿りながら、すべての左端ノードをスタックに積んでおきます。これにより、next() が呼ばれるたびに最小の未訪問ノードが常にスタックの先頭に来るようになります。

それでは、実際の実装を見てみましょう。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
    public:
        int val;
        TreeNode *left, *right;
        TreeNode(int data){
            val = data;
            left = right = NULL;
        }
};
void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        } else {
            q.push(temp->left);
        }
        if(!temp->right){
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        }else{
            q.push(temp->right);
        }
    }
}
TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        insert(&root, v[i]);
    }
    return root;
}
class BSTIterator {
public:
    stack <TreeNode*> st;
    void fillStack(TreeNode* node){
        while(node && node->val != 0){
            st.push(node);
            node=node->left;
        }
    }
    BSTIterator(TreeNode* root) {
        fillStack(root);
    }
    /** @return 次に小さい数値を返す */
    int next() {
        TreeNode* curr = st.top();
        st.pop();
        if(curr->right && curr->right->val != 0){
            fillStack(curr->right);
        }
        return curr->val;
    }
    /** @return 次に小さい数値が存在するかどうかを返す */
    bool hasNext() {
        return !st.empty();
    }
};
main(){
    vector<int> v = {7,3,15,NULL,NULL,9,20};
    TreeNode *root = make_tree(v);
    BSTIterator ob(root);
    cout << "Next: " << ob.next() << endl;
    cout << "Next: " << ob.next() << endl;
    cout << ob.hasNext() << endl;
    cout << "Next: " << ob.next() << endl;
    cout << ob.hasNext() << endl;
    cout << "Next: " << ob.next() << endl;
    cout << ob.hasNext() << endl;
    cout << "Next: " << ob.next() << endl;
    cout << ob.hasNext() << endl;
}

入力

BSTIterator ob(root);
ob.next()
ob.next()
ob.hasNext()
ob.next()
ob.hasNext()
ob.next()
ob.hasNext()
ob.next()
ob.hasNext()

出力

Next: 3
Next: 7
1
Next: 9
1
Next: 15
1
Next: 20
0

計算量について

この実装における計算量は以下の通りです。

• 時間計算量：next() および hasNext() は平均して O(1) で動作します。各ノードはスタックに最大1回プッシュされ、1回ポップされるだけだからです。
• 空間計算量：O(h)（h は木の高さ）。スタックには、任意の時点で最大でも木の高さ分のノードしか保持されません。

このように、スタックを利用した中順走査の遅延評価により、メモリ効率よく二分探索木を昇順に走査できるイテレータが実現できます。