DTree for Python

DTree has moved to Triordinal (from version 2.0.0, October 29, 2026; Zenodo doi:10.5281/zenodo.23760809). The API is unchanged; please install triordinal-dtree (Python, from triordinal.dtree import DTree) or Triordinal.DTree (NuGet). This repository keeps versions 1.0.0 to 1.9.0; dtree-encoding 1.9.0 only forwards to triordinal-dtree.

Python implementation of DTree, the incremental encoding of the topology 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

• Every method accepts a node name or a node handle (DNode). insert returns the handle of the new node, get_node(name) gives the handle of an existing one. A handle refers directly to the node's positions in Q1 and Q2, so can_reach on handles is two position comparisons without any lookup by name. Handles of deleted nodes, or of another tree, are rejected (KeyError) or reported as unreachable.

• 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.

• And/or queries on the topology: 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). Members are added with add and removed with discard. A constructed node stays valid under insertions and is recomputed automatically after delete, delete_subtree or cut_n_paste. See and/or queries on the topology.

• 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

The benchmarks come with the package, so you can measure on your own machine:

python -m dtree.bench            # trees of 10,000 and 100,000 nodes
python -m dtree.bench --quick    # a few seconds
python -m dtree.bench --dynamic  # only the dynamic updates and the tree view
python -m dtree.bench --note "idle machine"   # remark for the report
python -m dtree.bench 1000000    # custom sizes

In a clone of the repository, python python/benchmarks/bench.py runs the same code from the sources.

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, and/or queries with constructed nodes, dynamic updates (insertions with 1 or 10 queries each, and static pre/post numbers at depths 100 and 1,000), and a tree view with expand/collapse. Each dynamic measurement is the best of three runs. 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.

Every run also writes its tables as a Markdown report to benchmarks/python/—in the current directory, or at the repository root when run inside a clone— named after date and time (for example 2026-10-17_14-18.md), with a header giving the DTree and Python versions, the operating system and the processor; --no-save skips it. The C# benchmarks (dotnet run --project csharp/DTree.Tests -c Release -- bench) write theirs to benchmarks/csharp/.

Provenance

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