Documentation

Linglib.Core.Data.RoseTree.BinaryTree

Forests as binary trees #

This file defines Knuth's natural correspondence between forests of rose trees and binary trees, and deduces that rose trees over an encodable type are encodable. The binary tree of a nonempty forest has the root of the first tree as its root, the binary tree of that tree's children as its left subtree and the binary tree of the remaining trees as its right subtree: this is the left-child right-sibling representation. A rose tree is its root value together with the forest of its children, hence a value together with a binary tree.

Main definitions #

Main results #

References #

def BinaryTree.ofForest {α : Type u_1} :
List (RoseTree α) → BinaryTree α

The binary tree of a forest under the natural correspondence: nil for the empty forest, otherwise its first tree consed onto the binary tree of the rest.

Equations
Instances For
    def BinaryTree.cons {α : Type u_1} :
    RoseTree α → BinaryTree α → BinaryTree α

    cons t r is the binary tree of the forest t :: toForest r: a node with the root value of t, the binary tree of the children of t on the left and r on the right.

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

      The forest of a binary tree, inverse to BinaryTree.ofForest.

      Equations
      Instances For
        @[simp]
        theorem BinaryTree.ofForest_nil {α : Type u_1} :
        ofForest [] = nil
        @[simp]
        theorem BinaryTree.ofForest_cons {α : Type u_1} (t : RoseTree α) (rest : List (RoseTree α)) :
        ofForest (t :: rest) = cons t (ofForest rest)
        @[simp]
        theorem BinaryTree.cons_node {α : Type u_1} (a : α) (cs : List (RoseTree α)) (r : BinaryTree α) :
        cons (RoseTree.node a cs) r = node a (ofForest cs) r
        @[simp]
        theorem BinaryTree.toForest_nil {α : Type u_1} :
        nil.toForest = []
        @[simp]
        theorem BinaryTree.toForest_node {α : Type u_1} (a : α) (l r : BinaryTree α) :
        (node a l r).toForest = RoseTree.node a l.toForest :: r.toForest
        @[simp]
        theorem BinaryTree.toForest_ofForest {α : Type u_1} (cs : List (RoseTree α)) :
        (ofForest cs).toForest = cs
        @[simp]
        theorem BinaryTree.toForest_cons {α : Type u_1} (t : RoseTree α) (r : BinaryTree α) :
        (cons t r).toForest = t :: r.toForest
        @[simp]
        theorem BinaryTree.ofForest_toForest {α : Type u_1} (t : BinaryTree α) :
        def BinaryTree.equivForest {α : Type u_1} :
        BinaryTree α ≃ List (RoseTree α)

        The natural correspondence between binary trees and forests.

        Equations
        Instances For
          @[simp]
          theorem BinaryTree.equivForest_symm_apply {α : Type u_1} (a✝ : List (RoseTree α)) :
          equivForest.symm a✝ = ofForest a✝
          @[simp]
          theorem BinaryTree.equivForest_apply {α : Type u_1} (a✝ : BinaryTree α) :
          equivForest a✝ = a✝.toForest
          theorem BinaryTree.numNodes_ofForest {α : Type u_1} (cs : List (RoseTree α)) :
          (ofForest cs).numNodes = (List.map RoseTree.numNodes cs).sum
          theorem BinaryTree.numNodes_cons {α : Type u_1} (t : RoseTree α) (r : BinaryTree α) :
          (cons t r).numNodes = t.numNodes + r.numNodes
          def RoseTree.equivProdBinaryTree {α : Type u_1} :
          RoseTree α ≃ α × BinaryTree α

          A rose tree is its root value together with the binary tree of the forest of its children.

          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            @[simp]
            theorem RoseTree.equivProdBinaryTree_symm_apply {α : Type u_1} (p : α × BinaryTree α) :
            @[instance_reducible]
            instance RoseTree.encodable {α : Type u_1} [Encodable α] :
            Encodable (RoseTree α)
            Equations
            instance RoseTree.countable {α : Type u_1} [Countable α] :
            Countable (RoseTree α)