BST: remove less than

Discussion in 'C++' started by Ridimz, Oct 4, 2003.

  1. Ridimz

    Ridimz Guest

    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
    Ridimz, Oct 4, 2003
    #1
    1. Advertising

  2. Ridimz

    Mike Wahler Guest

    Re: remove less than

    "Ridimz" <> wrote in message
    news:drtfb.20510$...
    > 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

    >
    > Thanks,
    > Ridimz
    >
    >
    Mike Wahler, Oct 4, 2003
    #2
    1. Advertising

  3. On Sat, 04 Oct 2003 06:06:01 +0000, Ridimz wrote:

    > 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
    Josh Sebastian, Oct 4, 2003
    #3
  4. Josh Sebastian wrote:

    > On Sat, 04 Oct 2003 06:06:01 +0000, Ridimz wrote:
    >
    >> 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.


    (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 :
    "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
    Richard Heathfield, Oct 4, 2003
    #4
  5. Ridimz

    Ridimz Guest

    Re: remove less than

    "Ridimz" <> wrote...

    Gentlemen,

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

    Thank you!
    Ridimz
    Ridimz, Oct 4, 2003
    #5
  6. Ridimz wrote:
    >
    > 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 )
    }
    }

    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, Oct 6, 2003
    #6
  7. Re: remove less than

    "Ridimz" <> wrote in message
    news:drtfb.20510$...
    > 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::eek: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, Oct 6, 2003
    #7
  8. Re: remove less than

    "Stuart Golodetz" <> wrote in message
    news:3f8178bf$0$246$...
    > "Ridimz" <> wrote in message
    > news:drtfb.20510$...
    > > 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::eek: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::eek:stream&, const Node*) const not posted (but trivial to
    implement)

    Cheers,

    Stuart.

    > os << pNode->m_data << ' ';
    > if(pNode->m_pRight) output_all_less_than(t, os, pNode->m_pRight);
    > }
    > }
    >
    > HTH,
    >
    > Stuart.
    Stuart Golodetz, Oct 6, 2003
    #8
  9. On Sat, 04 Oct 2003 16:55:55 +0000, Richard Heathfield wrote:

    > 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
    Josh Sebastian, Oct 7, 2003
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. falcon
    Replies:
    10
    Views:
    18,656
    Roedy Green
    Feb 24, 2006
  2. Graeter than or less than

    , Jun 21, 2007, in forum: ASP .Net
    Replies:
    4
    Views:
    860
    bruce barker
    Jun 21, 2007
  3. jiajia wu
    Replies:
    0
    Views:
    355
    jiajia wu
    Oct 1, 2009
  4. Dwight Army of Champions
    Replies:
    4
    Views:
    2,749
    John H.
    Mar 17, 2010
  5. 6668
    Replies:
    0
    Views:
    148
Loading...

Share This Page