Documentation

Linglib.Core.Data.RoseTree.Subtree

Subtrees of a rose tree #

A tree s is a subtree of t when it is rooted at a node of t, reached from t by descending through children. The relation is a partial order, since a proper subtree has fewer nodes, and RoseTree.subtrees lists the subtrees of a tree in preorder, one per node, which decides the relation. The subtrees are the trees found at the addresses of the tree, as RoseTree/Get.lean shows.

theorem RoseTree.numNodes_lt_of_mem {α : Type u_1} {t c : RoseTree α} (h : c ∈ t.children) :
def RoseTree.IsSubtree {α : Type u_1} (s t : RoseTree α) :

IsSubtree s t holds when s is the subtree of t rooted at one of its nodes, reached from t by descending through children.

Equations
Instances For
    theorem RoseTree.IsSubtree.refl {α : Type u_1} (t : RoseTree α) :
    theorem RoseTree.IsSubtree.trans {α : Type u_1} {r s t : RoseTree α} (h₁ : r.IsSubtree s) (h₂ : s.IsSubtree t) :
    theorem RoseTree.IsSubtree.of_mem_children {α : Type u_1} {c t : RoseTree α} (h : c ∈ t.children) :
    theorem RoseTree.IsSubtree.map {α : Type u_1} {β : Type u_2} {s t : RoseTree α} (f : α → β) (h : s.IsSubtree t) :

    Relabelling preserves the subtree relation.

    theorem RoseTree.isSubtree_node_iff {α : Type u_1} {s : RoseTree α} {a : α} {cs : List (RoseTree α)} :
    s.IsSubtree (node a cs) ↔ s = node a cs ∨ ∃ (c : RoseTree α), c ∈ cs ∧ s.IsSubtree c
    @[simp]
    theorem RoseTree.isSubtree_leaf_iff {α : Type u_1} {s : RoseTree α} {a : α} :
    s.IsSubtree (leaf a) ↔ s = leaf a
    theorem RoseTree.IsSubtree.numNodes_le {α : Type u_1} {s t : RoseTree α} (h : s.IsSubtree t) :
    theorem RoseTree.IsSubtree.eq_of_numNodes_le {α : Type u_1} {s t : RoseTree α} (h : s.IsSubtree t) (hn : t.numNodes ≤ s.numNodes) :
    s = t
    theorem RoseTree.IsSubtree.antisymm {α : Type u_1} {s t : RoseTree α} (h₁ : s.IsSubtree t) (h₂ : t.IsSubtree s) :
    s = t
    instance RoseTree.instIsPartialOrderIsSubtree {α : Type u_1} :
    IsPartialOrder (RoseTree α) IsSubtree
    def RoseTree.subtrees {α : Type u_1} :
    RoseTree α → List (RoseTree α)

    subtrees t lists the subtrees of t in preorder, t first, one per vertex.

    Equations
    Instances For
      def RoseTree.subtreesList {α : Type u_1} :
      List (RoseTree α) → List (RoseTree α)

      subtreesList cs lists the subtrees of the trees of cs.

      Equations
      Instances For
        theorem RoseTree.subtreesList_eq {α : Type u_1} (cs : List (RoseTree α)) :
        subtreesList cs = List.flatMap subtrees cs
        @[simp]
        theorem RoseTree.subtrees_node {α : Type u_1} (a : α) (cs : List (RoseTree α)) :
        (node a cs).subtrees = node a cs :: List.flatMap subtrees cs
        theorem RoseTree.mem_subtrees {α : Type u_1} {s t : RoseTree α} :
        s ∈ t.subtrees ↔ s.IsSubtree t

        The listed subtrees are exactly the subtrees.

        theorem RoseTree.self_mem_subtrees {α : Type u_1} (t : RoseTree α) :
        t ∈ t.subtrees
        theorem RoseTree.subtrees_map {α : Type u_1} {β : Type u_2} (f : α → β) (t : RoseTree α) :
        (map f t).subtrees = List.map (map f) t.subtrees
        @[instance_reducible]
        instance RoseTree.instDecidableIsSubtreeOfDecidableEq {α : Type u_1} [DecidableEq α] (s t : RoseTree α) :
        Decidable (s.IsSubtree t)
        Equations