BST: remove less than

[Ridimz]

I have implemented a binary search tree and am interested in displaying all
keys less than a certain value. I understand how to approach this task if
the searchValue is equal to root.key(). Otherwise I'm lost. Any suggestions
or examples would be greatly appreciated

Thanks,
Ridimz

 

[Mike Wahler]

I have implemented a binary search tree and am interested in displaying all
keys less than a certain value. I understand how to approach this task if
the searchValue is equal to root.key(). Otherwise I'm lost. Any suggestions
or examples would be greatly appreciated

Without seeing any specific code or specific questions,
all I can say is that you can use the 'less than'
relational operator < to determine whether one value
is less than another.

if(x < y)
// value of 'x' is less than value of 'y'

-Mike

 

[Josh Sebastian]

I have implemented a binary search tree and am interested in displaying all
keys less than a certain value. I understand how to approach this task if
the searchValue is equal to root.key(). Otherwise I'm lost. Any suggestions
or examples would be greatly appreciated

In a BST, all elements less than the current node's value are to
the left. So keep moving down and to the left until you find the first
node with a value less than you value, and display the values of all the
nodes on the subtree with that node for the root.

Josh

 

[Richard Heathfield]

In a BST, all elements less than the current node's value are to
the left. So keep moving down and to the left until you find the first
node with a value less than you value, and display the values of all the
nodes on the subtree with that node for the root.

(Please select a non-proportional font.)

Let's test that theory. I'm looking for anything less than H in the
following tree:

M
F R
D I P U
A E G J N Q T W

Your algorithm starts by going from M to F. F is less than H, so your
algorithm will display the values of all the nodes on the subtree with F at
the root. These are A, D, E, F, G, I, J.

Neither I nor J is < H. I conclude that the algorithm is flawed.

 

[Ridimz]

Gentlemen,

Your suggestions successfully got me into the right frame of mind to solve
my proble.

Thank you!
Ridimz

 

[Karl Heinz Buchegger]

I have implemented a binary search tree and am interested in displaying all
keys less than a certain value. I understand how to approach this task if
the searchValue is equal to root.key(). Otherwise I'm lost. Any suggestions
or examples would be greatly appreciated

What do you know about a node in a BST and it's relationship to
the subnodes.

You know that in the left subtree of that node there are only nodes with
values less then the current nodes value. In the right subtree there
are only nodes with values greater then the current node.

So if you start at the root. Look at the roots value.
If it is greater then the value you use for the limit,
then you know imediatly that all nodes in the right subtree are
also greater then your limit. None of that nodes can be in your
output set. What about the nodes in the left subtree? Well.
They clearly are less then the roots node, but are they also less
then your limit? Some may be, some may not be. So you need to investigate
further.
What happens if a you encounter a tree node, which has a value less then your
limit. Well. You know imediatly that all nodes in the left subtree are clearly
less then your limit and belong to the output set. What about the nodes in
the right subtree? Some of them might be less then your limit, some may not.
Further investigation is neccessarry.

From all of this, you could come up with a strategy as follows (pseudocode)

SearchLessThenLimit( node, limit )
{
if( node->value > limit ) {
// right subtree is unimportant, can be ignored
// as can this node
SearchLessThenLimit( node->left, limit )
}

else {
if( node->value < limit ) {
output( node );
}
OutputAllIn( node->left );
SearchLessThenLimit( node->right, limit )
}
}

 

[Stuart Golodetz]

I have implemented a binary search tree and am interested in displaying all
keys less than a certain value. I understand how to approach this task if
the searchValue is equal to root.key(). Otherwise I'm lost. Any suggestions
or examples would be greatly appreciated

Thanks,
Ridimz

void output_all_less_than(const T& t, std:stream& os = std::cout, const
Node *pNode = NULL) const
{
if(!pNode)
{
if(!m_nodes.empty()) pNode = &m_nodes.front();
else return;
}
if(Pred()(t, pNode->m_data) || t == pNode->m_data)
{
if(pNode->m_pLeft) output_all_less_than(t, os, pNode->m_pLeft);
}
else
{
if(pNode->m_pLeft) output_all_less_than(t, os, pNode->m_pLeft);
os << pNode->m_data << ' ';
if(pNode->m_pRight) output_all_less_than(t, os, pNode->m_pRight);
}
}

HTH,

Stuart.

 

[Stuart Golodetz]

void output_all_less_than(const T& t, std:stream& os = std::cout, const
Node *pNode = NULL) const
{
if(!pNode)
{
if(!m_nodes.empty()) pNode = &m_nodes.front();
else return;
}
if(Pred()(t, pNode->m_data) || t == pNode->m_data)
{
if(pNode->m_pLeft) output_all_less_than(t, os, pNode->m_pLeft);
}
else
{
if(pNode->m_pLeft) output_all_less_than(t, os, pNode->m_pLeft);

Sorry, the above line could be more efficient:
if(pNode->m_pLeft) output(os, pNode->m_pLeft); // code for
output(std:stream&, const Node*) const not posted (but trivial to
implement)

Cheers,

Stuart.

 

[Josh Sebastian]

I conclude that the algorithm is flawed.

Umm... I left it as an exercise for the reader? Thanks Richard. OTOH, it's
pretty easy to go from my "algorithm" to the correct answer.

Josh