overload operator[] help please

[ychen42]

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

[Salem]

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.

[iMalc]

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.

[ychen42]

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

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;
      }

[grumpy]

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.

[ychen42]

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.

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!

[Elysia]

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.

[ychen42]

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???

[whiteflags]

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.

[ychen42]

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???

[whiteflags]

I mean that the value of the node is what is important when you traverse the tree in order.

[ychen42]

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

[whiteflags]

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.