overload operator[] help please

This is a discussion on overload operator[] help please within the C++ Programming forums, part of the General Programming Boards category; so i have to overload this so that it returns the ith element of a red black tree im guessing ...

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    15

    overload operator[] help please

    so i have to overload this so that it returns the ith element of a red black tree

    im guessing this will be an array but im having trouble trying to start it off

    can give me some pointers on how to start please

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,674
    Do you know how to traverse a tree?

    If you do, then the only other thing you need to be able to do is count up to i and then stop.

    At which point, you return a reference to whatever node of your RB tree that you've found.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    You could always do it this way:
    Count the number of child nodes to the left of the root, and then traverse down the left or right side according to whether your index is less than or greater than that value. Then at subsequent nodes you only have to count the left hand side as the right hand side is parantcount-left-1.
    Draw a diagram to play around with, to observe how this works.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Nov 2010
    Posts
    15
    i do know how to traverse a tree

    psuedocode:
    node* x = new node;
    x->data = some value;
    node* temp;
    temp = root;

    //then we traverse through the tree
    //ill use a temp node to point to root of tree
    //then move down until we find the node we are look for
    //if found we return the node position
    //if this value is not in tree return 0

    while(root != NULL){

    if(x->data > root->data)
    root = root->right;
    else if(x->data <= root->data)
    root = root->left;
    else if(x->data == root->data)
    return value;
    }

    this is somewhat correct???

    heres the prototype that my prof wrote for the assignment

    Code:
    val_type Tree::operator[](unsigned long i)
          {
          //PROBLEM FOR THE STUDENT
          //Note: this should return the ith element of the tree.  if i is outside
          //of the range of indexes, the return value is undefined.  You can just do
          //what I did and return the default value in the NIL node in this case.
             return 0;
          }

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,441
    So what's the problem?

    You've described how to traverse the tree, and you have a function that is required to find a node (by traversing from root, "i" times). Do do something "i" times, a loop of some form would be appropriate.
    Right 98% of the time, and don't care about the other 3%.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Posts
    15
    Quote Originally Posted by grumpy View Post
    So what's the problem?

    You've described how to traverse the tree, and you have a function that is required to find a node (by traversing from root, "i" times). Do do something "i" times, a loop of some form would be appropriate.
    Code:
    val_type Tree::operator[](unsigned long i) {
    		//PROBLEM FOR THE STUDENT
    		//Note: this should return the ith element of the tree.  if i is outside
    		//of the range of indexes, the return value is undefined.  You can just do
    		//what I did and return the default value in the NIL node in this case.
    		return 0;
    	}
    this is the method i was given to implement

    i understand how to traverse the tree and find the ith element by comparing each node
    its the unsigned long i thats throwing me off i have no clue how to work with it though

    please help!

  7. #7
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,791
    The "i" tells you what node to find. Basically, it says find the ith node.
    What is the ith node? That can be difficult to define in a tree, but the most straightforward definition, I believe, is simply that you travel the tree and count every node you find until the count is i.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    Registered User
    Join Date
    Nov 2010
    Posts
    15
    its the i thats really throwing me off

    dont really know how i need to do

    what i mean is this:

    if we had a full binary tree with 7 nodes

    o
    / \
    o o
    / \ / \
    o o o o

    n we wanna find lets say the 5th element
    how can i do that with just unsigned i given???
    if i go from the root how do i know that its the 5th element in the tree

    what if it wasnt a full tree


    o
    / \
    o o
    / \ /
    o o o

    how do i get the 5th element from that???

  9. #9
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,744
    I believe you're just confused about which direction to go in first, but I think a lot of people agree with me here: the logical thing would be to traverse in order. That is to say that if a tree has the first ten numbers in it [0, 9], then tree[5] would be 4, for instance.

  10. #10
    Registered User
    Join Date
    Nov 2010
    Posts
    15
    Let's say the tree is [1-10] like so:
    Is this the right way to label them from 1-10???

    O1
    /\
    O2O3
    /\/\
    O4O5O6O7

    Or should I label them according to their value ie < >
    Like a heap???
    Last edited by ychen42; 11-10-2010 at 08:43 AM.

  11. #11
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,744
    I mean that the value of the node is what is important when you traverse the tree in order.

  12. #12
    Registered User
    Join Date
    Nov 2010
    Posts
    15
    sorry im just not getting it ='/

    lets use a tree with actual values
    from 1 to 7 inserted the usual tree way

    4-O
    /\
    2-O6-O
    /\/\
    1-O3-O5-O7-O

    lets say we want the 5th element in the tree
    5th will be 6 which is the right child of the root node
    am i correct???
    im having trouble writing the code for this

    sorry im been slow but please explain a bit or maybe psuedocode-ish it

  13. #13
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,744
    Breadth-first Tree traversal - Wikipedia, the free encyclopedia

    If you still have problems after reading that section at least, then post, but I think you will get it anyway.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Overload False Operator
    By kenryuakuma in forum C# Programming
    Replies: 6
    Last Post: 11-25-2009, 09:38 PM
  2. need help with overload operator[]
    By effa in forum C++ Programming
    Replies: 8
    Last Post: 10-09-2009, 06:30 AM
  3. Template overload of operator ++/--
    By Elysia in forum C++ Programming
    Replies: 26
    Last Post: 10-23-2007, 08:45 AM
  4. overload *
    By shuo in forum C++ Programming
    Replies: 5
    Last Post: 06-10-2007, 04:44 AM
  5. Having trouble with operator*=()
    By Lurker in forum C++ Programming
    Replies: 10
    Last Post: 10-26-2003, 02:03 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21