DTree for Python

Python implementation of DTree, the incremental encoding of directed trees by two projections Q1 and Q2 (see the API reference and the paper). No dependencies; Python 3.8+.

pip install dtree-encoding

The package is imported as dtree.

from dtree import DTree

t = DTree("P1")
t.insert("A", "B")
t.insert("B", "C")

t.can_reach("A", "C")    # True
t.path_to_root("C")      # ['C', 'B', 'A']
t.q1, t.q2               # (['A', 'B', 'C'], ['A', 'B', 'C'])

t.insert("A", "D")
t.cut_n_paste("C", "D")  # move subtree C under D
t.delete("B")            # B's children (none left) move up to A
t.delete_subtree("D")    # removes D and C

Load one of the example files (parent: child1; child2 per line):

t = DTree.from_file("Test.csx")   # e.g. examples/Test.csx from the repository

API (C# name → Python name)

Semantics

• can_reach(u, v) is irreflexive: no node reaches itself, so can_reach(u, u) is False. (The C# prototype is reflexive.)
• is_ancestor(u, v) equals can_reach(u, v) and is likewise proper.
• delete(v) re-attaches v's children to v's parent, in v's place among its siblings.
• delete_subtree(v) removes v with all its descendants and returns them in Q1 order.
• cut_n_paste(u, p) moves the subtree rooted at u under p as p's last child; p must not lie inside u's subtree.
• The constructed nodes vmin(S), vmax(S) (S as target) and umin(S), umax(S) (S as source) take the minimum or maximum of each index over S, separately in Q1 and Q2. reaches_all and reached_by_all are exact O(1) tests; may_reach_some and may_be_reached_by_some are only filters, and reaches_some and reached_by_some are exact in O(log k). A constructed node stays valid under insertions and is recomputed automatically after delete, delete_subtree or cut_n_paste. See set queries.
• Projection positions are fractions: a new node gets the mediant (a+c)/(b+d) of its neighbors, so normally no other node moves. Only rare alternating insertion patterns trigger a local renumbering. Tree depth and width are unbounded. t.Q1.index(v) returns a position as a Fraction.

Tests

python -m unittest discover -s tests

Every operation is checked against a brute-force parent/children model on random trees, including random sequences of deletes and moves.

Benchmarks

python benchmarks/bench.py            # trees of 10,000 and 100,000 nodes
python benchmarks/bench.py --quick    # a few seconds
python benchmarks/bench.py --dynamic  # only insertions and queries alternating
python benchmarks/bench.py 1000000    # custom sizes

The script prints Markdown tables: build time and renumbering counts per tree shape (random, chain, star at the root, star at an inner node, alternating worst case), list growth at either end, and timings for can_reach, depth, delete, cut_n_paste and delete_subtree, and comparisons with a classical parent walk: reachability by tree depth, set queries with constructed nodes, and dynamic updates (insertions and queries alternating). Each DList keeps the counters renumber_count and renumber_moved, so the same figures are available in your own code via t.Q1 and t.Q2.

Provenance

Design and API: Enis Olgac. This Python port was written with Claude (Anthropic) from the C# original and the API reference.