半永続(partially persistent)2分探索木 https://www.youtube.com/watch?v=T0yzrZL1py0

tree.d

/*
$ rdmd tree.d 
insert/print [i,p]: i
value: 2
2 inserted. current version: 1
insert/print [i,p]: i
value: 6
6 inserted. current version: 2
insert/print [i,p]: i
value: 3
3 inserted. current version: 3
insert/print [i,p]: i
value: 4
4 inserted. current version: 4
insert/print [i,p]: i
value: 1
1 inserted. current version: 5
insert/print [i,p]: p
version [1-5]: 4

digraph g {
"n7F0577033060" [label="2"];
nullL7F0577033060 [shape=point];
"n7F0577033060" -> nullL7F0577033060
"n7F05770330F0" [label="6"];
"n7F0577033090" [label="3"];
nullL7F0577033090 [shape=point];
"n7F0577033090" -> nullL7F0577033090
"n7F0577033120" [label="4"];
nullL7F0577033120 [shape=point];
"n7F0577033120" -> nullL7F0577033120
nullR7F0577033120 [shape=point];
"n7F0577033120" -> nullR7F0577033120
"n7F0577033090" -> "n7F0577033120"
"n7F05770330F0" -> "n7F0577033090"
nullR7F05770330F0 [shape=point];
"n7F05770330F0" -> nullR7F05770330F0
"n7F0577033060" -> "n7F05770330F0"
}

insert/print [i,p]: p
version [1-5]: 3

digraph g {
"n7F0577033060" [label="2"];
nullL7F0577033060 [shape=point];
"n7F0577033060" -> nullL7F0577033060
"n7F0577033030" [label="6"];
"n7F0577033090" [label="3"];
nullL7F0577033090 [shape=point];
"n7F0577033090" -> nullL7F0577033090
nullR7F0577033090 [shape=point];
"n7F0577033090" -> nullR7F0577033090
"n7F0577033030" -> "n7F0577033090"
nullR7F0577033030 [shape=point];
"n7F0577033030" -> nullR7F0577033030
"n7F0577033060" -> "n7F0577033030"
}
*/

import std.stdio : readln, writefln, writeln, write;
import std.conv : to;
import std.typecons : Tuple;
import std.exception : collectException;
import std.string : chomp;

struct PersistentBinaryTree(T)
{
    size_t v;
    enum Field
    {
        lhs,
        rhs
    }

    struct Node
    {
        T key;
        Node* lhs;
        Node* rhs;
        Node* now;
        Field field;
        size_t ver;
        this(T _key, Node* _lhs, Node* _rhs)
        {
            key = _key;
            lhs = _lhs;
            rhs = _rhs;
        }

        Node* insert(T x, ref size_t v)
        {
            if (this.key == x)
                return null;

            Node* n = &this;
            Node* ret = null;
            if (this.now) switch (this.field)
            {
            case Field.lhs:
                ret = n = new Node(this.key, this.now, this.rhs);
                break;
            case Field.rhs:
                ret = n = new Node(this.key, this.lhs, this.now);
                break;
            default:
                assert(0);
            }

            n.field = (x < n.key) ? Field.lhs : Field.rhs;
            if (x < n.key && n.lhs)
                n.now = n.lhs.insert(x, v);
            else if (n.key < x && n.rhs)
                n.now = n.rhs.insert(x, v);
            else
            {
                n.now = new Node(x, null, null);
                v++;
            }
            n.ver = v;
            return ret;
        }

        // for debug
        string printAll()
        {
            string result = `"n` ~ (&this).to!string ~ `" [label="<key>` ~ this.key.to!string
                ~ ` | <lhs> lhs | <rhs> rhs | <now> now | <field> ` ~ (now
                        ? ((this.field == Field.lhs) ? "L" : "R") : "") ~ ` | <ver>` ~ (now
                        ? "v" ~ this.ver.to!string : "") ~ `" shape="record" ]` ~ '\n';
            if (this.lhs)
            {
                result ~= this.lhs.printAll();
                result ~= `"n` ~ (&this).to!string ~ `":lhs -> "n` ~ this.lhs.to!string ~ `"` ~ '\n';
            }
            if (this.rhs)
            {
                result ~= this.rhs.printAll();
                result ~= `"n` ~ (&this).to!string ~ `":rhs -> "n` ~ this.rhs.to!string ~ `"` ~ '\n';
            }
            if (this.now)
            {
                result ~= this.now.printAll();
                result ~= `"n` ~ (&this).to!string ~ `":now -> "n` ~ this.now.to!string ~ `"` ~ '\n';
            }
            return result;
        }

