File TreeSort.h

↰ Parent directory (ADS/sort)

The tree sort, beyond the book: the items are inserted in a search tree [see File SearchTree.h] and read back by the symmetric visit, which gives the keys in increasing order; each key keeps the number of its copies, so that the repeated items are not lost.

Definition (ADS/sort/TreeSort.h)

Detailed Description

On a Red-Black tree the insertions take :math:` O( n log n ) ` time in the worst case, and on a binary search tree with no balance :math:` Theta( n^2 ) ` on a sorted input, which is why the sort is the example of the cost of the balance; it is also the natural sort of a functional language, which builds the tree by recursion and flattens it.

The contracts [see File Contract.h]: the vector ends with the same items sorted, an audit. The function is defined in TreeSort.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 6.1, https://algoritmicamente.it/materiali/libro/capitoli/cap06.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions