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
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
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.
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"
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; }
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.
this is the method i was given to implementCode: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; }
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!
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.
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???
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.
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.
I mean that the value of the node is what is important when you traverse the tree in order.
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
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.