Пусть у нас есть следующая функция, которая берет указатель на root и возвращает true при поиске элемента, а false в противном случае
/**
* A method to test if an item is in a subtree.
* x is item to search for.
* ptr is the node that roots the subtree.
*/
template<typename T>
bool contains( const T & x, Node *t ) const
{
if( ! ptr ) return false;
else if( x < ptr->data ) return contains( x, ptr->left );
else if( ptr->data < x ) return contains( x, ptr->right );
else return true; // Match
}
Ожидаемое используемое пространство стека вызовов, как ожидается, быть O(log(N)) из-за копирования указателей при каждом вызове.
Теперь, если мы заменим предыдущий код следующим, будет ли использование пробела нулевым или как?
template<typename T>
bool contains( const T & x, Node* & ptr ) const
{
if( !ptr ) return false;
else if( x < ptr->data ) return contains( x, ptr->left );
else if( ptr->data < x ) return contains( x, ptr->right );
else return true; // Match
}