ComparisonTree
inductive
A binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
Statement
inductive ComparisonTree (n : ℕ) : Type
- Defined in
- arXiv:2610.18740 Sec. 3.1
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Used by 18
- v_selection_three_two_upper_boundThe 2nd smallest (the median) of 3 distinct elements can be found using at most 3 pairwise comparisons, that is, V_2(3) ≤ 3.
- comparison_tree_selects_rank_existsFor every n and every rank r : Fin n there exists a comparison decision tree on n elements that correctly selects the element of rank r.
- comparison_tree_correct_for_selectionGiven a natural number n, a partial order P on Fin n, a rank i, and a comparison tree t on n elements, t correctly selects the i-th…
- comparison_tree_num_leaves_le_two_pow_depthFor any natural number n and any comparison decision tree T on n elements, the number of leaves of T is at most 2 raised to the depth of T.
- comparison_selection_complexityThe worst-case comparison complexity to select the element of rank r : Fin n among n elements, defined as the infimum of the depths of all…
- comparison_tree_bindComposition of comparison decision trees: run
T, and at each leafacontinue with the treef a. Recursion peels off the first stage… - comparison_tree_selects_rankA comparison decision tree T on n elements (T : ComparisonTree n) correctly selects the element of rank r : Fin n if for every permutation…
- v_selection_le_iffFor any positive rank i ≤ n and bound d, the worst-case comparison complexity V_i(n) is at most d if and only if there exists a comparison…
- comparison_tree_num_leavesThe number of leaves in a comparison decision tree is 1 for a leaf, and the sum of the leaf counts of its left and right subtrees for an…
- v_selection_16_8_le_28_iff_exists_treeThe worst-case comparison complexity of selecting the 8th smallest element among 16 elements is at most 28 (that is, V_8(16) ≤ 28) if and…
- comparison_tree_depth_bind_leIf every continuation tree
f ahas depth at mostd, thencomparison_tree_bind T fhas depth at mostcomparison_tree_depth T + d:… - v_selection_posetFor a natural number n, a partial order P on Fin n, and a rank i, V_i(P) is the infimum of depths of all comparison decision trees on n…
- comparison_tree_depthThe depth of a comparison decision tree is the maximum number of comparisons along any branch from the root to a leaf.
- comparison_tree_eval_bindRunning the composition
comparison_tree_bind T fon a value assignmentvgives the same index as runningTonvand then running… - comparison_tree_correct_for_selection_existsFor every natural number n, strict partial order P on Fin n, and rank 1 ≤ i ≤ n, there exists a comparison decision tree on n elements…
- not_comparison_tree_selects_rank_two_leaf_oneFor n = 2, the leaf comparison decision tree returning index 0 does not correctly select rank 1.
- comparison_tree_selects_rank_one_zeroFor n = 1, the single leaf comparison decision tree returning index 0 correctly selects rank 0.
- comparison_tree_evalGiven an assignment v : Fin n → α of values in a linearly ordered type α, evaluate a comparison tree: on a leaf leaf ans, return the index…
Read back from the Lean
An inductive type family ComparisonTree (n : ℕ) representing binary comparison trees over indices in Fin n, with two constructors:
- leaf: takes an index ans : Fin n and produces a tree.
- branch: takes two indices i, j : Fin n and two child trees left, right : ComparisonTree n, and produces a tree.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A deterministic comparison decision tree for elements indexed by Fin n. -/ inductive ComparisonTree (n : ℕ) : Type | leaf (ans : Fin n) : ComparisonTree n | branch (i j : Fin n) (left right : ComparisonTree n) : ComparisonTree n