from __future__ import annotations
class Tree:
"""A tree.
Parameters
----------
data : str
The data contained in this tree.
children : list[Tree] or tuple[Tree, ...]
The subtrees of this tree.
"""
def __init__(
self,
data: str,
children: list[Tree] | tuple[Tree, ...] | None = None,
) -> None:
if children is not None and not isinstance(children, (list, tuple)):
raise TypeError("children must be a finite list or tuple of trees")
self._data = data
self._children = tuple(() if children is None else children)
self._validate()
def _validate(self) -> None:
"""Reject non-trees, cycles, and shared subtree objects."""
seen = {id(self)}
def visit(node: Tree) -> None:
if not isinstance(node, Tree):
raise TypeError("all children must be trees")
if id(node) in seen:
raise ValueError("trees cannot contain cycles or shared subtrees")
seen.add(id(node))
for child in node._children:
visit(child)
for child in self._children:
visit(child)
@property
def data(self) -> str:
"""The data at this node."""
return self._data
@property
def children(self) -> tuple[Tree, ...]:
"""The subtrees of this node."""
return self._children
def __str__(self) -> str:
if self._children:
return ' '.join(c.__str__() for c in self._children)
else:
return str(self._data)
def __repr__(self) -> str:
return self.to_string(0)
def to_string(self, depth: int = 0) -> str:
"""Render the tree as an indented string.
Parameters
----------
depth : int
The current depth for indentation.
Returns
-------
str
An indented text representation of the tree.
"""
s = (depth - 1) * ' ' +\
int(depth > 0) * '--' +\
self._data + '\n'
s += ''.join(c.to_string(depth+1)
for c in self._children)
return s
def __contains__(self, data: str) -> bool:
# pre-order depth-first search
if self._data == data:
return True
else:
for child in self._children:
if data in child:
return True
return FalseContainment Tests
Suppose I’m interested in finding all sentences with a definite determiner in a subject. This means checking whether a particular subtree (corresponding to the subject) contains a particular element.
Let’s figure out how to compute whether a tree contains a particular piece of data, and then we’ll get back to figuring out how to grab the relevant subtree.
Containment tests for a class are often implemented in the __contains__ magic method, which defines the behavior of in. What should this method do for a tree? It should take a piece of data and tell us whether that data occurs at any node. This is the tree analogue of asking whether a list contains an element.
For a list, containment could be naturally implemented using a for-loop. So suppose we’re redefining the list class, __contains__ could be implemented something like this:
def __contains__[T](self: list[T], data: T) -> bool:
for d in self:
if d == data:
return True
return FalseThe implementation for Tree will follow the same basic idea, but a tree is not a single sequence. We’ll compare two ways of visiting its nodes:
- depth-first search
- breadth-first search
In both kinds of search, we start at the top of the tree and work our way down, the question is which nodes we look at.
Depth-first search
We’ll look at two ways we can implement depth-first search: pre-order and post-order.
Pre-order depth-first search
To conduct pre-order depth-first search, we inspect the root first. We then search each child subtree from left to right, applying the same root-before-children order within each child.
This search path is visualized in the image below, where the line is our traversal path and the dots mark when we look at a piece of data in a node.
Why recursive containment is correct
So when should data in t return True? Exactly when some node of t stores data. We’ll call this the containment invariant. Let’s check the two directions separately by structural induction on t.
Start with a leaf t. If its data equals the target, the first branch returns True. If its data differs, the child loop has no iterations and the method returns False. The claim thus holds for a leaf.
Now fix a tree t and suppose that the containment invariant holds for each child. There are two ways the method can return True. First, the root data may equal the target, in which case the root itself witnesses containment. Second, a recursive call on some child may return True; by the induction hypothesis, that child contains a matching node, which is also a node of t. So every positive result has a witness in the tree.
Conversely, suppose some node of t stores the target. If that node is the root, the first branch returns True. Otherwise, the node belongs to exactly one child subtree. The induction hypothesis makes the recursive call on that child return True, so the loop returns True. Every matching node is thus found.
We have now shown both directions: every True result has a matching node as a witness, and every matching node is found. So the method returns True exactly for trees containing the target. Pre-order determines when a witness is found, but not whether one exists.
tree = Tree('S',
[Tree('NP',
[Tree('D',
[Tree('a')]),
Tree('N',
[Tree('greyhound')])]),
Tree('VP',
[Tree('V',
[Tree('loves')]),
Tree('NP',
[Tree('D',
[Tree('a')]),
Tree('N',
[Tree('greyhound')])])])])"loves" in tree, "hates" in tree%%timeit
"loves" in tree%%timeit
"hates" in treePost-order depth-first search
In post-order depth-first search, we recursively inspect each child subtree from left to right and inspect the current root only after all of its child subtrees.
class Tree(Tree):
def __contains__(self, data: str) -> bool:
# post-order depth-first search
if not self._children:
return self._data == data
else:
for c in self._children:
if data in c:
return True
return self._data == dataDoes changing the visit order change the answer? It should not. The post-order version satisfies the same containment invariant. For a leaf, not self._children is true, so the method compares the leaf’s data with the target. The one-node tree contains the target exactly when that comparison returns True.
Now suppose the invariant holds for every child of a nonleaf. The method searches those children first and checks the root last. If a child call succeeds, the induction hypothesis supplies a matching descendant; if the final root comparison succeeds, the root supplies the match. Conversely, any matching node is either in a child, where the induction hypothesis finds it, or at the root, where the last line finds it. Thus, pre-order and post-order may stop at different times while returning the same boolean answer.
tree = Tree('S',
[Tree('NP',
[Tree('D',
[Tree('a')]),
Tree('N',
[Tree('greyhound')])]),
Tree('VP',
[Tree('V',
[Tree('loves')]),
Tree('NP',
[Tree('D',
[Tree('a')]),
Tree('N',
[Tree('greyhound')])])])])"loves" in tree, "hates" in treeBreadth-first search
Rather than recursing through one subtree before moving to the next, breadth-first search inspects the data at every node of depth \(i\) before proceeding to depth \(i+1\).
One natural way to implement breadth-first search is iterative deepening depth-first search.
class Tree(Tree):
@property
def depth(self) -> int:
"""The maximum depth of the tree."""
if self._children:
return 1 + max(c.depth for c in self._children)
else:
return 0
def __contains__(self, data: str) -> bool:
# breadth-first search
for d in range(self.depth + 1):
if self._iddfs(data, d):
return True
return False
def _iddfs(self, data: str, depth: int) -> bool:
# iterative deepening depth-first search
if depth == 0:
return self._data == data
elif depth > 0:
for c in self._children:
if c._iddfs(data, depth-1):
return True
return FalseWhy iterative deepening searches every level
What exactly does the helper answer? t._iddfs(data, d) returns True if and only if a node exactly \(d\) edges below the root of t stores data. We’ll call this the exact-depth invariant.
At \(d=0\), the only node zero edges below the root is the root itself. The helper compares exactly that node’s data with the target, so the claim holds.
For \(d>0\), suppose the claim holds at depth \(d-1\) for every child. A node exactly \(d\) edges below t must be exactly \(d-1\) edges below one of its children. The loop asks each child that question. If one call returns True, the induction hypothesis supplies a target node at the required depth. And if such a node exists, it lies under some child, whose recursive call returns True by the same hypothesis. The helper thus satisfies the exact-depth invariant in both directions.
It remains to check the outer loop’s bounds. The depth property is the maximum root-to-leaf distance: a leaf has depth \(0\), and a nonleaf has one plus the maximum child depth. Thus, every node occurs at one of the depths \(0,\ldots,\texttt{self.depth}\). The loop must include both endpoints, which is why it uses range(self.depth + 1). On the example tree, the visits are:
| depth | node data inspected |
|---|---|
| 0 | S |
| 1 | NP, VP |
| 2 | D, N, V, NP |
| 3 | a, greyhound, loves, a, greyhound |
A target such as loves is found only on the final iteration. The table also shows why the outer loop must include depth \(3\). Combining the exact-depth invariant with this inclusive loop gives the desired result: breadth-first containment returns True exactly when the target occurs somewhere in the tree.
tree = Tree('S',
[Tree('NP',
[Tree('D',
[Tree('a')]),
Tree('N',
[Tree('greyhound')])]),
Tree('VP',
[Tree('V',
[Tree('loves')]),
Tree('NP',
[Tree('D',
[Tree('a')]),
Tree('N',
[Tree('greyhound')])])])])"loves" in tree, "hates" in tree