Thread: equal members in BST question..

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    equal members in BST question..

    where do we put a member which equals to the root
    on the left
    or on the right

    ??

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Under my understanding of the traditional BST, you don't put it anywhere (duplicates are not added). If you're in a multimap-ish situation where you've got a key and a value, you would probably use the value to break ties, I guess. But adding a duplicate is a little silly, since you will never find it in a search.

  3. #3
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    thanks

  4. #4
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    how can i look for the node which is the least bigger
    then some number
    amongst all

    if i am looking for bigger then 3 in the tree

    and i got nodes 4 6 8 9 (tree nodes)

    it will pick 4

    ??
    Last edited by transgalactic2; 10-30-2008 at 01:28 PM.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Off the top of my head: I would search for the number. If I found it, take the least element of the right subtree. (If the right subtree is NULL, I'd have to go up a level and do some cases -- if I went left to get my number, then the parent would be the next largest element; if I went right, then I go up another level and do it again. If I don't have another level to go up, my number is maximal.) If I miss, I'd have to do something similar, I would think.

    Anyway, it feels a little recursive to me. I would draw some pictures to make sure I got all my cases right.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. question about static members and functions
    By e66n06 in forum C++ Programming
    Replies: 5
    Last Post: 01-07-2008, 02:41 PM
  2. Design layer question
    By mdoland in forum C# Programming
    Replies: 0
    Last Post: 10-19-2007, 04:22 AM
  3. opengl DC question
    By SAMSAM in forum Game Programming
    Replies: 6
    Last Post: 02-26-2003, 09:22 PM
  4. question about static members
    By Shadow12345 in forum C++ Programming
    Replies: 3
    Last Post: 01-07-2003, 10:21 AM
  5. Very simple question, problem in my Code.
    By Vber in forum C Programming
    Replies: 7
    Last Post: 11-16-2002, 03:57 PM