A decision tree for ordering is a binary tree that represents a method for ordering based on comparisons. The figure illustrates such a decision tree for a three-element vector. Each node, not a leaf,...

Tarea#4: Arboles Binarios para Ordenamiento
Task#4:
Binary Trees for Ordering
Ebert Marquez
15-06637
Translated from Spanish to English - www.onlinedoctranslator.com
1
Presentation Topics
TOPIC 1:Show that a decision tree that never makes a redundant comparison has n! sheets.
TOPIC 2:Minimum depth of a decision tree is
THEME 3:Show that the depth of such a tree is O(n log n)
THEME 4:Explain why this proves that any classification method that uses comparisons on a tree of size n must make at least O(n log n) comparisons.
THEME 5:Implementation of a binary tree for sorting in C
There is a great variety of trees with many and diverse applications in the world of computing.
two
Introduction
Binary trees are a representation of a graph which uses nodes that point to a right child and a left child, throughout this presentation we will see that an important application of them is the representation of ordering algorithms, giving us a direct relationship between the efficiency of a binary tree and that of any sorting algorithm, which is why this type of data structure is really important in our daily lives.
3
Show that a decision tree that never makes a redundant comparison has n! sheets.
TOPIC 1
4
Array size permutations
Relationship to permutations
It is important to note that for an array of n elements the minimum number of ways to rearrange those n elements in n spaces perfectly matches the definition of permutation. You have to place n elements in n cells.
__ < __ < __ < … < __ < __ < __
N N-1 N-2 … 3 2 1
CONCEPT OF PERMUTATION
The permutations of n elements in n spaces are precisely n! shapes, this is because if I have n elements when I place one in any of the n positions I am left with n-1 positions left to place n-1 elements, if we continue this process iteratively we will lower the number of possible shapes until we only have a space remains, that is, n! shapes
5
Show that the minimum depth of a tree of
decisions is
TOPIC 2
6
Minimum height of a binary...