C++によるスプレーツリーの実装

概要

このプログラムは、スプレーツリー（Splay Tree）をC++で実装したものです。スプレーツリーは、アクセスされたノードをルートに移動させる「スプレイ」操作を行う自己調整型の二分探索木です。これにより、頻繁にアクセスされる要素へのアクセスが高速化されます。

クラス構造と主要関数

ノード構造体 s

struct s {
    int k;        // キー値
    s* lch;       // 左の子へのポインタ
    s* rch;       // 右の子へのポインタ
};

クラス SplayTree のメンバ関数

• RR_Rotate(s* k2): 右回転（Right-Right Rotation）
• LL_Rotate(s* k2): 左回転（Left-Left Rotation）
• Splay(int key, s* root): トップダウンスプレイ操作。指定キーをルートに移動
• New_Node(int key): 新しいノードを生成
• Insert(int key, s* root): ノードを挿入
• Delete(int key, s* root): ノードを削除
• Search(int key, s* root): ノードを探索（スプレイを実行）
• InOrder(s* root): 中順巡回でツリーを表示

アルゴリズムのポイント

スプレイ操作（トップダウン方式）

スプレイ操作では、ダミーヘッダーノードを用いて左部分木（LeftTreeMax）と右部分木（RightTreeMin）を構築しながら探索を進めます。探索パス上でジグジグ（同方向の二重回転）やジグザグ（異方向の回転）を行い、最終的に対象ノードをルートに組み立て直します。

挿入操作

1. 新しいノードを作成
2. 挿入キーでスプレイを実行（既存ノードならルートに移動）
3. ルートのキーと比較し、適切な位置に新ノードを接続

削除操作

1. 削除キーでスプレイを実行
2. キーが見つからなければそのまま返す
3. 左部分木が空なら右部分木を新ルートとする
4. そうでなければ左部分木の最大ノードをスプレイし、右部分木を接続

実装コード

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct s {
    int k;
    s* lch;
    s* rch;
};

class SplayTree {
public:
    // 右回転
    s* RR_Rotate(s* k2) {
        s* k1 = k2->lch;
        k2->lch = k1->rch;
        k1->rch = k2;
        return k1;
    }

    // 左回転
    s* LL_Rotate(s* k2) {
        s* k1 = k2->rch;
        k2->rch = k1->lch;
        k1->lch = k2;
        return k1;
    }

    // トップダウンスプレイ
    s* Splay(int key, s* root) {
        if (!root) return NULL;
        s header;
        header.lch = header.rch = NULL;
        s* LeftTreeMax = &header;
        s* RightTreeMin = &header;

        while (1) {
            if (key < root->k) {
                if (!root->lch) break;
                if (key < root->lch->k) {
                    root = RR_Rotate(root);
                    if (!root->lch) break;
                }
                RightTreeMin->lch = root;
                RightTreeMin = RightTreeMin->lch;
                root = root->lch;
                RightTreeMin->lch = NULL;
            }
            else if (key > root->k) {
                if (!root->rch) break;
                if (key > root->rch->k) {
                    root = LL_Rotate(root);
                    if (!root->rch) break;
                }
                LeftTreeMax->rch = root;
                LeftTreeMax = LeftTreeMax->rch;
                root = root->rch;
                LeftTreeMax->rch = NULL;
            }
            else break;
        }

        LeftTreeMax->rch = root->lch;
        RightTreeMin->lch = root->rch;
        root->lch = header.rch;
        root->rch = header.lch;
        return root;
    }

    // ノード生成
    s* New_Node(int key) {
        s* p_node = new s;
        if (!p_node) {
            fprintf(stderr, "Out of memory!\n");
            exit(1);
        }
        p_node->k = key;
        p_node->lch = p_node->rch = NULL;
        return p_node;
    }

    // 挿入
    s* Insert(int key, s* root) {
        static s* p_node = NULL;
        if (!p_node) p_node = New_Node(key);
        else p_node->k = key;

        if (!root) {
            root = p_node;
            p_node = NULL;
            return root;
        }

        root = Splay(key, root);
        if (key < root->k) {
            p_node->lch = root->lch;
            p_node->rch = root;
            root->lch = NULL;
            root = p_node;
        }
        else if (key > root->k) {
            p_node->rch = root->rch;
            p_node->lch = root;
            root->rch = NULL;
            root = p_node;
        }
        else return root;

        p_node = NULL;
        return root;
    }

    // 削除
    s* Delete(int key, s* root) {
        s* temp;
        if (!root) return NULL;
        root = Splay(key, root);
        if (key != root->k) return root;

        if (!root->lch) {
            temp = root;
            root = root->rch;
        }
        else {
            temp = root;
            root = Splay(key, root->lch);
            root->rch = temp->rch;
        }
        free(temp);
        return root;
    }

    // 探索
    s* Search(int key, s* root) {
        return Splay(key, root);
    }

    // 中順巡回表示
    void InOrder(s* root) {
        if (root) {
            InOrder(root->lch);
            cout << "key: " << root->k;
            if (root->lch) cout << " | left child: " << root->lch->k;
            if (root->rch) cout << " | right child: " << root->rch->k;
            cout << "\n";
            InOrder(root->rch);
        }
    }
};

int main() {
    SplayTree st;
    s* root = NULL;
    st.InOrder(root);
    int i, c;

    while (1) {
        cout << "1. Insert " << endl;
        cout << "2. Delete" << endl;
        cout << "3. Search" << endl;
        cout << "4. Exit" << endl;
        cout << "Enter your choice: ";
        cin >> c;

        switch (c) {
            case 1:
                cout << "Enter value to be inserted: ";
                cin >> i;
                root = st.Insert(i, root);
                cout << "\nAfter Insert: " << i << endl;
                st.InOrder(root);
                break;
            case 2:
                cout << "Enter value to be deleted: ";
                cin >> i;
                root = st.Delete(i, root);
                cout << "\nAfter Delete: " << i << endl;
                st.InOrder(root);
                break;
            case 3:
                cout << "Enter value to be searched: ";
                cin >> i;
                root = st.Search(i, root);
                cout << "\nAfter Search " << i << endl;
                st.InOrder(root);
                break;
            case 4:
                exit(1);
            default:
                cout << "\nInvalid type! \n";
        }
    }
    return 0;
}

実行例

1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 7
After Insert: 7
key: 7

1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 6
After Insert: 6
key: 6 | right child: 7
key: 7

1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 4
After Insert: 4
key: 4 | right child: 6
key: 6 | right child: 7
key: 7

1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 5
After Insert: 5
key: 4
key: 5 | left child: 4 | right child: 6
key: 6 | right child: 7
key: 7

1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 2
Enter value to be deleted: 3
After Delete: 3
key: 2 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7

1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 4

解説

実行例では、値 7, 6, 4, 5, 3, 2 を順に挿入し、各挿入後に中順巡回の結果を表示しています。スプレーツリーの特性により、最後にアクセスしたノード（挿入されたノード）がルートに移動します。例えば 5 を挿入した後は 5 がルートとなり、左右の部分木が適切に再構成されていることがわかります。

その後、値 2 を探索（スプレイ）し、値 3 を削除しています。削除後も二分探索木の性質が保たれ、中順巡回でソート順が維持されていることが確認できます。