Decision Trees of Algorithms and a Semivaluation to Measure Their Distance | Zendy

M. O' Keeffe | Zendy; Homeira Pajoohesh | Zendy; Michel Schellekens | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Decision Trees of Algorithms and a Semivaluation to Measure Their Distance

Author(s) -

M. O' Keeffe,

Homeira Pajoohesh,

Michel Schellekens

Publication year - 2006

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2006.04.032

Subject(s) - ternary search tree , weight balanced tree , random binary tree , binary search tree , binary tree , binary decision diagram , sort , optimal binary search tree , lattice (music) , mathematics , algorithm , binary number , combinatorics , k ary tree , extension (predicate logic) , decision tree , time complexity , interval tree , computer science , tree structure , data mining , arithmetic , physics , acoustics , programming language

We use the set Tn of binary trees with n leaves to study decision trees of algorithms. The set Tn of binary trees with n leaves can be ordered by the so called “imbalance” order, where two trees are related in the order iff the second is less “balanced” than the first. This order forms a lattice. We show that this lattice is nonmodular and extend the imbalance lattice with an algebraic operation. The operation corresponds to the extension of a binary tree with new binary trees at the leafs, which reflects the effect of recursive calls in an algorithm on the decision tree and we will characterize as an illustration the decision tree of the insertion sort algorithm.We investigate the semivaluations on the binary trees which is related to the running time of the algorithm

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research