        string print(size_t v)
        {
            string result = `"n` ~ (&this)
                .to!string ~ `" [label="` ~ this.key.to!string ~ '"' ~ "];\n";
            if ((this.lhs && (!(this.now) || this.field == Field.rhs || v < this.ver))
                    || (this.now && this.field == Field.lhs && this.ver <= v))
            {
                Node* n = (this.now && this.field == Field.lhs && this.ver <= v) ? this.now
                    : this.lhs;
                assert(n);
                result ~= n.print(v);
                result ~= `"n` ~ (&this).to!string ~ `" -> "n` ~ n.to!string ~ `"` ~ '\n';
            }
            else
            {
                result ~= "nullL" ~ (&this).to!string ~ " [shape=point];\n";
                result ~= `"n` ~ (&this).to!string ~ `" -> ` ~ "nullL" ~ (&this).to!string ~ '\n';
            }
            if ((this.rhs && (!(this.now) || this.field == Field.lhs || v < this.ver))
                    || (this.now && this.field == Field.rhs && this.ver <= v))
            {
                Node* n = (this.now && this.field == Field.rhs && this.ver <= v) ? this.now
                    : this.rhs;
                assert(n);
                result ~= n.print(v);
                result ~= `"n` ~ (&this).to!string ~ `" -> "n` ~ n.to!string ~ `"` ~ '\n';
            }
            else
            {
                result ~= "nullR" ~ (&this).to!string ~ " [shape=point];\n";
                result ~= `"n` ~ (&this).to!string ~ `" -> ` ~ "nullR" ~ (&this).to!string ~ '\n';
            }

            return result;
        }
    }

    Tuple!(size_t, Node*)[] root;

    void insert(T x)
    {
        if (root.length == 0)
        {
            root ~= Tuple!(size_t, Node*)(++v, new Node(x, null, null));
            return;
        }
        Node* r = root[$ - 1][1].insert(x, v);
        if (r)
        {
            root ~= Tuple!(size_t, Node*)(v, r);
        }
    }

    string printAll()
    {
        string result = "digraph g {\n";
        result ~= `"root" [ label="`;
        foreach (i, t; root)
        {
            if (i)
                result ~= " | ";
            result ~= "<v" ~ i.to!string ~ "> v" ~ t[0].to!string;
        }
        result ~= `" shape="record"];` ~ '\n';
        foreach (i, t; root)
        {
            result ~= t[1].printAll();
            result ~= `"root":v` ~ i.to!string ~ ` -> "n` ~ t[1].to!string ~ `"` ~ "\n";
        }
        result ~= "}";
        return result;
    }

    string print(size_t v)
    {
        if (root.length == 0)
            return "";
        size_t i;
        while (i < root.length && root[i][0] <= v)
            i++;
        string result = "digraph g {\n";
        result ~= root[i - 1][1].print(v);
        result ~= "}";
        return result;
    }

}

void main()
{
    PersistentBinaryTree!long t;
    while (true)
    {
        write("insert/print [i,p]: ");
        string op = readln();
        if (op[0] == 'i')
        {
            while (true)
            {
                write("value: ");
                long x;
                if (!collectException(readln().chomp().to!long, x))
                {
                    t.insert(x);
                    writeln(x, " inserted. current version: ", t.v);
                    break;
                }
            }
        }
        if (op[0] == 'p')
        {
            while (true)
            {
                write("version [", 1, "-", t.v, "]: ");
                size_t x;
                if (!collectException(readln().chomp().to!size_t, x) && x <= t.v)
                {
                    writeln();
                    t.print(x).writeln();
                    writeln();
                    break;
                }
                else
                {
                    writeln("debug print");
                    writeln();
                    t.printAll().writeln();
                    writeln();
                    break;
                }
            }
        }
    }
}