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]

Re: remove less than


"Ridimz" <ridimz@SPAMyah ooFREE.com> wrote in message
news:drtfb.2051 0$r25.2110@twis ter.southeast.r r.com...[color=blue]
> I have implemented a binary search tree and am interested in displaying[/color]
all[color=blue]
> 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[/color]
suggestions[color=blue]
> or examples would be greatly appreciated[/color]

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
[color=blue]
>
> Thanks,
> Ridimz
>
>[/color]

[Josh Sebastian]

Re: BST: remove less than

On Sat, 04 Oct 2003 06:06:01 +0000, Ridimz wrote:
[color=blue]
> 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[/color]

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]

Re: BST: remove less than

Josh Sebastian wrote:
[color=blue]
> On Sat, 04 Oct 2003 06:06:01 +0000, Ridimz wrote:
>[color=green]
>> 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[/color]
>
> 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.[/color]

(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.

--
Richard Heathfield : binary@eton.pow ernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Ridimz]

Re: remove less than

"Ridimz" <ridimz@SPAMyah ooFREE.com> wrote...

Gentlemen,

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

Thank you!
Ridimz

[Stuart Golodetz]

Re: remove less than

"Ridimz" <ridimz@SPAMyah ooFREE.com> wrote in message
news:drtfb.2051 0$r25.2110@twis ter.southeast.r r.com...[color=blue]
> I have implemented a binary search tree and am interested in displaying[/color]
all[color=blue]
> 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[/color]
suggestions[color=blue]
> or examples would be greatly appreciated
>
> Thanks,
> Ridimz[/color]

void output_all_less _than(const T& t, std::ostream& os = std::cout, const
Node *pNode = NULL) const
{
if(!pNode)
{
if(!m_nodes.emp ty()) 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]

Re: remove less than

"Stuart Golodetz" <sgolodetz@dial .pipex.com> wrote in message
news:3f8178bf$0 $246$cc9e4d1f@n ews.dial.pipex. com...[color=blue]
> "Ridimz" <ridimz@SPAMyah ooFREE.com> wrote in message
> news:drtfb.2051 0$r25.2110@twis ter.southeast.r r.com...[color=green]
> > I have implemented a binary search tree and am interested in displaying[/color]
> all[color=green]
> > keys less than a certain value. I understand how to approach this task[/color][/color]
if[color=blue][color=green]
> > the searchValue is equal to root.key(). Otherwise I'm lost. Any[/color]
> suggestions[color=green]
> > or examples would be greatly appreciated
> >
> > Thanks,
> > Ridimz[/color]
>
> void output_all_less _than(const T& t, std::ostream& os = std::cout, const
> Node *pNode = NULL) const
> {
> if(!pNode)
> {
> if(!m_nodes.emp ty()) 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);[/color]

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

Cheers,

Stuart.
[color=blue]
> os << pNode->m_data << ' ';
> if(pNode->m_pRight) output_all_less _than(t, os, pNode->m_pRight);
> }
> }
>
> HTH,
>
> Stuart.[/color]

[Josh Sebastian]

Re: BST: remove less than

On Sat, 04 Oct 2003 16:55:55 +0000, Richard Heathfield wrote:
[color=blue]
> I conclude that the algorithm is flawed.[/color]

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