tree
Let an agent reason about tree-shaped data as a structure with invariants that can be checked and broken, rather than as a picture of a hierarchy.
Research draft, second pass
A second pass drafted this model: the structure a model of this thing needs, and what is known about it in the world. The line under this one says how the second half was obtained - researched against sources, or recalled without web access, in which case nothing here was read anywhere and every claim is a lead to verify. Unreviewed either way.
written by Claude from model knowledge without web access - no source was read, every claim is a lead to verify
Researched by: Claude
Purpose and description
Let an agent reason about tree-shaped data as a structure with invariants that can be checked and broken, rather than as a picture of a hierarchy.
A data structure of nodes connected so that each node has exactly one parent except a single root, and no cycles exist.
What it is for: Representing containment, classification, decomposition and any relation where each thing has one place and that place has a path to a root.
It can be traverse it, in orders that give different results; insert, move and delete nodes, each of which can break an invariant; compute depth, ancestry and subtree size, which is why it is used; break it by creating a cycle or a second parent, producing something that is no longer a tree.
Distinguishing features
Exactly one root and one parent per node, which separates it from a general graph and from a forest
Acyclic by definition: a cycle means it was never a tree
Ordered and unordered trees are different structures with the same picture
The structure and the thing it represents are different: a classification is not a tree, it is modelled as one
What it looks like
Nothing to see. Drawings of trees are a convention, and the same structure is drawn root-up, root-down or sideways with no difference in meaning.
Physical character
depth: 1-40 levels - deep trees cause recursion limits and slow lookups
branching factor: 2-1000 children per node
node count: 1-10000000 nodes
How it is recognised
A drawing is not the structure; the invariants are what identify it
A picture that looks like a tree may be a graph with hidden extra edges
The only reliable check is structural: one root, one parent per node, no cycles
Related models
is a kind of - a tree is a graph with extra constraints, and losing them makes it a graph again
is confused with - a homonym; this entry is the data structure and carries none of the biology
represents - the hierarchy is the subject matter; the tree is the representation and can misrepresent it
is confused with - a DAG allows several parents, which is exactly the constraint a tree adds
In practice
Families and kinds
by shape rule: binary, n-ary, balanced, trie
by ordering: ordered, unordered
by storage: pointer, adjacency list, nested set, materialised path
by use: index, syntax tree, file system, taxonomy
Failure modes and hazards
Cycles introduced by a move operation, which turns traversal into an infinite loop
Orphaned nodes after a delete, which leave the structure invalid rather than smaller
Depth beyond what recursion can handle, producing stack exhaustion
Modelling as a tree something that genuinely has several parents, which forces data to be duplicated or lost
Also called
+32
Where this came from
wikidata · CC0 1.0
Also registered as vr.tr.tree
Drafted structure
Bundle to layer to finding to question, as the second pass will find it: 4 bundles · 8 layers · 8 findings · 16 questions.
Structure and invariants What makes it a tree and what breaks it.
A tree is defined by constraints rather than by shape, and every useful property follows from those constraints holding.
Invariants
One root, one parent, no cycles.
Invariants and their enforcement
Which constraints hold and what enforces them.
- Which invariants does this structure maintain, and what enforces each? definition
- What operation could break each one, and how would that be detected? boundary
Ordering and identity
Whether children are ordered and how nodes are named.
Ordering and node identity
Whether order carries meaning and what identifies a node.
- Is this tree ordered, and does the order carry meaning? definition
- What identifies a node independently of its position? provenance
Operations and cost What can be done and what it costs.
The reason to model something as a tree is the cost of its operations, so those costs belong in the model.
Traversal
Orders of visiting and what each yields.
Traversal orders
The orders available and their uses.
- Which traversal orders are meaningful here, and what does each produce? definition
- What is the cost of each traversal in this representation? measurement
Mutation
Insert, move, delete and rebalance.
Mutation and its risks
What changes the structure and what it endangers.
- Which mutations are supported, and at what cost? measurement
- Which mutation is most likely to leave the structure invalid, and what guards it? action
Representation and storage How it is actually stored.
The same tree stored four ways has four different performance profiles and four different failure modes.
Storage form
Pointers, adjacency, nested sets, paths.
Storage representation
How the structure is materialised.
- How is this tree stored, and what does that make cheap or expensive? definition
- What breaks in that representation when the tree is reorganised? boundary
Limits
Depth, size and the boundaries of the implementation.
Implementation limits
Where the representation stops working.
- What depth and size can this representation handle? measurement
- What should happen when those limits are approached? action
Fit to the domain Whether the world being modelled is really a tree.
Most real hierarchies are not trees, and forcing them into one is the modelling error this entry exists to flag.
Domain fit
Whether the subject has one parent per item.
Fitness of the structure
Where the domain resists the tree constraint.
- Does every item in the domain have exactly one parent, and how is that established? boundary
- Which real cases have several parents, and how are they currently handled? definition
Alternatives
What to use when it is not a tree.
When to use something else
The structures that fit better and what they cost.
- What structure fits when the tree constraint fails, and what is lost by switching? action
- How should a partial or approximate hierarchy be recorded honestly? action
What the second pass must settle
- Should the registry separate the abstract structure from its storage representations, since the invariants hold for all and the costs differ?
- How should a model express that a domain is almost a tree, which is the usual real case?
- What is the right way to record which invariant a particular implementation enforces and which it merely assumes?