trees and binary trees

[sagetrac-elixyre]

Hi,

I propose several methods for trees and binary trees:

File : trees_classicals_algorithms_EliX-jbp:
several classical operations on trees and binary trees

• on abstract trees:
  • depth pre/post order transversal algorithm
  • breadth first order transversal algorithm
• on binary trees:
  • infix order transversal algorithm
  • canonical permutation associated to the left/right binary search tree insertion
  • left/right rotate (for labelled and unlabelled BT)

File: trees_research_algorithms_EliX-jbp:
several research algorithms on binary trees

• over/under (Loday-Ronco)
• pred/succ in the Tamari lattice
• hook length formula

File: trees_latex_output_EliX-jbp:
a method for nice latex output

Apply:

• attachment: trac_14498-algorithms_trees-rebased.patch​
• attachment: trac_14498-tree-imps-dg-rebased.patch​
• attachment: trac_14998-more-edits-dg.patch​
• attachment: trac_14498-further-docfixes-dg.patch​

Depends on #8703
Depends on #14784

CC: @hivert @VivianePons @fchapoton @nathanncohen

Component: combinatorics

Keywords: trees, binary trees, latex

Author: Jean-Baptiste Priez

Branch/Commit: public/ticket/14498 @ 4e8fdd0

Reviewer: Darij Grinberg, Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/14498

[sagetrac-elixyre]

Attachment: trac_14498_trees_classicals_algorithms_EliX-jbp.patch.gz

[sagetrac-elixyre]

Attachment: trac_14498_trees_latex_output_EliX-jbp.patch.gz

Attachment: trac_14498_trees_research_algorithms_EliX-jbp.patch.gz

[fchapoton]

comment:2

Maybe there is a dependency on #8703 ?

[sagetrac-elixyre]

comment:3

Replying to @fchapoton:

Maybe there is a dependency on #8703 ?

Yes that's true.

[sagetrac-elixyre]

Dependencies: #8703

[darijgr]

comment:4

A nice step towards the Hopf algebras. Some comments:

@Classical algorithms:

Typo appearing twice: "explorer" (should be "explores"). Also, "An other" -> "Another".

Not sure, but I also think "transversal" should be "traversal".

The docstrings fail to explain an important point: what exactly "manipulate" means (and, correspondingly, what the "action" variable is for). The first time I read them I thought the methods output the list of nodes in the respective order! The doc for in_order_transversal should explain the difference between node_action and leaf_action. By the way, why do the other methods have only 1 type of action?

The example for in_order_transversal has two different things called "b". Not a big issue, of course.

I don't understand what "the canonical permutation associated to the binary search tree insertion" is supposed to mean; is this a notation from one of Loday(-Ronco)'s papers?

Copypaste error: the docstring for left_rotate says "Right". (Both times.)

@Research algorithms:

Is computing the hook_length_formula by symbolic integration really easier than just recursively multiplying the hook_length_formulas for the left and right subtrees and then multiplying by an appropriate binomial coefficient? I'm not saying it isn't, just asking.

[fchapoton]

comment:5

Some doctests are failing, please correct them.