Template Function ADS::minimumHeightSearchTree(const std::vector<T>&, Make, Compare)

• Defined in File BinaryTreeAlgorithms.h

Function Documentation

template<class T, class Make, class Compare = std::less<>>
auto ADS::minimumHeightSearchTree(const std::vector<T> &A, Make make, Compare less = {}) -> std::invoke_result_t<Make&, const T&, std::nullptr_t, std::nullptr_t>

minimumHeightSearchTree(): the binary search tree of the keys of A of the least height, the lower middle key at the root of each subtree, whose nodes are made by make( v , l , r ) over the subtrees l and r, nil if A is empty; O( n ) time

Pre:

A strictly increasing by less

Post:

the height is ceil( log2( n + 1 ) ) - 1 (an audit)